基于動(dòng)態(tài)詞典的文本壓縮研究.pdf

1、近年來(lái)，數(shù)據(jù)壓縮的理論得到了相當(dāng)充分的發(fā)展，相關(guān)的產(chǎn)品在各個(gè)領(lǐng)域被廣泛應(yīng)用。從數(shù)據(jù)還原的角度來(lái)看，數(shù)據(jù)壓縮可以分為有損壓縮和無(wú)損壓縮兩大領(lǐng)域…。 本文的壓縮研究屬于無(wú)損壓縮領(lǐng)域。在第一章中，對(duì)無(wú)損壓縮領(lǐng)域中基于統(tǒng)計(jì)和基于字典的兩大主流方法進(jìn)行了回顧，并闡述了其中主要壓縮方法的原理和特點(diǎn)，指出了其適用范圍和局限性。本文進(jìn)一步從基于字典的壓縮方法出發(fā)，針對(duì)相關(guān)字典內(nèi)容的特點(diǎn)進(jìn)行了具體分析：一般基于字典壓縮方法中的字典，僅與源碼流的字

2、符順序相關(guān)，而不與其具體內(nèi)容的意義相關(guān)。本文著重針對(duì)文本文件尤其是中文文本文件進(jìn)行了分析，指出文本文件的字符比一般文件的字符有更強(qiáng)的關(guān)聯(lián)性，字符之間的搭配也有較強(qiáng)的穩(wěn)定性。據(jù)此，本文在壓縮方法中建立了內(nèi)容關(guān)聯(lián)性較強(qiáng)的詞典，而不是一般的字典，并提出了一種嶄新的數(shù)據(jù)壓縮方法一動(dòng)態(tài)詞典壓縮法。 動(dòng)態(tài)詞典壓縮法，克服了傳統(tǒng)字典壓縮方法的某些不足。傳統(tǒng)的字典壓縮方法中，當(dāng)字典飽和或壓縮率降低時(shí)，要么保持字典不變繼續(xù)使用，要么將字典完全廢棄

3、[2]。此時(shí)的字典或不能很好的反映歷史數(shù)據(jù)特點(diǎn)，或不能反應(yīng)現(xiàn)實(shí)數(shù)據(jù)特點(diǎn)，不能發(fā)揮它的最大作用，字典的管理存在明顯的局限性。本文的動(dòng)態(tài)詞典由保持獨(dú)立的詞典單元組成。在壓縮和解壓過(guò)程中，使用散列法對(duì)詞典單元進(jìn)行定位，并使用線性搜索查找詞典單元的內(nèi)容，使對(duì)整個(gè)字典的操作能很快進(jìn)行。同時(shí)，本文對(duì)詞典的管理采用了一種全新的方法一沖突率法，并用沖突率對(duì)詞典單元的有效性進(jìn)行及時(shí)檢查。當(dāng)沖突率超過(guò)某一設(shè)定值時(shí)，本詞典單元立即廢棄不用并需重新建立，但其它

4、的單元保持不變，這樣既能使符合要求的詞典單元保留下來(lái)繼續(xù)使用，又能將不滿足條件的詞典單元及時(shí)廢棄，從而保證整個(gè)字典的高效性。本文把這種及時(shí)更新內(nèi)容的詞典稱為動(dòng)態(tài)詞典，由此建立的壓縮法稱為動(dòng)態(tài)詞典壓縮法，并簡(jiǎn)稱為“QQQ。 詞典重用法是本文采取的另一種重要方法，它主要用于對(duì)文件夾進(jìn)行詞典的高效管理。一般而言，處于文件夾中的文件在內(nèi)容方面有較強(qiáng)的關(guān)聯(lián)性，因而建立的詞典也應(yīng)有相似的部分。為了進(jìn)一步體現(xiàn)動(dòng)態(tài)詞典的高效性，本文不是為每一個(gè)