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.
|Title of host publication||2011 Data Compression Conference (DCC 2011), 29-31 March 2011, Snowbird, UT, USA|
|Publisher||Institute of Electrical and Electronics Engineers (IEEE)|
|Number of pages||10|
|Publication status||Published - 2011|