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
Volume6
Issue number1
Pages (from-to)article number 3
Number of pages14
ISSN1549-6325
DOIs
StatePublished - 2009
Peer-reviewedYes
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:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

ID: 4813411