5 papers · 1 filter
Streaming algorithms for products of probabilities
Markus Lohrey, Leon Rische, Louisa Seelbach Benkner +1
We consider streaming algorithms for approximating a product of input probabilities up to multiplicative error of . It is shown that every randomized streaming algorithm for t…
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…
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…