Multiple-Pattern Matching In LZW Compressed Files Using Aho-Corasick Algorithm

Compressed pattern matching is an emerging research area that aims in searching patterns efficiently in the compressed files with minimal (or no) decompression. In this paper, we report our work on multiple-pattern matching in LZW compressed files using Aho-Corasick algorithm. The algorithm takes O(mt+n+r) time with O(mt) extra space, where n is the size of the compressed file, m is the size of the pattern length, t is the size of the LZW trie and r is the number of occurrences of the patterns. Extensive experiments have been conducted to test the performance of our algorithms. The results showed that our multiple-pattern matching algorithm is practically the fastest among all approaches when the number of patterns is not very large. Therefore, our algorithm is preferable for general string matching applications. The proposed algorithm is efficient for large files and it is particularly efficient when being applied on archival search if the archives are compressed with a common LZW trie.