臺灣博碩士論文加值系統

壓縮字串比對(CPM; compressed pattern matching)乃一新興之研究領域，著眼於此類問題：給定一壓縮序列及一字串，在最少量之解壓縮作用（或無解壓縮作用）下，於序列中尋找字串的出現(pattern occurrences)。可應用於直接在壓縮檔案中做電腦病毒及機密資訊外洩漏與否的偵查。LZW為一廣受應用且壓縮效率高的壓縮演算法，本論文即記述了我們在壓縮字串比對上，對於處理LZW壓縮序列的研究成果。著名的Amir-Benson-Farach演算法是最早能在LZW壓縮序列中尋得字串的首次出現位置的演算法，我們針對此演算法提出一以位元串映像為基礎的(bitmap-based)實現方式，同時亦將其推廣為可尋得所有的字串出現，並回報它們在序列未壓縮前所處的絕對位置。程式模擬結果顯示，相較於解壓縮後再於解開之序列中搜尋的機制，我們採用的機制具有較高的時間效能；而相較於另一套同樣以位元串映像實現的壓縮字串比對演算法──Navarro-Raffinot機制，我們的機制對於中等長度以上的字串，在所需的記憶體空間上，是較為節省的。

Compressed pattern matching (CPM) is an emerging research field addressing the problem: Given a compressed sequence and a pattern, find the pattern occurrence(s) in the (uncompressed) sequence with minimal (or no) decompression. It can be applied to detection of computer virus and confidential information leakage in compressed files directly. In this thesis, we report our work of CPM in LZW compressed sequences. LZW is one of the most effective compression algorithms used extensively. We propose a simple bitmap-based realization of the well-known　 Amir-Benson-Farach algorithm. We also generalize the algorithm to find all pattern occurrences (rather than just the first one) and to report their absolute positions in the uncompressed sequence. Experiments are conducted to compare the performance of our proposed generalization with the decompress-then-search scheme. We found that our proposed generalization is much faster than the decompress-then-search scheme. The memory space requirement of our proposed generalization is compared with that of the Navarro-Raffinot scheme, an alternative CPM algorithm which can also be realized with bitmaps. Results show that our proposed generalization has better space performance than the Navarro-Raffinot scheme for moderate and long patterns.

中文摘要 i

English Abstract ii

誌謝 iii

Contents iv

List of Tables v

List of Figures vi

Chapter 1 Introduction 1

Chapter 2 Background 4

2.1 The LZW Compression Algorithm 　　　　 4

2.2 The Amir-Benson-Farach Algorithm 5

Chapter 3 An Efficient Pattern Matching Scheme in LZW Compressed Sequences 11

3.1 An Efficient Realization of Amir-Benson-Farach Algorithm 11

3.2 Generalization to All Pattern Occurrences 16

Chapter 4 Related Work 24

Chapter 5 Comparison and Experimental Results 28

Chapter 6 Conclusion 34

Bibliographies 35

[1] Welch, T.A.: ‘A technique for High-Performance Data Compression’, June 1984, IEEE Computer, 17(6): 8-19

[2] Amir, A., Benson, G., and Farach, M.: ‘Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files’, April 1996, Journal of Computer and System Sciences, vol. 52, pp. 299-307

[3] Tao, T., and Mukherjee, A.: ‘Pattern Matching in LZW Compressed Files’, August 2005, IEEE Transactions on Computers, vol. 54, no. 8, pp. 929-938

[4] Ho, M.H., and Yen, H.C.: ‘A Dictionary-based Compressed Pattern Matching Algorithm’, IEEE Proceedings of the 26th Annual International Computer Software and Applications Conference, Oxford, England, August 2002, pp. 873-878

[5] Navarro G., and Raffinot, M.: ‘A General Practical Approach to Pattern Matching over Ziv-Lempel Compressed Text’, Proc. 10th Ann. Symp. on Combinatorial Pattern Matching, Springer-Verlag, London, UK, 1999, Lecture Notes in Computer Science, vol. 1645, pp. 14-36

[6] Kida, T., Takeda, M., Shinohara, A., and Arikawa, S.: ‘Shift-And Approach to Pattern Matching in LZW Compressed Text’, Proc. 10th Ann. Symp. on Combinatorial Pattern Matching, Springer-Verlag, London, UK, 1999, Lecture Notes in Computer Science, vol. 1645, pp. 1–13

[7] Kida, T., Takeda, M., Shinohara, A., Miyazaki, M., and Arikawa, S.: ‘Multiple Pattern Matching in LZW Compressed Text’, 2000, J. Discrete Algorithms, vol. 1, no. 1, pp. 133-158

[8] Knuth, D.E., Morris, J.H., and Pratt, V.R.: ‘Fast Pattern Matching in Strings’, 1977, SIAM Journal on Computing, 6, (2), pp.323-350