Paper Info
Title
An efficient pattern matching scheme in LZW compressed sequences
Abstract
Compressed pattern matching (CPM) is an emerging research field addressing the problem: given a compressed sequence and a pattern, process the sequence with minimal (or no) decompression to find the pattern occurrence(s) in the uncompressed sequence. It can be applied to detect malwares and confidential information leakage in compressed files directly. In this paper, we report our work of CPM in Lempel-Ziv-Welch (LZW) compressed sequences. We propose an efficient bitmap-based realization of the Amir-Benson-Farach algorithm. We also generalize the algorithm to find all pattern occurrences and report their absolute positions in the uncompressed sequence. Experiments are conducted to test the space requirements of our proposed generalization and two related CPM schemes which can also be realized with bitmaps. Results show that our proposed generalization requires the least amount of storage for moderate and long patterns. We also conduct experiments to compare the throughput performance of our proposed generalization with these two related CPM schemes and the decompress-then-search scheme. Results show that our proposed generalization outperforms the decompress-then-search scheme significantly. When scanning a file with pattern occurrences, our proposed generalization performs slightly better than the two related CPM schemes. The difference is significant when scanning a file with no pattern occurrence. Copyright (c) 2008 John Wiley & Sons, Ltd.
Year
DOI
Venue
2008
10.1002/sec.32
SECURITY AND COMMUNICATION NETWORKS
Keywords
Field
DocType
bit-parallelism,compressed pattern matching,information search and retrieval,LZW compression,malwares detection,string matching
Compressed pattern matching,String searching algorithm,Space requirements,Computer science,Algorithm,Bit parallelism,Throughput,Bitmap,Pattern matching,Uncompressed video
Journal
Volume
Issue
ISSN
1
4
1939-0114
Citations 
PageRank 
References 
0
0.34
8
Authors
2
Name
Order
Citations
PageRank
Tsern-Huei Lee124430.63
Nai-Lun Huang251.48