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 matchingtree compressiontop trees

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

• scientific article; zbMATH DE number 1617247 (Why is no real title available?)
• scientific article; zbMATH DE number 1150567 (Why is no real title available?)
• 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
• 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 Smallest Grammar Problem
• The complexity of tree automata and XPath on grammar-compressed trees
• Variations on the Common Subexpression Problem
• XML compression techniques: A survey and comparison

Cited in

(16)

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

Describes a project that uses

Uses Software

• TreeRePair
• XMill

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)