Conference paper
Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts
In
Lecture Notes in Computer Science
—
2007, pp. 52-62
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. In practical applications the space is likely to be a bottleneck and therefore this is of crucial importance.
| Language: | English |
|---|---|
| Publisher: | Springer |
| Year: | 2007 |
| Pages: | 52-62 |
| Proceedings: | 18th Annual Symposium on Combinatorial Pattern Matching |
| Series: | Lecture Notes in Computer Science |
| ISBN: | 3540734368 , 3540734376 , 9783540734369 and 9783540734376 |
| ISSN: | 03029743 |
| Types: | Conference paper |
| DOI: | 10.1007/978-3-540-73437-6_8 |
| ORCIDs: | Gørtz, Inge Li |
