Slowing down top trees for better worst-case compression

DOI10.4230/LIPICS.CPM.2018.16MaRDI QIDQ5140780zbMATH OpenOpenAlexFDO

Authors Bartłomiej Dudek, Paweł Gawrychowski

Publication date 16 December 2020

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

zbMATH Keywords

compressiontop treestree grammars

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)

Abstract: We consider the top tree compression scheme introduced by Bille et al. [ICALP 2013] and construct an infinite family of trees on $n$ nodes labeled from an alphabet of size $sigma$, for which the size of the top DAG is $Theta(fracnlo{g}_{s}igmanloglo{g}_{s}igman)$. Our construction matches a previously known upper bound and exhibits a weakness of this scheme, as the information-theoretic lower bound is $Omega(fracnlo{g}_{s}igman)$. This settles an open problem stated by Lohrey et al. [arXiv 2017], who designed a more involved version achieving the lower bound. We show that this can be also guaranteed by a very minor modification of the original scheme: informally, one only needs to ensure that different parts of the tree are not compressed too quickly. Arguably, our version is more uniform, and in particular, the compression procedure is oblivious to the value of $sigma$.

Recommendations

• Tree compression with top trees
• Tight bounds for top tree compression
• Tree compression with top trees
• Size-optimal top dag compression
• TREE COMPRESSION AND OPTIMIZATION WITH APPLICATIONS

Cites work

• Approximation of smallest linear tree grammar
• Compressing and indexing labeled trees, with applications
• LZ77 factorisation of trees
• The complexity of tree automata and XPath on grammar-compressed trees
• Tight bounds for top tree compression
• Tree compression with top trees
• Variations on the Common Subexpression Problem

Cited in

(8)

• A speed-up for the commute between subword trees and DAWGs.
• Top tree compression of tries
• Balancing straight-line programs for strings and trees
• Tree compression with top trees
• Size-optimal top dag compression
• scientific article; zbMATH DE number 19770 (Why is no real title available?)
• Tight bounds for top tree compression
• Tree compression with top trees

This page was built for publication: Slowing down top trees for better worst-case compression

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