Faster Approximate String Matching over Compressed Text
Gonzalo Navarro, Takuya Kida, Masayuki Takeda, Ayumi Shinohara and
Approximate string matching on compressed text was a problem open during
almost a decade. The two existing solutions are very recent. Despite that
they represent important complexity breakthroughs, in most practical cases
they are not useful, in the sense that they are slower than uncompressing
the text and then searching the uncompressed text.
In this paper we present a different approach, which reduces the problem to
multipattern searching of pattern pieces plus local decompression and direct
verification of candidate text areas. We show experimentally that this solution
is 10-30 times faster than previous work and up to three times faster than the
trivial approach of uncompressing and searching, thus becoming the first
practical solution to the problem.