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

时间:2021-05-02 04:47:04

1. 前文回顾

  在字符串算法—数据压缩中,我们介绍了哈夫曼压缩算法(Huffman compression),本文将介绍LZW算法

  

2. LZW算法

  这个算法很简单,为了方便讲述,我们将采用16进制,写代码的时候在把它转回2进制就是了。

  在16进制下:A:41; B:42; C:43; D:44;......

  从例子入手:

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

  压缩表是边读数据边建立起来的,一开始,压缩表里的数据为各个字符对应的十六进制值,这里不一一列出,具体可百度26个字母的十六进制。

  首先从第一个数据开始读:

  第一个字符为A, A在压缩表里已存在,值是41;

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

  下一个字符为B,B在压缩表里已存在,值是42;

  前一个字符A与这个字符B结合成AB,给它一个值:81;(为什么是81?因为41~79都被字母用了)

  把AB加到压缩表里:

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

  下一个字符为R,R在压缩表里已存在,值是52;

  前一个字符B与这个字符R结合成BR,给它一个值:82,加到压缩表中:

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

  下一个字符为A,A在压缩表里已存在,值是41;

  前一个字符R与这个字符A结合成RA,给它一个值:83,加到压缩表中:

  如此类推,一直到D那里:

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

  下一个字符为A, A在压缩表里已存在,但下下一个字符为B,它们两组合而成的AB也在压缩表里,我们取含字符最多的AB:

  前一个字符D与这个字符串的首字符A结合成DA,给它一个值:87,加到压缩表中:

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

  下一个字符为R, R在压缩表里已存在,但下下一个字符为A,它们两组合而成的RA也在压缩表里,我们取含字符最多的RA;

  前一个字符串AB与这个字符串的首字符R结合成ABR,给它一个值:88,加到压缩表中:

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

  下一个字符为B, B在压缩表里已存在,但下下一个字符为R,它们两组合而成的BR也在压缩表里,我们取含字符最多的BR;

  前一个字符串RA与这个字符串的首字符B结合成RAB,给它一个值:89,加到压缩表中:

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

  下一个字符为A, A在压缩表里已存在,但下下一个字符为B,它们两组合而成的BR也在压缩表里; 但下下下一个字符为R,它们三组合而成的ABR也在压缩表里,我们取含字符最多的ABR;

  前一个字符串BR与这个字符串的首字符A结合成BRA,给它一个值:8A,加到压缩表中:

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

  下一个字符为A, A在压缩表里已存在,值为41;

  前一个字符串BRA与这个字符A结合成ABRA,给它一个值:8B,加到压缩表中:

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

  下一个字符为空,说明数据已经压缩完了,给个值80作为终止标记:

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

  压缩后的数据就是上述的值的组合,压缩表直接删除。

  压缩后的数据S:41425241434144818382884180。

  压缩的方法讲完了,那么如何解压呢?

  我们也是边解压边建表:

  现有压缩数据S:41425241434144818382884180。

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

  同样的,一开始,压缩表里的数据为各个字符对应的十六进制值,这里不一一列出,具体可百度26个字母的十六进制。

  首先从第一个数据开始读:

  第一个值为41,对应字符A:

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

  下一个数据为42,对应字符B;

  前一个字符A与这个字符B结合成AB,给它一个值:81,加到压缩表中:

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

  下一个数据为52,对应字符R;

  前一个字符B与这个字符R结合成BR,给它一个值:82,加到压缩表中:

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

  如此类推,一直读到81:

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

  下一个数据为81,对应字符串AB;

  前一个字符D与这个字符串的首字符A结合成DA,给它一个值:87,加到压缩表中:

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

  下一个数据为83,对应字符串RA;

  前一个字符串AB与这个字符串的首字符R结合成ABR,给它一个值:88,加到压缩表中:

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

  如此类推,一直读到80:

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

  下一个数据为80,这是压缩的终止值,说明解压完成了,此时,把压缩表丢掉。

  解压后得到原数据S:ABRACADABRABRABRA;

  由于我们的压缩表都是动态生成的,我们省了保存它的时间和空间。

  解压和压缩都介绍完了,这个算法也就结束了,超级简单!

  有时候解压时,会遇到些有趣的情形,如下图:

  原数据压缩:

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

  解压时:

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

  下一个数据为81,对应字符串AB;

  前一个字符B与这个字符串的首字符A结合成BA,给它一个值:82,加到压缩表中:

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

  下一个数据为83,嗯?83?83不在压缩表里啊,去哪找83?

  容我们冷静分析一波:

  首先,压缩表去到了82,下一个数据就是83。因为是83,所以肯定是个字符串。(81以上都是我们自己加的字符串!)

  假设83对应的字符串为X:

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

  前一个字符串AB与这个字符串的首字符X1(假设X是由X1X2X3...XN组成)结合成ABX1,给它一个值:83,加到压缩表中:

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

  即X=ABX1, X1是X的首字符(ABX1的首字符),即X1=A;

  故得知X=ABA:

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

  下一个数据是80,解压完成。解压后的原数据为ABABABA;

  至此,LZW算法介绍完毕。

实现代码:

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