Adapting the Knuth-Morris-Pratt algorithm for pattern matching in Huffman encoded texts

We perform compressed pattern matching in Huffman encoded texts. A modified Knuth-Morris-Pratt (KMP) algorithm is used in order to overcome the problem of false matches, i.e., an occurrence of the encoded pattern in the encoded text that does not correspond to an occurrence of the pattern itself in the original text. We propose a bitwise KMP algorithm that can move one extra bit in the case of a mismatch, since the alphabet is binary. To avoid processing any encoded text bit more than once, a preprocessed table is used to determine how far to back up when a mismatch is detected, and is defined so that the encoded pattern is always aligned with the start of a codeword in the encoded text. We combine our KMP algorithm with two Huffman decoding algorithms which handle more than a single bit per machine operation; Skeleton trees defined by Klein [1], and numerical comparisons between special canonical values and portions of a sliding window presented in Moffat and Turpin [3]. We call the combined algorithms sk-kmp and win-kmp respectively. The following table compares our algorithms with cgrep of Moura et al. [2] and agrep which searches the uncompressed text. Columns three and four compare the compression performance (size of the compressed text as a percentage of the uncom-pressed text) of the Huffman code (huff) with cgrep. The next columns compare the processing time of pattern matching of these algorithms. The “decompress and search ” methods, which decode using skeleton trees or Moffat and Turpin’s sliding window and search in parallel using agrep, are called sk-d and win-d respectively. The search times are average values for patterns ranging from infrequent to frequent ones