Time/Space Efficient Compressed Pattern Matching
Leszek Antoni Gąsieniec, Igor Potapov · 2002
An exact pattern matching problem is to find all occurrences of a pattern p in a text t. We say that the pattern matching algorithm is optimal if its running time is linear in the sizes of t and p, i.e. O(t+p): Perhaps one of the most interesting settings of the pattern matching problem is when one has to design an efficient algorithm with a help of small extra space. In this paper we explore this setting to the extreme. We use an additional assumption that the text t is available only in a compressed form, represented by a straight-line program. The compression methods based on efficient construction of straight-line programs are as competitive as the compression standards, including Lempel-Ziv's compression scheme and recently intensively studied compression via block sorting, due to Burrows and Wheeler. Our main result consists in solving compressed string matching problem in optimal linear time when only a constant size of extra space is available. We also discuss an efficient implementation of a version our algorithm showing that the new concept may have also interesting real applications. Our result is in contrast with many other compressed pattern matching algorithms where the goal is to find all pattern occurrences in time related to the size of a compressed text. However one must remember that all previous algorithms used at least linear (in compressed text, dictionary, and pattern) extra memory while our algorithm can be implemented in constant size extra space. Also from a practical point of view, when a compression ratio is constant (very rarely smaller than 25%), there is no dramatic difference between the running time based on the size of the compressed text and the size of the original text, while the additional storage requirements can be unrealistic.