Engineering Hybrid DenseZDDs
Engineering Hybrid DenseZDDs
复制标题
工程混合密集ZDD
DOI：
10.1109/dcc.2016.69
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Kunihiko Sadakane:
中科院分区：
文献类型：
--
作者：
Taito Lee;Shuhei Denzumi;Kunihiko Sadakane:
由Larsson和Moat提出的Re-Pair算法(Re-Pair)是一种简单的基于文法的压缩方法，获得了良好的压缩比。尽管对于长度为n的输入，重配对在O(N)时间和空间内运行，但它不能用于大输入，因为它运行Oine并且消耗大量的内存空间。本文提出了一种基于模式化再对的在线语法转换算法，并给出了使用该算法的压缩方法。该算法使用O(G)空间，运行时间为O(nlog^h)，其中g和^h分别是文法中产生式规则的个数和由规则生成的句法树的最大高度。我们实现了我们的方法，与原始的重构方法相比，它显著地减少了内存使用量，而压缩比几乎没有变化。
The Re-Pair algorithm (Re-Pair), proposed by Larsson and Moat, is a simple grammar-based compression method that achieves a good compression ratio. Although Re-Pair runs in O(n) time and space for an input of length n, it cannot be used with a large input, because it runs oine and consumes substantial memory space. In this paper, we propose an online grammar transformation algorithm based on a modied Re-Pair along with a compression method using the algorithm. The proposed algorithm runs in O(n log^ h) time using O(g) space, where g and ^h are the number of production rules in a grammar and the maximum height of syntax trees generated by the rules, respectively. We implemented our method and demonstrated that it signicantly reduces memory usage with little sacrice of compression ratio in comparison with the original Re-Pair.