Processing Compressed Texts: A Tractability Border
Processing Compressed Texts: A Tractability Border
复制标题
处理压缩文本：易处理边界
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Y. Lifshits
中科院分区：
文献类型：
--
作者：
Y. Lifshits
我们可以对压缩文本有效地执行哪些操作（无需完全解包）？在本文中，我们考虑三个基本问题：（1）检查两个压缩文本的相等性，（2）检查一个压缩文本是否是另一压缩文本的子串，（3）计算两个相同长度的压缩文本之间不同符号的数量（汉明距离）。
我们提出了一种算法，可以在 O(n3) 时间内解决第一个问题，在 O(n2m) 时间内解决第二个问题。这里 n 是文本的压缩表示（我们考虑直线程序的表示）的大小，m 是模式的压缩表示的大小。接下来，我们证明第三个问题实际上是#P-完全的。因此，我们指出了一对相似的问题（等价检查、汉明距离计算），它们在压缩文本上具有截然不同的复杂性。我们用于问题（1）和（2）的算法技术有助于计算压缩文本的最小周期和覆盖范围。
What kind of operations can we perform effectively (without full unpacking) with compressed texts? In this paper we consider three fundamental problems: (1) check the equality of two compressed texts, (2) check whether one compressed text is a substring of another compressed text, and (3) compute the number of different symbols (Hamming distance) between two compressed texts of the same length.
We present an algorithm that solves the first problem in O(n3) time and the second problem in O(n2m) time. Here n is the size of compressed representation (we consider representations by straight-line programs) of the text and m is the size of compressed representation of the pattern. Next, we prove that the third problem is actually #P-complete. Thus, we indicate a pair of similar problems (equivalence checking, Hamming distance computation) that have radically different complexity on compressed texts. Our algorithmic technique used for problems (1) and (2) helps for computing minimal periods and covers of compressed texts.