1、標準的LZW壓縮原理： 先來解釋一下幾個基本概念： LZW壓縮有三個重要的對象：數(shù)據流(CharStream)、編碼流(CodeStream)和編譯 表(String Table)。在編碼時，數(shù)據流是輸入對象（圖象的光柵數(shù)據序列），編碼流 就是輸出對象（經過壓縮運算的編碼數(shù)據）；在解碼時，編碼流則是輸入對象，數(shù)據 流是輸出對象；而編譯表是在編碼和解碼時都須要用借助的對象。 字符(Character)：最基礎的數(shù)據元素，在文本文件中就是一個字節(jié)，在光柵數(shù)據中就 是一個像素的顏色在指定的顏色列表中的索引值； 字符串(String)：由幾個連續(xù)的字符組成； 前綴(Prefix)：也是一個字符串，不過

2、通常用在另一個字符的前面，而且它的長度可以為0； 根(Root)：單個長度的字符串； 編碼(Code)：一個數(shù)字，按照固定長度（編碼長度）從編碼流中取出，編譯表的映射值； 圖案：一個字符串，按不定長度從數(shù)據流中讀出,映射到編譯表條目. LZW壓縮的原理：提取原始圖象數(shù)據中的不同圖案，基于這些圖案創(chuàng)建一個編譯表， 然后用編譯表中的圖案索引來替代原始光柵數(shù)據中的相應圖案，減少原始數(shù)據大小?？?起來和調色板圖象的實現(xiàn)原理差不多，但是應該注意到的是，我們這里的編譯表不是事 先創(chuàng)建好的，而是根據原始圖象數(shù)據動態(tài)創(chuàng)建的，解碼時還要從已編碼的數(shù)據中還原出 原來的編譯表（GIF文件中是不攜帶編譯表信息的），為

3、了更好理解編解碼原理，我們 來看看具體的處理過程： 編碼器(Compressor) 編碼數(shù)據，第一步，初始化一個編譯表，假設這個編譯表的大小是12位的，也就是最 多有4096個單位，另外假設我們有32個不同的字符（也可以認為圖象的每個像素最多有32 種顏色），表示為a，b，c，d，e.，初始化編譯表：第0項為a，第1項為b，第2項為c. 一直到第31項，我們把這32項就稱為根。 開始編譯，先定義一個前綴對象Current Prefix，記為.c.，現(xiàn)在它是空的，然后 定義一個當前字符串Current String，標記為.c.k，.c.就為Current Prefix，k就 為當前讀取字符?，F(xiàn)

4、在來讀取數(shù)據流的第一個字符，假如為p，那么Current String就等 于.c.p（由于.c.為空，實際上值就等于p），現(xiàn)在在編譯表中查找有沒有Current String的值，由于p就是一個根字符，我們已經初始了32個根索引，當然可以找到，把p 設為Current Prefix的值，不做任何事繼續(xù)讀取下一個字符，假設為q，Current String 就等于.c.q（也就是pq），看看在編譯表中有沒有該值，當然。沒有，這時我們要做下 面的事情：將Current String的值（也就是pq）添加到編譯表的第32項，把Current Prefix 的值（也就是p）在編譯表中的索引輸出到編碼

5、流，修改Current Prefix為當前讀取的字符 （也就是q）。繼續(xù)往下讀，如果在編譯表中可以查找到Current String的值(.c.k)， 則把Current String的值(.c.k)賦予Current Prefix；如果查找不到，則添加Current String的值(.c.k)到編譯表，把Current Prefix的值(.c.)在編譯表中所對應的索引 輸出到編碼流，同時修改Current Prefix為k ，這樣一直循環(huán)下去直到數(shù)據流結束。偽代 碼看起來就像下面這樣： 編碼器偽代碼 Initialize String Table; .c. = Empty; .c.k =

6、First Character in CharStream; while (.c.k != EOF ) if ( .c.k is in the StringTable) .c. = .c.k; else add .c.k to the StringTable; Output the Index of .c. in the StringTable to the CodeStream; .c. = k; .c.k = Next Character in CharStream; Output the Index of .c. in the StringTable to the CodeStream;

