We study the approximate string matching and regular expression matching problem for the case when the text to be searched is compressed with the Ziv-Lempel adaptive dictionary compression schemes. We present a time-space trade-off that leads to algorithms improving the previously known complexities for both problems. In particular, we significantly improve the space bounds, which in practical applications are likely to be a bottleneck.
- Compressed pattern matching
- approximate string matching
- regular expression matching
Bille, P., Fagerberg, R., & Gørtz, I. L. (2009). Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts. A C M Transactions on Algorithms, 6(1), article number 3. https://doi.org/10.1145/1644015.1644018