超级简单的数据压缩算法—LZW算法

在字符串算法—数据压缩中，我们介绍了 赫夫曼树（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算法介绍完毕。

实现代码：