首页|Multiple pattern matching in LZW compressed text
Multiple pattern matching in LZW compressed text
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NETL
IEEE
We address the problem of searching in LZW compressed text directly， and present a new algorithm for finding multiple patterns by simulating the move of the Aho-Corasick (1975) pattern matching machine。 The new algorithm finds all occurrences of multiple patterns whereas the algorithm proposed by Amir， Benson， and Farach (see Journal of Computer and System Sciences， vol。52， p。299-307， 1996) finds only the first occurrence of a single pattern。 The new algorithm runs in O(n+m/sup 2/+r/sub a/) time using O(n+m/sup 2/) space， where n is the length of the compressed text， m is the length of the total length of the patterns， and r is the number of occurrences of the patterns。 We implemented a simple version of the algorithm， and showed that it is approximately twice faster than a decompression followed by a search using the Aho-Corasick machine。
Pattern matching
T. Kida、M. Takeda、A. Shinohara、M. Miyazaki、S. Arikawa
展开 >
Dept. of Inf., Kyushu Univ., Fukuoka, Japan
Data Compression Conference, 1998. DCC '98. Proceedings
NETL
IEEE
