The Fully Compressed String Matching for Lempel-Ziv Encoding
Marek Karpiński, Wojciech Plandowski, Wojciech Rytter · 1995
The growing importance of massively stored information requires new approaches to efficient algorithms on texts represented in a compressed form. We consider here the {\em string-matching} problem in the compressed setting. This problem has been already investigated in \cite{AB}, \cite{ABF2}, \cite{ABF1}. A rather theoretical type of compression was considered in \cite{KRS}. In this paper we consider a practically important compression algorithm of Lempel and Ziv ({\em LZ algorithm}, in short). Denote by $LZ(w)$ the compressed version of a given string $w$ using the LZ algorithm. The {\em \bf Fully Compressed Matching Problem} is that of deciding if the pattern $P$ occurs in a text $T$, given only $LZ(P)$ and $LZ(T)$, without decompressing the pattern and the text. The first occurrence is reported, if there is any. Let $m$ and $n$ denote the sizes of $LZ(P)$ and $LZ(T)$, and $M$, $N$ be the sizes of uncompressed strings $P$ and $T$, respectively.