7、 來看一個具體的例子,我們有一個字母表a，b，c，d.有一個輸入的字符流abacaba。 現(xiàn)在來初始化編譯表：#0=a,#1=b,#2=c,#3=d.現(xiàn)在開始讀取第一個字符a，.c.a=a， 可以在在編譯表中找到，修改.c.=a;不做任何事繼續(xù)讀取第二個字符b，.c.b=ab， 在編譯表中不能找，那么添加.c.b到編譯表：#4=ab，同時輸出.c.（也就是a）的 索引#0到編碼流，修改.c.=b；讀下一個字符a，.c.a=ba，在編譯表中不能找到： 添加編譯表#5=ba，輸出.c.的索引#1到編碼流，修改.c.=a；讀下一個字符c， .c.c=ac，在編譯表中不能找到：添加編譯表#6=ac，輸

8、出.c.的索引#0到編碼流， 修改.c.=c；讀下一個字符a，.c.c=ca，在編譯表中不能找到：添加編譯表#7=ca， 輸出.c.的索引#2到編碼流，修改.c.=a；讀下一個字符b，.c.b=ab，編譯表的 #4=ab，修改.c.=ab；讀取最后一個字符a，.c.a=aba，在編譯表中不能找到： 添加編譯表#8=aba，輸出.c.的索引#4到編碼流，修改.c.=a；好了，現(xiàn)在沒有數(shù) 據了，輸出.c.的值a的索引#0到編碼流，這樣最后的輸出結果就是：#0#1#0#2#4#0. 解碼器(Decompressor) 好了，現(xiàn)在來看看解碼數(shù)據。數(shù)據的解碼，其實就是數(shù)據編碼的逆向過程，要從 已經編譯的

9、數(shù)據（編碼流）中找出編譯表，然后對照編譯表還原圖象的光柵數(shù)據。 首先，還是要初始化編譯表。GIF文件的圖象數(shù)據的第一個字節(jié)存儲的就是LZW編 碼的編碼大?。ㄒ话愕扔趫D象的位數(shù)），根據編碼大小，初始化編譯表的根條目（從 0到2的編碼大小次方），然后定義一個當前編碼Current Code，記作code，定義一 個Old Code，記作old。讀取第一個編碼到code，這是一個根編碼，在編譯表中可 以找到，把該編碼所對應的字符輸出到數(shù)據流，old=code；讀取下一個編碼到 code，這就有兩種情況：在編譯表中有或沒有該編碼，我們先來看第一種情況：先 輸出當前編碼code所對應的字符串到數(shù)據流，然

10、后把old所對應的字符（串）當成 前綴prefix .，當前編碼code所對應的字符串的第一個字符當成k，組合起來當 前字符串Current String就為.k，把.k添加到編譯表，修改old=code， 讀下一個編碼；我們來看看在編譯表中找不到該編碼的情況，回想一下編碼情況：如 果數(shù)據流中有一個p.p.pq這樣的字符串，p.在編譯表中而p.p不在， 編譯器將輸出p.的索引而添加p.p到編譯表，下一個字符串p.p就可以在 編譯表中找到了，而p.pq不在編譯表中，同樣將輸出p.p的索引值而添加 p.pq到編譯表，這樣看來，解碼器總比編碼器慢一步，當我們遇到p.p所 對應的索引時，我們不知到該索

11、引對應的字符串（在解碼器的編譯表中還沒有該索引， 事實上，這個索引將在下一步添加），這時需要用猜測法：現(xiàn)在假設上面的p.所 對應的索引值是#58，那么上面的字符串經過編譯之后是#58#59，我們在解碼器中讀 到#59時，編譯表的最大索引只有#58，#59所對應的字符串就等于#58所對應的字符串 (也就是p.)加上這個字符串的第一個字符(也就是p)，也就是p.p。事實上， 這種猜測法是很準確（有點不好理解，仔細想一想吧）。上面的解碼過程用偽代碼表 示就像下面這樣： 解碼器偽代碼 Initialize String Table; code = First Code in the CodeStrea

