LZW压缩算法（数据无损压缩）

目录

一、LZW算法介绍

二、算法介绍

1、LZＷ算法的基本概念

2、LZW压缩的基本原理

3、LZW算法流程：

零、常用无损数据压缩算法

字典算法

 游程编码

基于字典编码技术的LZW算法

基于哈夫曼编码原理的压缩算法

基于算术编码的压缩算法

一、LZW算法介绍

LZW（Lempel-Ziv-Welch Encoding）算法又叫“串表压缩算法”就是通过建立一个字符串表，用较短的代码来表示较长的字符串来实现数据的无损压缩。

LZW压缩算法是Unisys的专利，有效期到2003年，所以现在对它的使用已经没有限制了。

二、算法介绍

1、LZＷ算法的基本概念

LZW有三个重要对象：数据流（CharStream）、编码流（String Table）和编译表（String Table）。

（1）编码时，数据流是输入对象 （数据序列），编码流就是输出对象（经过压缩运算的编码数据）；

（2）解码时，编码流是输入对象，数据流是输出对象；而编译表是在编码和解码时都需要借助的对象。

2、LZW压缩的基本原理

提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始数据中的相应字符，减少原始数据大小。注意：此处的编译表是根据原始数据动态创建的，解码时需要从已编码的数据中还原出原来的编译表。

 1. 初始状态，字典里只有所有的默认项，例如0->a，1->b，2->c。此时P和C都是空的。
 2. 读入新的字符C，与P合并形成字符串P+C。
 3. 在字典里查找P+C，如果:
    - P+C在字典里，P=P+C。
    - P+C不在字典里，将P的记号输出；在字典中为P+C建立一个记号映射；更新P=C。
 4. 返回步骤2重复，直至读完原字符串中所有字符。

3、LZW算法流程

（1）步骤一：开始时词典包含所有可能的根，当前前缀字符串P 和 当前字符 均为空；

（2）步骤二：读入新的字符C，与P合并形成字符串P+C；

（3）步骤三：判断P+C是否在字典中

                        如果“是”：

                                P = P + C； 

                                返回步骤二；

                        如果“否”：

                                输出P的映射；

                                 P = P+C ；

                                把前缀字符串P添加到字典，建立映射;

                                令P = C //(现在的P仅包含一个字符C);

（4）步骤四： 判断码字流中是否还有码字要译

                         如果“是”：

                                 返回步骤二；

                         如果“否”：
　　                          把代表当前前缀P的码字输出到码字流;
　　                          结束。

例如：

待压缩字符串：

abccbaaabc

初始时字典中包含所有的根：

在数据压缩过程中形成的字典：

参考：

https://segmentfault.com/a/1190000011425787

https://baike.baidu.com/item/LZW%E7%AE%97%E6%B3%95

https://blog.csdn.net/qq_41819698/article/details/82558107

参考代码：