目录
一、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初始时字典中包含所有的根：
| 初始 | 映射 |
| a | 1 |
| b | 2 |
| c | 3 |
在数据压缩过程中形成的字典：
| Step | P | C | P+C | if P+C | Action | Output |
| 1 | – | a | a | y | p = a | – |
| 2 | a | b | ab | n | 4<–ab, p = b | 1 |
| 3 | b | c | bc | n | 5<–bc, p = c | 2 |
| 4 | c | b | cb | n | 6<–cb, p = b | 3 |
| 5 | b | a | ba | n | 7<–ba, p = a | 2 |
| 6 | a | a | aa | n | 8<–aa, p = a | 1 |
| 7 | a | a | aa | y | p = aa | – |
| 8 | aa | b | aab | n | 9<–aab,p = b | 8 |
| 9 | b | c | bc | y | p = bc | – |
| 10 | bc | – | bc | y | p = – | 5 |
参考：
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
参考代码：