12、m; Output the String for code to the CharStream; old = code; code = Next Code in the CodeStream; while (code != EOF ) if ( code is in the StringTable) Output the String for code to the CharStream; / 輸出code所對應的字符串 . = translation for old; / old所對應的字符串 k = first character of translation for code; / co

13、de所對應的字符串的第一個字符 add .k to the StringTable; old = code; else . = translation for old; k = first character of .; Output .k to CharStream; add .k to the StringTable; old = code; code = Next Code in the CodeStream; 詞典編碼詞典編碼主要利用數(shù)據本身包含許多重復的字符串的特性.例如:吃葡萄不吐葡萄皮,不吃葡萄倒吐葡萄皮. 我們如果用一些簡單的代號代替這些字符串,就可以實現(xiàn)壓縮,實際上就是利用了

14、信源符號之間的相關性.字符串與代號的對應表就是詞典. 實用的詞典編碼算法的核心就是如何動態(tài)地形成詞典,以及如何選擇輸出格式以減小冗余. 第一類詞典編碼第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據中出現(xiàn)過,然后用已經出現(xiàn)過的字符串替代重復的部分,它的輸出僅僅是指向早期出現(xiàn)過的字符串的指針. LZ77算法 LZ77 算法在某種意義上又可以稱為滑動窗口壓縮,該算法將一個虛擬的,可以跟隨壓縮進程滑動的窗口作為詞典,要壓縮的字符串如果在該窗口中出現(xiàn),則輸出其出現(xiàn)位置和長度.使用固定大小窗口進行詞語匹配,而不是在所有已經編碼的信息中匹配,是因為匹配算法的時間消耗往往很多,必須限制詞典

15、的大小才能保證算法的效率;隨著壓縮的進程滑動詞典窗口,使其中總包含最近編碼過的信息,是因為對大多數(shù)信息而言,要編碼的字符串往往在最近的上下文中更容易找到匹配串. LZ77編碼的基本流程 1,從當前壓縮位置開始,考察未編碼的數(shù)據,并試圖在滑動窗口中找出最長的匹配字符串,如果找到,則進行步驟 2,否則進行步驟 3. 2,輸出三元符號組 ( off, len, c ).其中 off 為窗口中匹配字符串相對窗口邊界的偏移,len 為可匹配的長度,c 為下一個字符,即不匹配的第一個字符.然后將窗口向后滑動 len + 1 個字符,繼續(xù)步驟 1. 3,輸出三元符號組 ( 0, 0, c ).其中 c 為下

16、一個字符.然后將窗口向后滑動 1 個字符,繼續(xù)步驟 1. LZ77算法 LZ77編碼舉例 C A B A B B C B A A 5, 3, A ABC 7 5 2, 1, B B 5 4 0, 0, C - 4 3 1, 1, B A 2 2 0, 0, A - 1 1 輸出匹配串位置步驟 LZSS算法 LZ77通過輸出真實字符解決了在窗口中出現(xiàn)沒有匹配串的問題,但這個解決方案包含有冗余信息.冗余信息表現(xiàn)在兩個方面,一是空指針,二是編碼器可能輸出額外的字符,這種字符是指可能包含在下一個匹配串中的字符. LZSS算法的思想是如果匹配串的長度比指針本身的長度長就輸出指針(匹配串長度大于等于MIN

17、_LENGTH),否則就輸出真實字符.另外要輸出額外的標志位區(qū)分是指針還是字符. LZSS編碼的基本流程 1,從當前壓縮位置開始,考察未編碼的字符,并試圖在滑動窗口中找出最長的匹配字符串,如果匹配串長度len大于等于最小匹配串長度(len = MIN_LENGTH),則進行步驟 2,否則進行步驟 3. 2,輸出指針二元組 ( off, len).其中 off 為窗口中匹配字符串相對窗口邊界的偏移,len 為匹配串的長度,然后將窗口向后滑動 len 個字符,繼續(xù)步驟 1. 3,輸出當前字符c,然后將窗口向后滑動 1 個字符,繼續(xù)步驟 1. LZSS編碼舉例 C B A A B B C B B A

