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

Publication: Research - peer-reviewJournal article – Annual report year: 2009

View graph of relations

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.
Original languageEnglish
JournalA C M Transactions on Algorithms
Publication date2009
Volume6
Issue1
Pagesarticle number 3
Number of pages14
ISSN1549-6325
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 0

Keywords

  • Compressed pattern matching, approximate string matching, regular expression matching, Ziv-Lempel
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 4813411