基于多模式匹配的數(shù)據(jù)壓縮算法研究.pdf

1、近年來,日常需要處理和傳輸?shù)臄?shù)據(jù)越來越多,數(shù)據(jù)壓縮也變得越來越重要,而其中文本是數(shù)據(jù)的一個重要組成部分,因此對文本數(shù)據(jù)的壓縮研究就成為了壓縮領(lǐng)域研究的一個重點?；谧值涞膲嚎s算法是文本壓縮的一種典型的算法,對其展開研究對文本數(shù)據(jù)的壓縮有著十分重要的意義。本文在對基于字典的壓縮算法分析的基礎(chǔ)上,選擇LZSS算法展開了研究,主要工作如下:
　　 首先,為了提高文件的壓縮率,對文本文件的無損壓縮進行了研究,回顧了經(jīng)典的無損壓縮算法,并

2、闡述了主要壓縮方法的原理和特點。實現(xiàn)了三種基于字典的經(jīng)典壓縮算法并在此基礎(chǔ)上進行了分析。LZSS算法是LZ77算法的改進,壓縮率雖然不高,但因其算法簡單、解壓速度快,在實際應(yīng)用中得到了廣泛的認可。因此選擇了LZSS算法進行研究,目的是在保持高解壓速度的基礎(chǔ)上進一步提高其壓縮率。
　　 其次,在LZSS的基礎(chǔ)上,本文進一步利用目前流行的多模式匹配算法——Wu-Manber算法,改進了字符串匹配的過程,提出了一種新的算法——WM_L

3、ZSS算法。
　　 算法的基本思想是利用文本的最近相關(guān)性,針對LZSS算法在壓縮過程中存在查找回溯的問題,采用多級匹配、Hash散列和跳躍查找的思想,使用多模式匹配技術(shù)在更大范圍內(nèi)進行查找。一次針對多個模式進行匹配,避免了不必要的匹配,加速了匹配的過程,有利于查找到更長的匹配信息,獲得更高的壓縮率。
　　 本文詳細介紹了基于多模式匹配的壓縮算法的核心過程。即利用每一次匹配的結(jié)果,動態(tài)建立shift表和hash表,得到模式

4、庫。然后,從文件中讀取固定大小的數(shù)據(jù)塊,進行多模式匹配預(yù)處理,針對模式庫中的所有的模式進行查找,得到匹配數(shù)據(jù)(其中包括匹配位置和匹配長度等)。利用得到的匹配數(shù)據(jù)輸出編碼并完善樹結(jié)構(gòu)。
　　 最后,選取了通用的文本壓縮測試文件作為測試數(shù)據(jù),從文件的類型、文件的大小、最小模式大小的選擇等方面對壓縮率進行了充分的測試,并與相關(guān)的壓縮算法進行了橫向比較。實驗證明,改進后算法的壓縮率有了較明顯的提高,同時該算法還具有解壓快速、算法簡單的特