Faster approximate string matching over compressed text

Gonzalo Navarro, Takuya Kida, Masayuki Takeda, Ayumi Shinohara, Setsuo Arikawa

Research output: Contribution to journalArticlepeer-review

36 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)459-468
Number of pages10
JournalProceedings of the Data Compression Conference
Publication statusPublished - 2001


Dive into the research topics of 'Faster approximate string matching over compressed text'. Together they form a unique fingerprint.

Cite this