Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts
<|reference_start|>Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts: 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.<|reference_end|>
@article{bille2006improved,
    title={Improved Approximate String Matching and Regular Expression Matching on
  Ziv-Lempel Compressed Texts},
    author={Philip Bille, Rolf Fagerberg, Inge Li Goertz},
    journal={arXiv preprint arXiv:cs/0609085},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0609085},
    primaryClass={cs.DS}
}