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

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

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

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

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