Deflate内部实现（LZ77无损压缩算法）超详细图解算法版

Deflate内部实现（LZ77无损压缩算法）超详细图解算法版

引用

CSDN

1.

https://blog.csdn.net/qq_29493173/article/details/139805208

无损压缩算法

Deflate算法是一种广泛使用的无损数据压缩算法，主要用于文件压缩和网络传输。它由两个阶段组成：重复消除（LZ77算法）和位减少（Huffman编码）。

第一阶段：重复消除 — LZ77无损压缩算法

LZ77算法是一种基于字典的无损压缩算法，通过查找重复的未压缩序列并用引用指针替换它们来实现压缩。引用指针由两个元素定义：

• offset（距离）：原始未压缩数据中出现的第一个现有字节的相对位置。
• Length（长度）：重复的字节长度。

LZ77算法使用“滑动窗口”技术，窗口分为两个部分：

• 查找缓冲区（Search buffer）：已编码部分，也称字典。
• 先行缓冲区（Look ahead buffer）：即将进行编码序列的一部分。

滑动窗口的尺寸是影响压缩性能的关键因素。如果窗口太小，可能会发现较少的重复数据序列，导致压缩文件较大；如果窗口太大，则可能需要更长时间来查找重复数据序列，导致压缩速度变慢。

LZ77算法的主要步骤如下：

1. 将编码位置设置为输入流的开头。
2. 在查找缓冲区的窗口中找到最长的匹配项。
3. 如果找到匹配，则输出指针P。将编码位置（和窗口）向前移动L个字节。
4. 如果未找到匹配项，则输出空指针和先行缓冲区中的第一个字节。将编码位置（和窗口）向前移动一个字节。
5. 如果先行缓冲区不为空，则返回步骤2。

举例说明

以字符串"AABCBBABC"为例，说明LZ77算法的压缩过程：

1. 初始字符串从右往左滑动，直至占满所有buffer区。
2. 开始遍历buffer的第一个字符'A'，因Dictionary空，未匹配到'A'，输出(0,0)A。
3. 遍历buffer第一个字符"A"，在Dictionary找到"A"，未超过buffer黄色长度，往后遍历到编码"AB"，Dictionary没有匹配到“AB”字符串，于是只编码"A"，输出(1, 1)。
4. 匹配buffer区第一个字符’B’，Dictionary内未匹配，输出(0,0)B。
5. 匹配buffer区第一个字符’C’，Dictionary内未匹配，输出(0,0)C。
6. 匹配buffer区第一个字符’B’，offset（'B’与Dictionary中匹配的’B’的距离）=2，length=1，输出（2，1）。
7. 匹配buffer区第一个字符’B’，在DICTIONARY匹配到，offset=1，length=1，输出（1，1）。
8. 匹配BUFFER第一个字符 ‘A’，在DICTIONARY匹配到，offset=5，length=3，输出(5, 3)。

最终压缩结果为：(0,0)A (1,1) (0,0)B (0,0)C (2,1) (1,1) (5,3)

图解压缩过程

第二阶段：位减少 — Huffman编码

Huffman编码是一种熵编码方法，用于减少数据的位数。其基本思想是为出现频率较高的字符分配较短的编码，为出现频率较低的字符分配较长的编码，从而实现数据压缩。

通过构建Huffman树，可以将原始数据的位数从120bit（15*8）减少到28bit。

范式Huffman树：在普通Huffman树的基础上，只需保存编码位长，利用位长反推编码。

总结

Deflate算法通过LZ77算法实现重复消除，通过Huffman编码实现位减少，从而实现高效的数据压缩。这种两阶段的压缩策略在许多应用场景中都取得了很好的效果。