在字符串算法—数据压缩中，介绍了ffdty树(Huffman )的构建和应用(编码、解码)聪明的世界压缩算法) Huffman compression )。 本文介绍LZW算法。
2. LZW算法
这个算法很简单。 为了便于说明，采用十六进制。 写代码时只需恢复为二进制。
在十六进制中，为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算法介绍完毕。
实现代码：