Multiple-pattern matching for LZW compressed files
Tao Tao, Amar Mukherjee · 2005
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 total size of all patterns, 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 show 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.