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



AbstractIn 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.
TypeConference paper [With referee]
ConferenceProc. 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007)
Year2007    Month July    Vol. 4580    pp. 52-62
PublisherSpringer
SeriesLecture Notes in Computer Science
BibTeX data [bibtex]
IMM Group(s)Computer Science & Engineering