18、 A 字符 11 10 9 8 7 6 5 4 3 2 1 位置 C C 11 8 (7,3) AAB 8 7 (3,2) BB 6 6 C - 5 5 B B 4 4 B - 3 3 A A 2 2 A - 1 1 輸出匹配串位置步驟輸入數(shù)據流: 編碼過程 MIN_LEN =2 LZSS算法在相同的計算機環(huán)境下,LZSS算法比LZ77可獲得比較高的壓縮比,而譯碼同樣簡單.這也就是為什么這種算法成為開發(fā)新算法的基礎,許多后來開發(fā)的文檔壓縮程序都使用了LZSS的思想.例如,PKZip, GZip, ARJ, LHArc和ZOO等等,其差別僅僅是指針的長短和窗口的大小等有所不同. LZSS同樣可以

19、和熵編碼聯(lián)合使用,例如ARJ就與霍夫曼編碼聯(lián)用,而PKZip則與Shannon-Fano聯(lián)用,它的后續(xù)版本也采用霍夫曼編碼. 第二類詞典編碼第二類算法的想法是企圖從輸入的數(shù)據中創(chuàng)建一個短語詞典 (dictionary of the phrases),這種短語可以是任意字符的組合.編碼數(shù)據過程中當遇到已經在詞典中出現(xiàn)的短語時,編碼器就輸出這個詞典中的短語的索引號,而不是短語本身. LZ78算法 LZ78的編碼思想是不斷地從字符流中提取新的字符串(String),通俗地理解為新詞條,然后用代號也就是碼字(Code word)表示這個詞條.這樣一來,對字符流的編碼就變成了用碼字(Code word)

20、去替換字符流(Char stream),生成碼字流(Code stream),從而達到壓縮數(shù)據的目的. LZ78編碼器的輸出是碼字-字符(W,C)對,每次輸出一對到碼字流中,與碼字W相對應的字符串(String)用字符C進行擴展生成新的字符串(String),然后添加到詞典中. LZ78編碼算法步驟1:將詞典和當前前綴P都初始化為空. 步驟2:當前字符C:=字符流中的下一個字符. 步驟3:判斷P+C是否在詞典中 (1)如果是,則用C擴展P,即讓P:=P+C,返回到步驟2. (2)如果否,則輸出與當前前綴P相對應的碼字W和當前字符C, 即(W,C); 將P+C添加到詞典中; 令P:=空值,并返回

21、到步驟2 LZ78編碼舉例 A B A C B C B B A 字符 9 8 7 6 5 4 3 2 1 位置 (2, A) BA 8 5 (3, A) BCA 5 4 (2, C) BC 3 3 (0, B) B 2 2 (0, A) A 1 1 輸出詞典位置步驟輸入數(shù)據流: 編碼過程: LZW算法 J.Ziv和A.Lempel在1978年首次發(fā)表了介紹第二類詞典編碼算法的文章.在他們的研究基礎上,Terry A.Welch在1984年發(fā)表了改進這種編碼算法的文章,因此把這種編碼方法稱為LZW(Lempel-Ziv Walch)壓縮編碼. 在編碼原理上,LZW與LZ78相比有如下差別: LZ

22、W只輸出代表詞典中的字符串(String)的碼字(code word).這就意味在開始時詞典不能是空的,它必須包含可能在字符流出現(xiàn)中的所有單個字符.即在編碼匹配時,至少可以在詞典中找到長度為1的匹配串. LZW編碼是圍繞稱為詞典的轉換表來完成的. LZW算法的詞典 LZW編碼器(軟件編碼器或硬件編碼器)就是通過管理這個詞典完成輸入與輸出之間的轉換.LZW編碼器的輸入是字符流(Char stream),字符流可以是用8位ASCII字符組成的字符串,而輸出是用n位(例如12位)表示的碼字流 (Code stream),碼字代表單個字符或多個字符組成的字符串(String). LZW編碼算法步驟1:

