Tree Structure Compression with RePair

Markus Lohrey; Sebastian Maneth; Roy Mennicke

doi:10.1109/DCC.2011.42

Tree Structure Compression with RePair

Markus Lohrey, Sebastian Maneth, Roy Mennicke

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Larsson and Moffat's RePair algorithm is generalized from strings to trees. The new algorithm (TreeRePair) produces straight-line linear context-free tree (SLT) grammars which are smaller than those produced by previous grammar-based compressors such as BPLEX. Experiments show that a Huffman-based coding of the resulting grammars gives compression ratios comparable to the best known XML file compressors. Moreover, SLT grammars can be used as efficient memory representation of trees. Our investigations show that tree traversals over TreeRePair grammars are 14 times slower than over pointer structures and 5 times slower than over succinct trees, while memory consumption is only 1/43 and 1/6, respectively.

Original language	English
Title of host publication	2011 Data Compression Conference (DCC 2011), 29-31 March 2011, Snowbird, UT, USA
Publisher	Institute of Electrical and Electronics Engineers
Pages	353-362
Number of pages	10
ISBN (Print)	978-1-61284-279-0
DOIs	https://doi.org/10.1109/DCC.2011.42
Publication status	Published - 2011

Access to Document

10.1109/DCC.2011.42

http://dx.doi.org/10.1109/DCC.2011.42

Cite this

@inproceedings{9826e0f6658a40d8828558abf0c9d109,

title = "Tree Structure Compression with RePair",

abstract = "Larsson and Moffat's RePair algorithm is generalized from strings to trees. The new algorithm (TreeRePair) produces straight-line linear context-free tree (SLT) grammars which are smaller than those produced by previous grammar-based compressors such as BPLEX. Experiments show that a Huffman-based coding of the resulting grammars gives compression ratios comparable to the best known XML file compressors. Moreover, SLT grammars can be used as efficient memory representation of trees. Our investigations show that tree traversals over TreeRePair grammars are 14 times slower than over pointer structures and 5 times slower than over succinct trees, while memory consumption is only 1/43 and 1/6, respectively.",

author = "Markus Lohrey and Sebastian Maneth and Roy Mennicke",

year = "2011",

doi = "10.1109/DCC.2011.42",

language = "English",

isbn = "978-1-61284-279-0",

pages = "353--362",

booktitle = "2011 Data Compression Conference (DCC 2011), 29-31 March 2011, Snowbird, UT, USA",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

}

TY - GEN

T1 - Tree Structure Compression with RePair

AU - Lohrey, Markus

AU - Maneth, Sebastian

AU - Mennicke, Roy

PY - 2011

Y1 - 2011

N2 - Larsson and Moffat's RePair algorithm is generalized from strings to trees. The new algorithm (TreeRePair) produces straight-line linear context-free tree (SLT) grammars which are smaller than those produced by previous grammar-based compressors such as BPLEX. Experiments show that a Huffman-based coding of the resulting grammars gives compression ratios comparable to the best known XML file compressors. Moreover, SLT grammars can be used as efficient memory representation of trees. Our investigations show that tree traversals over TreeRePair grammars are 14 times slower than over pointer structures and 5 times slower than over succinct trees, while memory consumption is only 1/43 and 1/6, respectively.

AB - Larsson and Moffat's RePair algorithm is generalized from strings to trees. The new algorithm (TreeRePair) produces straight-line linear context-free tree (SLT) grammars which are smaller than those produced by previous grammar-based compressors such as BPLEX. Experiments show that a Huffman-based coding of the resulting grammars gives compression ratios comparable to the best known XML file compressors. Moreover, SLT grammars can be used as efficient memory representation of trees. Our investigations show that tree traversals over TreeRePair grammars are 14 times slower than over pointer structures and 5 times slower than over succinct trees, while memory consumption is only 1/43 and 1/6, respectively.

U2 - 10.1109/DCC.2011.42

DO - 10.1109/DCC.2011.42

M3 - Conference contribution

SN - 978-1-61284-279-0

SP - 353

EP - 362

BT - 2011 Data Compression Conference (DCC 2011), 29-31 March 2011, Snowbird, UT, USA

PB - Institute of Electrical and Electronics Engineers

ER -

Tree Structure Compression with RePair

Abstract

Access to Document

Fingerprint

Cite this