Practical Parallel Lempel-Ziv Factorization
Practical Parallel Lempel-Ziv Factorization
复制标题
DOI：
10.1109/dcc.2013.20
复制
发表时间：
2013-03
期刊：
影响因子：
--
通讯作者：
Julian Shun;Fuyao Zhao
中科院分区：
文献类型：
--
作者：
Julian Shun;Fuyao Zhao
在大数据时代，对高效数据压缩算法的需求不断增长。一种广泛使用的数据压缩方法是Lempel-Ziv-77（LZ 77）方法，它是流行的压缩包（如gzip和PKZIP）中的子例程。最近已经有很多关于开发Lempel-Ziv分解（相当于LZ 77压缩）的实用顺序算法的努力，但在实际并行实现方面的研究并不令人满意。在这项工作中，我们提出了一个简单的工作效率的并行算法Lempel-Ziv因式分解。我们从理论上表明，我们的算法需要线性工作和运行在O（log 2 n）的时间（随机）为常数字母和O（n）的时间（<; 1）为整数字母。我们目前的实验结果表明，我们的算法是有效的，并取得了良好的加速Lempel-Ziv分解的最佳顺序实现。
In the age of big data, the need for efficient data compression algorithms has grown. A widely used data compression method is the Lempel-Ziv-77 (LZ77) method, being a subroutine in popular compression packages such as gzip and PKZIP. There has been a lot of recent effort on developing practical sequential algorithms for Lempel-Ziv factorization (equivalent to LZ77 compression), but research in practical parallel implementations has been less satisfactory. In this work, we present a simple work-efficient parallel algorithm for Lempel-Ziv factorization. We show theoretically that our algorithm requires linear work and runs in O(log2 n) time (randomized) for constant alphabets and O(nϵ) time (ϵ <; 1) for integer alphabets. We present experimental results showing that our algorithm is efficient and achieves good speedup with respect to the best sequential implementations of Lempel-Ziv factorization.