23、將詞典初始化為包含所有可能的單字符,當前前綴P初始化為空. 步驟2:當前字符C:=字符流中的下一個字符. 步驟3:判斷P+C是否在詞典中 (1)如果是,則用C擴展P,即讓P:=P+C,返回到步驟2. (2)如果否,則輸出與當前前綴P相對應的碼字W; 將P+C添加到詞典中; 令P:=C,并返回到步驟2 LZW編碼舉例 C A B A B A B B A 字符 9 8 7 6 5 4 3 2 1 位置 2 BB 5 2 2 2 BA 6 3 3 4 ABA 7 4 4 7 ABAC 8 6 5 4 3 2 1 碼字 1 AB 1 1 C B A 輸出詞典位置步驟輸入數(shù)據流: 編碼過程: LZW算法

24、 LZW算法得到普遍采用,它的速度比使用LZ77算法的速度快,因為它不需要執(zhí)行那么多的綴-符串比較操作.對LZW算法進一步的改進是增加可變的碼字長度,以及在詞典中刪除老的綴-符串.在GIF圖像格式和UNIX的壓縮程序中已經采用了這些改進措施之后的LZW算法. LZW算法取得了專利,專利權的所有者是美國的一個大型計算機公司Unisys(優(yōu)利系統(tǒng)公司),除了商業(yè)軟件生產公司之外,可以免費使用LZW算法. 預測編碼預測編碼是數(shù)據壓縮理論的一個重要分支.它根據離散信號之間存在一定相關性的特點,利用前面的一個或多個信號對下一個信號進行預測,然后對實際值和預測值的差(預測誤差)進行編碼.如果預測比較準確,

25、那么誤差信號就會很小,就可以用較少的碼位進行編碼,以達到數(shù)據壓縮的目的. 第n個符號Xn的熵滿足: 所以參與預測的符號越多,預測就越準確,該信源的不確定性就越小,數(shù)碼率就可以降低.lzw壓縮算法的c語言實現(xiàn)1 程序由五個模塊組成。(1)lzw.h定義了一些基本的數(shù)據結構，常量，還有變量的初始化等。#ifndef _LZW_H_#define _LZW_H_/-#include #include #include #include /-#define LZW_BASE0x102/The code base#define CODE_LEN12/Max code length#define TABL

26、E_LEN4099 / It must be prime number and bigger than 2CODE_LEN=4096. / Such as 5051 is also ok.#define BUFFERSIZE1024/-typedef structHANDLEh_sour;/ Source file handle.HANDLEh_dest;/ Destination file handle.HANDLEh_suffix; / Suffix table handle.HANDLEh_prefix; / Prefix table handle.HANDLEh_code;/ Code

27、 table handle.LPWORDlp_prefix; / Prefix table head pointer.LPBYTElp_suffix; / Suffix table head pointer.LPWORDlp_code; / Code table head pointer.WORDcode;WORDprefix;BYTEsuffix;BYTEcur_code_len; / Current code length. used in Dynamic-Code-Length mode LZW_DATA,*PLZW_DATA;typedef structWORDtop;WORDinde

28、x;LPBYTElp_buffer;HANDLEh_buffer;BYTEby_left;DWORDdw_buffer;BOOLend_flag;BUFFER_DATA,*PBUFFER_DATA;typedef struct/Stack used in decodeWORDindex;HANDLEh_stack;LPBYTElp_stack;STACK_DATA,*PSTACK_DATA;/-VOID stack_create( PSTACK_DATA stack )stack-h_stack= GlobalAlloc( GHND , TABLE_LEN*sizeof(BYTE) );sta

