Let sleeping files lie: Pattern matching in Z-compressed files

Amihood Amir, Gary Benson, Martin Farach

    Research output: Contribution to journalArticlepeer-review


    The current explosion of stored information necessitates a new model of pattern matching, that of compressed matching. In this model one tries to find all occurrences of a pattern in a compressed text in time proportional to the compressed text size, i.e., without decompressing the text. The most effective general purpose compression algorithms are adaptive, in that the text represented by each compression symbol is determined dynamically by the data. As a result, the encoding of a sub-string depends on its location. Thus the same substring may "look different" every time it appears in the compressed text. In this paper we consider pattern matching without decompression in the UNIX Z-compression. This is a variant of the Lempel-Ziv adaptive compression scheme. If n is the length of the compressed text and m is the length of the pattern, our algorithms find the first pattern occurrence in time O(n+m2) or O(n log m+m). We also introduce a new criterion to measure compressed matching algorithms, that of extra space. We show how to modify our algorithms to achieve a trade-off between the amount of extra space used and the algorithm's time complexity.

    Original languageEnglish (US)
    Pages (from-to)299-307
    Number of pages9
    JournalJournal of Computer and System Sciences
    Issue number2
    StatePublished - Apr 1996

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science
    • Applied Mathematics
    • Computer Networks and Communications
    • Computational Theory and Mathematics


    Dive into the research topics of 'Let sleeping files lie: Pattern matching in Z-compressed files'. Together they form a unique fingerprint.

    Cite this