Computing LZ77 in Run-Compressed Space
Computing LZ77 in Run-Compressed Space
复制标题
在运行压缩空间中计算 LZ77
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
N. Prezza
中科院分区：
文献类型：
--
作者：
A. Policriti;N. Prezza
本文证明了文本T ε n的LZ 77因子分解可以在O（Rlog n）位的工作空间和O（nlog R）时间内计算，R是T的Burrows-Wheeler变换的游程数（反向）.对于（极度）重复的输入，工作空间可以低至O（log n）位：比文本本身呈指数级小。因此，我们的研究结果发现重要的应用在建设重复意识的自我索引和压缩重复的文本集合在小的工作空间。
In this paper, we show that the LZ77 factorization of a text T ε Σn can be computed in O(R log n) bits of working space and O(n log R) time, R being the number of runs in the Burrows-Wheeler transform of T (reversed). For (extremely) repetitive inputs, the working space can be as low as O(log n) bits: exponentially smaller than the text itself. Hence, our result finds important applications in the construction of repetition-aware self-indexes and in the compression of repetitive text collections within small working space.