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 -