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

Philip Bille, Rolf Fagerberg, Inge Li Gørtz

    Research output: Contribution to journalJournal articleResearchpeer-review


    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
    Issue number1
    Pages (from-to)article number 3
    Number of pages14
    Publication statusPublished - 2009


    • Compressed pattern matching
    • approximate string matching
    • regular expression matching
    • Ziv-Lempel

    Cite this