Size-optimal top dag compression

DOI10.1016/J.IPL.2019.03.001MaRDI QIDQ2414042zbMATH OpenOpenAlexFDO

Authors Markus Lohrey, Carl Philipp Reh, Kurt Sieber

Publication date 10 May 2019

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

algorithmsdata structurestree compression

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: It is shown that for a given ordered node-labelled tree of size $n$ and with $s$ many different node labels, one can construct in linear time a top dag of height $O(logn)$ and size $O(n/lo{g}_{s}igman)capO(dcdotlogn)$, where $sigma=max2,s$ and $d$ is the size of the minimal dag. The size bound $O(n/lo{g}_{s}igman)$ is optimal and improves on previous bounds.

Recommendations

• Tight bounds for top tree compression
• Slowing down top trees for better worst-case compression
• Tree compression with top trees
• Tree compression with top trees
• XML compression via directed acyclic graphs

Cites work

• Constructing small tree grammars and small circuits for formulas
• Grammar-Based Tree Compression
• Slowing down top trees for better worst-case compression
• Tight bounds for top tree compression
• Tree compression with top trees
• Variations on the Common Subexpression Problem

Cited in

(4)

• Slowing down top trees for better worst-case compression
• Tight bounds for top tree compression
• Tree compression with top trees
• Slowing down top trees for better worst-case compression

This page was built for publication: Size-optimal top dag compression

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