A Comparison of Empirical Tree Entropies

DOI10.1007/978-3-030-59212-7_17MaRDI QIDQ6341936zbMATH OpenOpenAlexFDO

Authors Danny Hucke, Markus Lohrey, Louisa Seelbach Benkner

Publication date 1 June 2020

Full work available at URL https://doi.org/10.1007/978-3-030-59212-7_17

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: Whereas for strings, higher-order empirical entropy is the standard entropy measure, several different notions of empirical entropy for trees have been proposed in the past, notably label entropy, degree entropy, conditional versions of the latter two, and empirical entropy of trees (here, called label-shape entropy). In this paper, we carry out a systematic comparison of these entropy measures. We underpin our theoretical investigations by experimental results with real XML data.

Recommendations

• Entropy and optimal compression of some general plane trees
• Minimum-Entropy Tree Structures with a Given Terminal Node Assignment
• Entropy rates for Horton self-similar trees
• An(other) Entropy-Bounded Compressed Suffix Tree
• Fast algorithms for constructing maximum entropy summary trees

Cited in

(2)

• Entropy and optimal compression of some general plane trees
• Succinct preferential-attachment graphs

This page was built for publication: A Comparison of Empirical Tree Entropies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6341936)