6 papers
Hypersuccinct Trees -- New universal tree source codes for optimal compressed tree data structures and range minima
J. Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner +1
We present a new universal source code for distributions of unlabeled binary and ordinal trees that achieves optimal compression to within lower order terms for all tree sources co…
A Comparison of Empirical Tree Entropies
Danny Hucke, Markus Lohrey, Louisa Seelbach Benkner
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, notabl…
On the Collection of Fringe Subtrees in Random Binary Trees
Louisa Seelbach Benkner, Stephan Wagner
A fringe subtree of a rooted tree is a subtree consisting of one of the nodes and all its descendants. In this paper, we are specifically interested in the number of non-isomorphic…
Practical Random Access to SLP-Compressed Texts
Travis Gagie, Tomohiro I, Giovanni Manzini +4
Grammar-based compression is a popular and powerful approach to compressing repetitive texts but until recently its relatively poor time-space trade-offs during real-life construct…
Entropy Bounds for Grammar-Based Tree Compressors
Danny Hucke, Markus Lohrey, Louisa Seelbach Benkner
The definition of -order empirical entropy of strings is extended to node labelled binary trees. A suitable binary encoding of tree straight-line programs (that have been u…
Tunneling on Wheeler Graphs
Jarno Alanko, Travis Gagie, Gonzalo Navarro +1
The Burrows-Wheeler Transform (BWT) is an important technique both in data compression and in the design of compact indexing data structures. It has been generalized from single st…