LZ算法

无损压缩算法(https://blog.csdn.net/weixin_39541632/article/details/108435916)

1、案例介绍

举个例子，如果我们要发送 “AAA” 这个字符串，那么我们就要发送 3 个字节的数据来存储这个信息，但是，如果将数据压缩，以数字+字符的形式，可能只需要使用 “3A” 作为发送的信息，也就是只需要使用 2 个字节即可完成发送，收到者会解压该信息，理解为由 3 个后面的字符组成的信息流，解压得到 “AAA”。

Lempel Zip（LZ）编码是称为基于字典的编码的那一类算法的一个例子，它是用其发明者的名字（Abraham Lempel 和 Jacob Ziv）命名的。在通信会话的时候它将会产生一个字符串字典。如果接受和发送双方都有这样的字典，那么字符串可以由字典中的索引代替，以减少通信的数据的传输量。这种算法有不同的版本（LZ77、LZ78等）。

—— 《计算机科学导论 第三版》

2、准备工作

使用 try-except-else-finally 结构，当然这其中的关键字不是必须的，其中 except 用来捕获可能的异常，如果出错就会执行 except 下面的代码，如果没有出错就会执行 else 下面的代码，而 finally 中的代码无论出错与否都会执行。发现了吗？只要我们使用异常捕获语句，我们就能够让程序即使发生了异常也能运行下去。

3、算法思想

压缩：以纯英文字符串为例，逐个遍历每个字符串，如果当前字典表中还没有该字符，则将该字符加入字典中，键为该字符，值为生成器返回的数字，若有当前字符，则继续加入下一个字符，此时便有两个字符组成了字符串，判断该字符串是否在当前字典中，如果在，则继续添加下一个字符，组成新的字符串，如果不在，则将该字符串加入字典。最终构成的输出字符串，是用字典中的值代替字符串+末尾字符的形式。

解压：传入字符串是数字+字符构成的，故取其中的数字和字符来构建字典，再反向通过查找字典，将传入字符串中的数字用字符串来代替。

4、样例说明

待压缩字符流:    BAABABBBAABBBBAC, 长度:16.
dictionary:
B    -->    1
A    -->    2
AB    -->    3
ABB    -->    4
BA    -->    5
ABBB    -->    6
BAC    -->    7
压缩结果:    BA2B3B1A4B5C, 长度:12
待解压字符流:    BA2B3B1A4B5C, 长度:12.
解压缩结果:    BAABABBBAABBBBAC, 长度16

Process finished with exit code 0

字典建立过程： B不存在则分配1 A不存在则分配2 A存在，则和B组合即AB不存在分配3 A存在，AB存在，ABB不存在则分配4 ....

压缩过程： B刚建立字典 A刚建立字典 2是字典2中的A，此时没有AB 第4个B应该是1，但是这时候可以和前面的AB建立字典3，因此保持B ...

解压过程： B建立字典1 A建立字典2 2则转换为A B建立字典AB--3 3则转换为AB ...