Bit-parallel approach to approximate string matching in compressed texts

Addresses the problem of approximate string matching on compressed text. We consider this problem for a text string described in terms of a collage system, which is a formal system proposed by T. Kida et al. (1999) that captures various dictionary-based compression methods. We present an algorithm that exploits bit-parallelism, assuming that our problem fits in a single machine word, e.g. (m - k)(k + 1) ≤ L, where m is the pattern length, k is the number of allowed errors and L is the length, in bits, of the machine word. For a class of simple collage systems, the algorithm runs in O(k²(∥D∥ + |S|) + km) time using O(k²∥D∥) space, where ∥D∥ is the size of dictionary D and |S| is the number of tokens in the sequence S. The LZ78 (Lempel-Ziv, 1978) and the LZW (Lempel-Ziv-Welch, 1984) compression methods are covered by this class. Since we can regard ∥D∥ + |S| as the compressed length, the time and space complexities are O(k²n + km) and O(k²n), respectively. For general k and m, they become O(k³mn/L + km) and O(k³mn/L). Thus, our algorithm is competitive to the algorithm proposed by J. Kärkkäinen, et al. (2000), which runs in O(km) time using O(kmn) space, when k = O(√L).