Tree compression with top trees

DOI10.1016/J.IC.2014.12.012zbMATH Open1327.68085DBLPjournals/iandc/BilleGLW15arXiv1304.5702OpenAlexW2174735959WikidataQ60554381 ScholiaQ60554381MaRDI QIDQ2347804FDOQ2347804

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)

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.

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

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

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)

Cites Work

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

Cited In (16)

• 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
• Title not available (Why is that?)
• Size-optimal top dag compression
• Slowing down top trees for better worst-case compression
• Random access in persistent strings and segment selection

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)