Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts

Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts

Abstract	In this paper 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.
Type	Conference paper [With referee]
Conference	Proc. 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007)
Year	2007 Month July Vol. 4580 pp. 52-62
Publisher	Springer
Series	Lecture Notes in Computer Science
BibTeX data	[bibtex]
IMM Group(s)	Computer Science & Engineering