LZW based compressed pattern matching
Tao Tao, Amar Mukherjee · 2004
In this paper, work on compressed pattern matching in LZW compressed files is reported. The reported work is based on author's well-known "almost-optimal" algorithm. The improvements include the multipattern matching and a faster implementation for so-called "simple pattern", which is defined as "a pattern with no symbol appearing more than once". Extensive experiments have been conducted to test the search performance and compared with the "decompress-then-search" and the best available compressed pattern-matching algorithm, particularly the BWT-based algorithms.