TY - GEN

T1 - Shift-and approach to pattern matching in LZW compressed text

AU - Kida, Takuya

AU - Takeda, Masayuki

AU - Shinohara, Ayumi

AU - Arikawa, Setsuo

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.

PY - 1999

Y1 - 1999

N2 - This paper considers the Shift-And approach to the problem of pattern matching in LZW compressed text, and gives a new algorithm that solves it. The algorithm is indeed fast when a pattern length is at most 32, or the word length. After an O(m +| Σ|) time and O(| Σ|) space preprocessing of a pattern, it scans an LZW compressed text in O(n + r) time and reports all occurrences of the pattern, where n is the compressed text length, m is the pattern length, and r is the number of the pattern occurrences. Experimental results show that it runs approxi- mately 1.5 times faster than a decompression followed by a simple search using the Shift-And algorithm. Moreover, the algorithm can be extended to the generalized pattern matching, to the pattern matching with k mismatches, and to the multiple pattern matching, like the Shift-And algorithm..

AB - This paper considers the Shift-And approach to the problem of pattern matching in LZW compressed text, and gives a new algorithm that solves it. The algorithm is indeed fast when a pattern length is at most 32, or the word length. After an O(m +| Σ|) time and O(| Σ|) space preprocessing of a pattern, it scans an LZW compressed text in O(n + r) time and reports all occurrences of the pattern, where n is the compressed text length, m is the pattern length, and r is the number of the pattern occurrences. Experimental results show that it runs approxi- mately 1.5 times faster than a decompression followed by a simple search using the Shift-And algorithm. Moreover, the algorithm can be extended to the generalized pattern matching, to the pattern matching with k mismatches, and to the multiple pattern matching, like the Shift-And algorithm..

UR - http://www.scopus.com/inward/record.url?scp=84957655641&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84957655641&partnerID=8YFLogxK

U2 - 10.1007/3-540-48452-3_1

DO - 10.1007/3-540-48452-3_1

M3 - Conference contribution

AN - SCOPUS:84957655641

SN - 3540662782

SN - 9783540662785

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 13

BT - Combinatorial Pattern Matching - 10th Annual Symposium, CPM 1999, Proceedings

A2 - Paterson, Mike

A2 - Crochemore, Maxime

PB - Springer Verlag

T2 - 10th Annual Symposium on Combinatorial Pattern Matching, CPM 1999

Y2 - 22 July 1999 through 24 July 1999

ER -