TY - JOUR
T1 - Optimal Two-Dimensional Compressed Matching
AU - Amir, Amihood
AU - Benson, Gary
AU - Farach, Martin
N1 - Funding Information:
Recent proliferation of digitized data and the unprecedented growth in the volume of stored and transmitted data motivated the definition of the compressed matching paradigm. This is the problem of efficiently finding a pattern P in a compressed text T without the need to decompress. We present the first optimal two-dimensional compressed matching algorithm. The compression under consideration is the two dimensional run-length compression, used by FAX transmission. We achieve optimal time by proving new properties of two-dimensional periodicity. This enables performing duels in which no witness is required. At the heart of the dueling idea lies the concept that two overlapping occurrences of a pattern in a text can use the content of a predetermined text position or witness in the overlap to eliminate one of them. Finding witnesses is a costly operation in a compressed text, thus the importance of witness-free dueling. Q 1997 Academic Press UPartially supported by NSF Grant IRI-90-13055. E-mail: [email protected]. ²Partially supported by NSF Grant DMS-90-05833. E-mail: [email protected]. mssm.edu. ³Supported by DIMACS under NSF Contract STC-88-09648. E-mail: [email protected].
PY - 1997/8
Y1 - 1997/8
N2 - Recent proliferation of digitized data and the unprecedented growth in the volume of stored and transmitted data motivated the definition of the compressed matching paradigm. This is the problem of efficiently finding a pattern P in a compressed text T without the need to decompress. We present the first optimal two-dimensional compressed matching algorithm. The compression under consideration is the two dimensional run-length compression, used by FAX transmission. We achieve optimal time by proving new properties of two-dimensional periodicity. This enables performing duels in which no witness is required. At the heart of the dueling idea lies the concept that two overlapping occurrences of a pattern in a text can use the content of a predetermined text position or witness in the overlap to eliminate one of them. Finding witnesses is a costly operation in a compressed text, thus the importance of witness-free dueling.
AB - Recent proliferation of digitized data and the unprecedented growth in the volume of stored and transmitted data motivated the definition of the compressed matching paradigm. This is the problem of efficiently finding a pattern P in a compressed text T without the need to decompress. We present the first optimal two-dimensional compressed matching algorithm. The compression under consideration is the two dimensional run-length compression, used by FAX transmission. We achieve optimal time by proving new properties of two-dimensional periodicity. This enables performing duels in which no witness is required. At the heart of the dueling idea lies the concept that two overlapping occurrences of a pattern in a text can use the content of a predetermined text position or witness in the overlap to eliminate one of them. Finding witnesses is a costly operation in a compressed text, thus the importance of witness-free dueling.
UR - http://www.scopus.com/inward/record.url?scp=0037760922&partnerID=8YFLogxK
U2 - 10.1006/jagm.1997.0860
DO - 10.1006/jagm.1997.0860
M3 - Article
AN - SCOPUS:0037760922
SN - 0196-6774
VL - 24
SP - 354
EP - 379
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 2
ER -