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

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

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

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

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