XML tree structure compression using RePair
XML tree structure compression using RePair
复制标题
DOI：
10.1016/j.is.2013.06.006
复制
发表时间：
2013-11-01
影响因子：
3.7
通讯作者：
Mennicke, Roy
中科院分区：
文献类型：
--
作者：
Lohrey, Markus;Maneth, Sebastian;Mennicke, Roy
XML树结构可以很方便地用有序无秩树来表示。由于XML标记的重复性，这些树可以使用基于字典的方法有效地压缩，例如最小有向无环图（DAG）或直线上下文无关（SLCF）树语法。虽然最小SLCF树文法通常小于最小DAG，但它们不能在多项式时间内计算，除非P = NP。在这里，我们提出了一个新的线性时间算法计算小SLCF树文法，称为TreeRePair，并表明，它大大优于最知名的以前的算法BPLEX。TreeRePair是Larsson和Moffat的RePair字符串压缩算法的树的推广。SLCF树文法可以用作树的有效存储表示。使用TreeRePair，我们能够生成我们所知道的有序树的最小可查询内存表示。我们在一个大型语料库的常用XML文档的调查表明，树遍历TreeRePair语法是14倍慢于指针结构和5倍慢于简洁的树，而内存消耗只有1/43和1/6，分别。关于文件压缩，我们能够表明，基于霍夫曼编码的TreeRePair语法提供的压缩比可比的最知名的XML文件压缩器。(C)2013爱思唯尔有限公司保留所有权利。
XML tree structures can conveniently be represented using ordered unranked trees. Due to the repetitiveness of XML markup these trees can be compressed effectively using dictionary-based methods, such as minimal directed acyclic graphs (DAGs) or straight-line context-free (SLCF) tree grammars. While minimal SLCF tree grammars are in general smaller than minimal DAGs, they cannot be computed in polynomial time unless P = NP. Here, we present a new linear time algorithm for computing small SLCF tree grammars, called TreeRePair, and show that it greatly outperforms the best known previous algorithm BPLEX. TreeRePair is a generalization to trees of Larsson and Moffat's RePair string compression algorithm. SLCF tree grammars can be used as efficient memory representations of trees. Using TreeRePair, we are able to produce the smallest queryable memory representation of ordered trees that we are aware of. Our investigations over a large corpus of commonly used XML documents 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. With respect to file compression we are able to show that a Huffman-based coding of TreeRePair grammars gives compression ratios comparable to the best known XML file compressors. (C) 2013 Elsevier Ltd. All rights reserved.