Journal article
Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts
In
A C M Transactions on Algorithms
—
2009, Volume 6, Issue 1, pp. 1-14
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.
| Language: | English |
|---|---|
| Publisher: | ACM, 2 Penn Plaza, Suite 701, New York, NY, USA |
| Year: | 2009 |
| Pages: | 1-14 |
| ISSN: | 15496333 and 15496325 |
| Types: | Journal article |
| DOI: | 10.1145/1644015.1644018 |
| ORCIDs: | Gørtz, Inge Li |
