Abstract
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.
Original language | English |
---|---|
Journal | A C M Transactions on Algorithms |
Volume | 6 |
Issue number | 1 |
Pages (from-to) | article number 3 |
Number of pages | 14 |
ISSN | 1549-6325 |
DOIs | |
Publication status | Published - 2009 |
Keywords
- Compressed pattern matching
- approximate string matching
- regular expression matching
- Ziv-Lempel