Regular Expression Searching over Ziv-Lempel Compressed Text

Gonzalo Navarro

We present a solution to the problem of regular expression searching on compressed text. The format we choose is the Ziv-Lempel family, specifically the LZ78 and LZW variants. Given a text of length u compressed into length n and a pattern of length m we report all the R occurrences of the pattern in the text in O(2^m + mn + Rm\log m) worst case time. On average this drops to O(m^2 + (n + R)\log m) or O(m^2+n+Ru/n) for most regular expressions. This is the first nontrivial result for this problem. The experimental results show that our compressed search algorithm needs half the time necessary for decompression plus searching, which is currently the only alternative.