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