在字符串算法—数据压缩中，我们介绍了 赫夫曼树（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：
推荐阅读
- 红泥小火炉 新雪备烹茶
- 盘点几位茶鬼的故事
- 吴传家与他的祥华茶厂的馨香故事
- 普洱茶发展前景,普洱茶的泡法
- 液晶电视打开是白色的怎么弄,液晶电视为什么白屏
- 厨房水流太小是三角阀的问题吗,厨房水流太小怎么解决
- 网络交换机的分类、性能和选择
- 防水涂料气味大的是不是有毒,防水涂料气味大并且被盖住了怎么处理
- 2米的床买多大的四件套,2米的床买多大的床垫
- 在查询的优化中为什么要永远小表驱动大表？