The current explosion of stored information necessitates a new model o
f pattern matching, that of compressed matching. In this model one tri
es to find all occurrences of a pattern in a compressed text in time p
roportional to the compressed text size, i.e., without decompressing t
he 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 dif
ferent'' every time it appears in the compressed text. In this paper w
e consider pattern matching without decompression in the UNIX Z-compre
ssion. 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
+ m(2)) or O(n log m + m). We also introduce a new criterion to measu
re compressed matching algorithms, that of extra space. We show how to
modify our algorithms to achieve a trade-off between the amount of ex
tra space used and the algorithm's time complexity. (C) 1996 Academic
Press, Inc.