Tree compression with top trees

DOI10.1016/J.IC.2014.12.012MaRDI QIDQ2347804zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Philip Bille, Inge Li Gørtz, Gad M. Landau, Oren Weimann

Publication date 9 June 2015

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.5702

zbMATH Keywords

pattern matchingtop treestree compression

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: We introduce a new compression scheme for labeled trees based on top trees. Our compression scheme is the first to simultaneously take advantage of internal repeats in the tree (as opposed to the classical DAG compression that only exploits rooted subtree repeats) while also supporting fast navigational queries directly on the compressed representation. We show that the new compression scheme achieves close to optimal worst-case compression, can compress exponentially better than DAG compression, is never much worse than DAG compression, and supports navigational queries in logarithmic time.

Recommendations

• Tree compression with top trees
• Slowing down top trees for better worst-case compression
• Tight bounds for top tree compression
• TREE COMPRESSION AND OPTIMIZATION WITH APPLICATIONS

Cites work

• Algorithmics on SLP-compressed strings: a survey
• Automata, Languages and Programming
• Compressing and indexing labeled trees, with applications
• Efficient algorithms for Lempel-Ziv encoding
• Foundations of Software Science and Computation Structures
• scientific article; zbMATH DE number 1617247 (Why is no real title available?)
• scientific article; zbMATH DE number 1150567 (Why is no real title available?)
• Maintaining information in fully dynamic trees with top trees
• Minimizing diameters of dynamic trees
• Random access to grammar-compressed strings
• Representing trees of higher degree
• Succinct ordinal trees with level-ancestor queries
• Succinct representation of balanced parentheses and static trees
• The complexity of tree automata and XPath on grammar-compressed trees
• The Smallest Grammar Problem
• Variations on the Common Subexpression Problem
• XML compression techniques: A survey and comparison

Cited in

(19)

• Top tree compression of tries
• Balancing straight-line programs for strings and trees
• Constructing small tree grammars and small circuits for formulas
• Size-optimal top dag compression
• Algorithmic height compression of unordered trees
• Approximation of smallest linear tree grammar
• Compressing and indexing labeled trees, with applications
• scientific article; zbMATH DE number 19770 (Why is no real title available?)
• Slowing down top trees for better worst-case compression
• Tight bounds for top tree compression
• Approximation of trees by self-nested trees
• Tree compression with top trees
• scientific article; zbMATH DE number 7765406 (Why is no real title available?)
• Random access in persistent strings and segment selection
• Slowing down top trees for better worst-case compression
• Memoization on shared subtrees accelerates computations on genealogical forests
• Constant-time tree traversal and subtree equality check for grammar-compressed trees
• FL-RMQ: a learned approach to range minimum queries
• Constant delay traversal of grammar-compressed graphs with bounded rank

Describes a project that uses

Uses Software

• XMill
• TreeRePair

This page was built for publication: Tree compression with top trees

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