Space Efficient Linear Time Lempel-Ziv Factorization for Small Alphabets
Space Efficient Linear Time Lempel-Ziv Factorization for Small Alphabets
复制标题
DOI：
10.1109/dcc.2014.62
复制
发表时间：
2014-03
期刊：
影响因子：
--
通讯作者：
Keisuke Goto;H. Bannai
中科院分区：
文献类型：
--
作者：
Keisuke Goto;H. Bannai
本文提出了一种新的线性时间算法，用于计算长度为N的给定字符串在大小为σ的字母表上的Lempel-Ziv分解（LZ77），该算法仅利用N log N + O（σ log N）位的工作空间。当字母表大小较小时，这大大提高了以前线性时间LZ77分解的最佳空间要求（Karkkainen et al.）。CPM 2013)，即2N log N位，即两个长度为N的整数数组。实验表明，尽管算法增加了复杂性，但算法的速度仅比以前最快的线性时间算法慢2到3倍左右。
We present a new linear time algorithm for computing the Lempel-Ziv Factorization (LZ77) of a given string of length N on an alphabet of size σ, that utilizes only N log N + O(σ log N) bits of working space. When the alphabet size is small, this greatly improves the previous best space requirement for linear time LZ77 factorization (Karkkainen et al. CPM 2013), which is 2N log N bits, i.e. two integer arrays of length N. Experiments show that despite the added complexity of the algorithm, the speed of the algorithm is only around two to three times slower than previous fastest linear time algorithms.