在字符串算法—數(shù)據(jù)壓縮中，我們介紹了 赫夫曼樹（Huffman）的構(gòu)建和應(yīng)用（編碼、譯碼）哈夫曼壓縮算法（Huffman compression）， 本文將介紹 LZW算法 。
2. LZW算法
這個(gè)算法很簡(jiǎn)單，為了方便講述，我們將采用16進(jìn)制，寫代碼的時(shí)候在把它轉(zhuǎn)回2進(jìn)制就是了。
在16進(jìn)制下：A:41; B:42; C:43; D:44;......
從例子入手：
壓縮表是邊讀數(shù)據(jù)邊建立起來的，一開始，壓縮表里的數(shù)據(jù)為各個(gè)字符對(duì)應(yīng)的十六進(jìn)制值，這里不一一列出，具體可百度26個(gè)字母的十六進(jìn)制。
首先從第一個(gè)數(shù)據(jù)開始讀：
第一個(gè)字符為A, A在壓縮表里已存在，值是41；
下一個(gè)字符為B,B在壓縮表里已存在，值是42;
前一個(gè)字符A與這個(gè)字符B結(jié)合成AB，給它一個(gè)值：81；（為什么是81？因?yàn)?1~79都被字母用了）
把AB加到壓縮表里：
下一個(gè)字符為R，R在壓縮表里已存在，值是52;
前一個(gè)字符B與這個(gè)字符R結(jié)合成BR，給它一個(gè)值：82，加到壓縮表中：
下一個(gè)字符為A，A在壓縮表里已存在，值是41;
前一個(gè)字符R與這個(gè)字符A結(jié)合成RA，給它一個(gè)值：83，加到壓縮表中：
如此類推，一直到D那里：
下一個(gè)字符為A, A在壓縮表里已存在，但下下一個(gè)字符為B，它們兩組合而成的AB也在壓縮表里，我們?nèi)『址疃嗟腁B：
前一個(gè)字符D與這個(gè)字符串的首字符A結(jié)合成DA，給它一個(gè)值：87，加到壓縮表中：
下一個(gè)字符為R, R在壓縮表里已存在，但下下一個(gè)字符為A，它們兩組合而成的RA也在壓縮表里，我們?nèi)『址疃嗟腞A;
前一個(gè)字符串AB與這個(gè)字符串的首字符R結(jié)合成ABR，給它一個(gè)值：88，加到壓縮表中：
下一個(gè)字符為B, B在壓縮表里已存在，但下下一個(gè)字符為R，它們兩組合而成的BR也在壓縮表里，我們?nèi)『址疃嗟腂R;
前一個(gè)字符串RA與這個(gè)字符串的首字符B結(jié)合成RAB，給它一個(gè)值：89，加到壓縮表中：
下一個(gè)字符為A, A在壓縮表里已存在，但下下一個(gè)字符為B，它們兩組合而成的BR也在壓縮表里; 但下下下一個(gè)字符為R，它們?nèi)M合而成的ABR也在壓縮表里，我們?nèi)『址疃嗟腁BR;
前一個(gè)字符串BR與這個(gè)字符串的首字符A結(jié)合成BRA，給它一個(gè)值：8A，加到壓縮表中：
下一個(gè)字符為A, A在壓縮表里已存在，值為41；
前一個(gè)字符串BRA與這個(gè)字符A結(jié)合成ABRA，給它一個(gè)值：8B，加到壓縮表中：
下一個(gè)字符為空，說明數(shù)據(jù)已經(jīng)壓縮完了，給個(gè)值80作為終止標(biāo)記：
壓縮后的數(shù)據(jù)就是上述的值的組合，壓縮表直接刪除。
壓縮后的數(shù)據(jù)S：41425241434144818382884180。
壓縮的方法講完了，那么如何解壓呢？
我們也是邊解壓邊建表：
現(xiàn)有壓縮數(shù)據(jù)S：41425241434144818382884180。
同樣的，一開始，壓縮表里的數(shù)據(jù)為各個(gè)字符對(duì)應(yīng)的十六進(jìn)制值，這里不一一列出，具體可百度26個(gè)字母的十六進(jìn)制。
首先從第一個(gè)數(shù)據(jù)開始讀：
第一個(gè)值為41，對(duì)應(yīng)字符A:
下一個(gè)數(shù)據(jù)為42，對(duì)應(yīng)字符B；
前一個(gè)字符A與這個(gè)字符B結(jié)合成AB，給它一個(gè)值：81，加到壓縮表中：
下一個(gè)數(shù)據(jù)為52，對(duì)應(yīng)字符R；
前一個(gè)字符B與這個(gè)字符R結(jié)合成BR，給它一個(gè)值：82，加到壓縮表中：
如此類推，一直讀到81：
下一個(gè)數(shù)據(jù)為81，對(duì)應(yīng)字符串AB；
前一個(gè)字符D與這個(gè)字符串的首字符A結(jié)合成DA，給它一個(gè)值：87，加到壓縮表中：
下一個(gè)數(shù)據(jù)為83，對(duì)應(yīng)字符串RA；
前一個(gè)字符串AB與這個(gè)字符串的首字符R結(jié)合成ABR，給它一個(gè)值：88，加到壓縮表中：
如此類推，一直讀到80：
下一個(gè)數(shù)據(jù)為80，這是壓縮的終止值，說明解壓完成了,此時(shí)，把壓縮表丟掉。
解壓后得到原數(shù)據(jù)S：ABRACADABRABRABRA;
由于我們的壓縮表都是動(dòng)態(tài)生成的，我們省了保存它的時(shí)間和空間。
解壓和壓縮都介紹完了，這個(gè)算法也就結(jié)束了，超級(jí)簡(jiǎn)單！
有時(shí)候解壓時(shí)，會(huì)遇到些有趣的情形，如下圖：
原數(shù)據(jù)壓縮：
解壓時(shí)：
下一個(gè)數(shù)據(jù)為81，對(duì)應(yīng)字符串AB；
前一個(gè)字符B與這個(gè)字符串的首字符A結(jié)合成BA，給它一個(gè)值：82，加到壓縮表中：
下一個(gè)數(shù)據(jù)為83，嗯？83？83不在壓縮表里啊，去哪找83？
容我們冷靜分析一波：
首先，壓縮表去到了82，下一個(gè)數(shù)據(jù)就是83。因?yàn)槭?3，所以肯定是個(gè)字符串。（81以上都是我們自己加的字符串！）
假設(shè)83對(duì)應(yīng)的字符串為X：
前一個(gè)字符串AB與這個(gè)字符串的首字符X 1 (假設(shè)X是由X 1 X 2 X 3 ...X N 組成）結(jié)合成ABX 1 ，給它一個(gè)值：83，加到壓縮表中：
即X=ABX 1 , X 1 是X的首字符（ABX 1 的首字符），即X 1 =A;
故得知X=ABA：
下一個(gè)數(shù)據(jù)是80，解壓完成。解壓后的原數(shù)據(jù)為ABABABA;
至此，LZW算法介紹完畢。
實(shí)現(xiàn)代碼：
