Faster approximate string matching over compressed text

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

研究成果: Article査読

36 被引用数 (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.

ジャーナルData Compression Conference Proceedings
出版ステータスPublished - 2001

ASJC Scopus subject areas

  • コンピュータ ネットワークおよび通信


「Faster approximate string matching over compressed text」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。