Implementation of Algebraic Algorithms for Approximate Pattern Matching on Compressed Data

Approximate pattern matching is a well-studied problem on strings: given a text t and a pattern p, find all substrings of t that are similar to p. The measure of similarity that we use in this work is the length of the longest common subsequence (LCS) of two strings. We implement an algorithm that solves the approximate pattern matching problem for a pattern p of length m and a text t of length n in time O(mn) implicitly storing all the LCS values in an algebraic structure of size O(m + n). We additionally generalize the algorithm to calculate the longest common subsequence of a plain (uncompressed) pattern string of length m and a text string of length n, compressed by a context-free grammar of length k in time O(mk log m). Using the fact that this algorithm’s time complexity does not depend on the length of the uncompressed text, we show that the algorithm will achieve a substantial speedup on specific types of compressed texts, even with the increase in the running time constant resulting from complex operations with algebraic structures. We compare the running time of our algorithm to the standard dynamic programming algorithm for approximate pattern matching and to the approximate pattern matching utility agrep, and we demonstrate an improvement for some specific types of text in both cases, even though our algorithm is less optimal than the standard solutions on random texts. Keywords: string algorithms, approximate pattern matching, longest common subsequence, context-free grammar.