Publication: Research - peer-review › Journal article – Annual report year: 2009
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.
|Citations||Web of Science® Times Cited: 0|
- Compressed pattern matching, approximate string matching, regular expression matching, Ziv-Lempel