Efficient algorithms for Lempel-Ziv encoding
Efficient algorithms for Lempel-Ziv encoding
复制标题
Lempel-Ziv 编码的高效算法
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
W. Rytter
中科院分区：
文献类型：
--
作者：
L. Gąsieniec;Marek Karpinski;Wojciech Plandowski;W. Rytter
我们考虑几个基本问题的文本，并表明，如果输入的文本是由他们的Lempel-Ziv代码，然后可以确定性地解决问题的情况下，在多项式时间的原始（未压缩）的文本是指数大小。大量存储的信息的重要性日益增加，需要新的方法来压缩文本的算法，而无需解压缩。用LZ（ω）表示由Lempel-Ziv编码算法产生的字符串ω的版本。对于给定的压缩字符串LZ（T），LZ（P），我们给出了第一个已知的确定性多项式时间算法来计算T中模式的所有出现、T的所有周期、T的所有回文和T的所有平方的集合的压缩表示.然后我们考虑几个经典的语言识别问题：
We consider several basic problems for texts and show that if the input texts are given by their Lempel-Ziv codes then the problems can be solved deterministically in polynomial time in the case when the original (uncompressed) texts are of exponential size. The growing importance of massively stored information requires new approaches to algorithms for compressed texts without decompressing. Denote by LZ(ω) the version of a string ω produced by Lempel-Ziv encoding algorithm. For given compressed strings LZ(T), LZ(P) we give the first known deterministic polynomial time algorithms to compute compressed representations of the set of all occurrences of the patternP in T, all periods of T, all palindromes of T, and all squares of T. Then we consider several classical language recognition problems: