Tree compression with top trees

DOI10.1016/j.ic.2014.12.012zbMath1327.68085arXiv1304.5702OpenAlexW2174735959WikidataQ60554381 ScholiaQ60554381MaRDI QIDQ2347804

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

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

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

Related Items

Approximation of smallest linear tree grammar ⋮ Constructing small tree grammars and small circuits for formulas ⋮ Size-optimal top dag compression ⋮ Random access in persistent strings and segment selection ⋮ Unnamed Item ⋮ Tight Bounds for Top Tree Compression ⋮ Tree compression using string grammars ⋮ Grammar-based compression of unranked trees ⋮ Constant-time tree traversal and subtree equality check for grammar-compressed trees ⋮ Compressed range minimum queries ⋮ Top tree compression of tries ⋮ Constant delay traversal of grammar-compressed graphs with bounded rank ⋮ Balancing straight-line programs for strings and trees ⋮ Slowing Down Top Trees for Better Worst-Case Compression

Uses Software

• XMill
• TreeRePair

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Representing trees of higher degree
• The complexity of tree automata and XPath on grammar-compressed trees
• XML compression techniques: A survey and comparison
• Succinct Representation of Balanced Parentheses and Static Trees
• Algorithmics on SLP-compressed strings: A survey
• Maintaining information in fully dynamic trees with top trees
• Compressing and indexing labeled trees, with applications
• The Smallest Grammar Problem
• Variations on the Common Subexpression Problem
• Minimizing diameters of dynamic trees
• Efficient algorithms for Lempel-Ziv encoding
• Foundations of Software Science and Computation Structures
• Automata, Languages and Programming