29、ck-lp_stack = GlobalLock( stack-h_stack );stack-index = 0;/-VOID stack_destory( PSTACK_DATA stack )GlobalUnlock( stack-h_stack );GlobalFree( stack-h_stack );/-VOID buffer_create( PBUFFER_DATAbuffer )buffer-h_buffer= GlobalAlloc(GHND,BUFFERSIZE*sizeof(BYTE);buffer-lp_buffer= GlobalLock( buffer-h_buff

30、er );buffer-top= 0;buffer-index= 0;buffer-by_left= 0;buffer-dw_buffer= 0;buffer-end_flag= FALSE;/-VOID buffer_destory( PBUFFER_DATAbuffer )GlobalUnlock( buffer-h_buffer );GlobalFree( buffer-h_buffer );/-VOID re_init_lzw( PLZW_DATA lzw )/When code table reached its top it should/be reinitialized.mems

31、et( lzw-lp_code, 0xFFFF, TABLE_LEN*sizeof(WORD) );lzw-code= LZW_BASE;lzw-cur_code_len= 9;/-VOID lzw_create(PLZW_DATAlzw,HANDLE h_sour,HANDLE h_dest)WORD i;lzw-h_code= GlobalAlloc( GHND, TABLE_LEN*sizeof(WORD) );lzw-h_prefix= GlobalAlloc( GHND, TABLE_LEN*sizeof(WORD) );lzw-h_suffix= GlobalAlloc( GHND

32、, TABLE_LEN*sizeof(BYTE) );lzw-lp_code= GlobalLock( lzw-h_code);lzw-lp_prefix= GlobalLock( lzw-h_prefix );lzw-lp_suffix= GlobalLock( lzw-h_suffix );lzw-code= LZW_BASE;lzw-cur_code_len= 9;lzw-h_sour= h_sour;lzw-h_dest= h_dest;memset( lzw-lp_code, 0xFFFF, TABLE_LEN*sizeof(WORD) );/-VOID lzw_destory(PL

33、ZW_DATAlzw)GlobalUnlock( lzw-h_code);GlobalUnlock( lzw-h_prefix );GlobalUnlock( lzw-h_suffix );GlobalFree( lzw-h_code);GlobalFree( lzw-h_prefix );GlobalFree( lzw-h_suffix );/-#endif(2) fileio.h定義了一些文件操作#ifndef _FILEIO_H_#define _FILEIO_H_/-#include #include #include /-HANDLEfile_handle(CHAR* file_na

34、me)HANDLE h_file;h_file = CreateFile(file_name,GENERIC_READ|GENERIC_WRITE,FILE_SHARE_READ|FILE_SHARE_WRITE,NULL,OPEN_ALWAYS,0,NULL);return h_file;/-WORD load_buffer(HANDLE h_sour, PBUFFER_DATA buffer)/ Load file to bufferDWORD ret;ReadFile(h_sour,buffer-lp_buffer,BUFFERSIZE,&ret,NULL);buffer-index =

35、 0;buffer-top = (WORD)ret;return (WORD)ret;/-WORD empty_buffer( PLZW_DATA lzw, PBUFFER_DATA buffer)/ Output buffer to fileDWORD ret;if(buffer-end_flag) / The flag mark the end of decodeif( buffer-by_left )buffer-lp_buffer buffer-index+ = (BYTE)( buffer-dw_buffer 32-buffer-by_left )by_left);WriteFile

36、(lzw-h_dest, buffer-lp_buffer,buffer-index,&ret,NULL);buffer-index = 0;buffer-top = ret;return (WORD)ret;/-#endif(3) hash.h定義了壓縮時所用的碼表操作函數(shù)，為了快速查找使用了hash算法，還有處理hash沖突的函數(shù)#ifndef _HASH_H_#define _HASH_H_/-#include #include #include /-#defineDIVTABLE_LEN#defineHASHSTEP13/ It should bigger than 0./-WORD

37、get_hash_index( PLZW_DATA lzw )DWORD tmp;WORD result;DWORD prefix;DWORD suffix;prefix = lzw-prefix;suffix = lzw-suffix;tmp = prefixlp_code hash = 0xFFFF )result = FALSE;elseif( lzw-lp_prefix hash = lzw-prefix &lzw-lp_suffix hash = lzw-suffix )result = TRUE;elseresult = FALSE;while( lzw-lp_code hash

38、!= 0xFFFF )if( lzw-lp_prefix hash = lzw-prefix &lzw-lp_suffix hash = lzw-suffix )result = TRUE;break;hash = re_hash_index( hash );return result;/-WORD get_code( PLZW_DATA lzw )WORD hash;WORD code;hash = get_hash_index( lzw );if( lzw-lp_prefix hash = lzw-prefix &lzw-lp_suffix hash = lzw-suffix )code = lzw-lp_code hash ;elsewhile( lzw-lp_prefix hash != lzw-prefix |lzw-lp_suffix hash != lzw-suffix )hash = re_h