Title

Multiple-Pattern Matching For Lzw Compressed Files

Abstract

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. © 2005 IEEE.

Publication Date

9-21-2005

Publication Title

International Conference on Information Technology: Coding and Computing, ITCC

Volume

1

Number of Pages

91-96

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

Socpus ID

24744452611 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/24744452611

This document is currently not available here.

Share

COinS