Advertisement
Published in:
2007 | OriginalPaper | Chapter
Processing Compressed Texts: A Tractability Border
Author : Yury Lifshits
Published in: Combinatorial Pattern Matching
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
(
n
3
) time and the second problem in
O
(
n
2
m
) 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.