字典壓縮算法是利用許多數(shù)據(jù)類型都含有重復(fù)的代碼序列這一特性。在文本文件中其代碼字代表字符，而在光柵圖像中代碼字代表象素。在編碼時將有霞復(fù)的內(nèi)容一次性地記錄在一個數(shù)據(jù)串表中，這個表就仿佛是字典，當(dāng)譯碼是利用指針號或索引號就可以找到原輸入數(shù)據(jù)流中相應(yīng)的內(nèi)容，LZ的幾種算法都屬于基于字典的壓縮算法。

基于字典壓縮算法的分類

1、LZ77、LZSS算法

LZ77、LZSS算法的思想是：在數(shù)據(jù)壓縮過程中。尋找當(dāng)前等待進行壓縮處理的數(shù)據(jù)串中是否在已經(jīng)處理過的數(shù)據(jù)串中出現(xiàn)過，如果確實曾經(jīng)出現(xiàn)過，則利用指向該已經(jīng)進行處理數(shù)據(jù)串的指針代替當(dāng)前等待進行壓縮的數(shù)據(jù)串。

2、LZ78、LZW算法

（1）編碼算法

LZw編碼是圍繞稱為詞典的轉(zhuǎn)換表來完成的。這張轉(zhuǎn)換表用來存放稱為前綴的字符序列，并且為每個表項分配一個碼字。LZW編碼器使用了一種很實用的分析算法，稱為貪婪分析算法。在貪婪分析算法中，每一次分析都要串行地檢查來自字符流的字符串，從中分解出已經(jīng)識別的最長的字符串，也就是已經(jīng)在詞典中出現(xiàn)的最長的前綴。用已知的前綴加上下一個輸入字符ｃ也就是當(dāng)前字符作為該前綴的擴展字符，形成新的擴展字符串綴一符串：Prefix.c.這個新的綴一符串是否要加到詞典中，還要看詞典中是否存有和它相同的綴一符串String。如果有，那么這個綴一符串就變成前綴（Prefix），繼續(xù)輸入新的字符，否則就把這個綴一符串寫到詞典中生成一個新的前綴（Prefix），并給一個代碼。

（2）譯碼算法

LZW譯碼算法中還用到另外兩個術(shù)語：①當(dāng)前碼字：指當(dāng)前正在處理的碼字，用cw表示，用String.cw表示當(dāng)前綴一符串；②先前碼字：指先于當(dāng)前碼字的碼字，用ｐｗ表示。用String.pw表示先前綴一符串。LZW譯碼算法開始時，譯碼詞典與編碼詞典相同，它包含所有可能的前綴根（rotts）。Ｌｚｗ算法在譯碼過程中會記住先前碼字（ｐｗ）。從碼字流中讀當(dāng)前碼字String.cw之后輸出當(dāng)前綴一符串，然后把用String.cw的第一個字符擴展的先前綴一符串String.cw添加到詞典中。

改進的U州算法

1、實現(xiàn)零搜索

如何才能使根據(jù)字頭碼和字尾碼建立的索引值不重復(fù)，其辦法是以其本身的值合成內(nèi)存地址，依靠指針進行定位，從而不再需要查找過程。在32位操作系統(tǒng)下，其尋址能力可達4GB，再加上硬件設(shè)施大大提高，物理內(nèi)存空間一般達到了128G，技術(shù)上虛擬內(nèi)存町達4GB，使得上述方法成為可能。

2、動態(tài)編碼

使用動態(tài)編碼長度進一步提高了算法效率。這種方法允許壓縮代碼長度的更改，即利用不固定長度的代碼存儲壓縮數(shù)據(jù)。LZW算法一般從9位開始編碼，這時存儲代碼也是9位，直到編碼增加到10位時，存儲代碼才增加到10位。傳統(tǒng)的Lzw算法是直接存儲最人編碼位的，這樣做導(dǎo)致非編碼數(shù)據(jù)也要存儲這樣大的位數(shù)，浪費了完全沒有用處的幾個高位。

編碼流程圈

由以上幾個例子可以看出本壓縮算法對一些常用的文件格式如：記事本，word，ppt，圖片以及一些應(yīng)用程序等都能進行準(zhǔn)確的壓縮與解壓縮，并具都比原來的LZW算法壓縮率要高。同時也發(fā)現(xiàn)，對于文本類文件，壓縮速度比較快，而且壓縮比比較高，對于圖片來講，該壓縮效果算法效果不是很好。

cc

收藏 海報分享