TY - GEN
T1 - Let sleeping files lie
T2 - Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms
AU - Amir, Amihood
AU - Benson, Gary
AU - Farach, Martin
N1 - Funding Information:
* Partially supported by NSF Grants CCR-92-23699 and IRI-90-13055. -Partially supported by NSF Grants DMS-90-05833 and DMS-87-20208. Supported by DIMACS under NSF Contract STC-88-09648.
PY - 1994
Y1 - 1994
N2 - 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 substring 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 tradeoff between the amount of extra space used and the algorithm's time complexity.
AB - 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 substring 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 tradeoff between the amount of extra space used and the algorithm's time complexity.
UR - http://www.scopus.com/inward/record.url?scp=0028337895&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0028337895
SN - 0898713293
T3 - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
SP - 705
EP - 714
BT - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
PB - Publ by ACM
Y2 - 23 January 1994 through 25 January 1994
ER -