超级简单的数据压缩算法—LZW算法 - MichaelCen
超级简单的数据压缩算法—LZW算法
1. 前文回顾
在字符串算法—数据压缩中，我们介绍了哈夫曼压缩算法（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与这个字符串的首字符X1(假设X是由X1X2X3…XN组成）结合成ABX1，给它一个值：83，加到压缩表中：
即X=ABX1, X1是X的首字符（ABX1的首字符），即X1=A;
故得知X=ABA：
下一个数据是80，解压完成。解压后的原数据为ABABABA;
至此，LZW算法介绍完毕。
实现代码：