跳到主要內容

臺灣博碩士論文加值系統

(35.175.191.36) 您好!臺灣時間:2021/07/31 00:56
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:邱登煌
論文名稱:壓縮檔案的字樣比對
論文名稱(外文):Pattern Matching in Compressed Files
指導教授:李程輝
學位類別:碩士
校院名稱:國立交通大學
系所名稱:電信工程系所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:35
中文關鍵詞:字樣比對壓縮
外文關鍵詞:pattern matching
相關次數:
  • 被引用被引用:0
  • 點閱點閱:109
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
字樣比對是一門重要的技術,可以在檔案中搜尋特定的內容,我們可以將它應用在病毒掃描和資料檢索上。隨著資料壓縮的使用變得愈來愈普遍,對壓縮檔案進行字樣比對是無可避免的,針對這種情況,我們必須提供有效的方法來提升比對的效率。在這篇論文中,我們針對病毒掃描和資料檢索於壓縮檔案上的應用,提出能夠提升比對效率的方法。我們提出可以對gzip壓縮檔案進行串流掃描的機制,當封包陸續到達閘道口時,對它們進行即時地掃描。另外,我們提出可以在不解壓縮的情況下,對LZW壓縮檔案進行正規表示式比對的機制,在短字樣的比對上,具有比解壓縮後再比對更好的效率,我們可以將這個機制應用在資料檢索系統上。
Pattern matching is an important technique and it can be use to search specific contents in the files. We can apply pattern matching to virus detection and information retrieval. As data compression becomes more and more popular, the use of pattern matching in compressed files is avoidless, we must provide available approaches to improve the efficiency of search for this situation. This thesis presents the approaches for the applications of virus detection and information retrieval in compressed files to improve the efficiency. We propose the scheme of stream-based scanning in gzip compressed files, when packets arrive at Gateway continually, we can scan them immediately. Besides, we present the scheme of pattern matching for regular expression in LZW files with no decompression and it has better efficiency than decompress and then search in short patterns. We can apply the scheme to information retrieval system.
第一章 簡介 1
1.1 研究背景 1
1.2 研究動機 2
第二章 字樣比對演算法 4
2.1 Aho-Corasick演算法 4
2.2 Glushkov automaton 6
第三章 資料壓縮演算法 10
3.1 LZ77演算法 10
3.2 Gzip演算法 13
3.2.1 檔案格式 13
3.2.2 Huffman編碼 14
3.2.3 區塊格式 15
3.3 LZW演算法 19
第四章 應用於gzip壓縮檔案之串流字樣比對機制 22
4.1 Gzip解壓縮 22
4.2 串流解壓縮 23
4.3 串流字樣比對 25
第五章 應用於LZW壓縮檔案之正規表示式比對機制 28
5.1以位元映像實現DFA 28
5.2應用於LZW壓縮檔案之正規表示式比對機制 29
5.3模擬結果 31
第六章 結論 33
參考文獻 34
[1] D. E. Knuth, J. H. Morris, and V. R. Pratt, “Fast pattern matching in strings,” TR CS-74-440, Stanford University, Stanford, California, 1974.

[2] R. S. Boyer and J. S. Moore, “A fast string searching algorithm,” Communications of the ACM, Vol. 20, pp. 762-772, October 1977.

[3] A. V. Aho and M. J. Corasick, “Efficient string matching: an aid to bibliographic search,” Communications of the ACM, Vol. 18, pp. 333-340, June 1975.

[4] J. Ziv. and A. Lempel, “A universal algorithm for sequential data compression,” IEEE Trans. Inf. Theory, 23: 337-343, 1977.

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

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

[7] K. Thompson, “Regular expression search algorithm,” CACM, 11(6): 419-422, 1968.
[8] V. M. Glushkov, “The abstract theory of automaton,” Russian Mathematical Surveys, 16: 1-53, 1961.

[9] G. Navarro and M. Raffinot, “Compact DFA Representation for Fast Regular Expression Search,” In Proceedings of the 5th Workshop on Algorithm Engineering (WAE'01), LNCS 2141, pp. 1-12, 2001.

[10] RFC1952 – GZIP file format specification version 4.3.

[11] RFC1951 – DEFLATE Compression Data Format Specification version 1.3.

[12] J. Ziv. and A. Lempel, “Compression of individual Sequences via Variable-Rate Coding,” IEEE Trans. Inf. Theory, Vol. 24, 1978.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top