Zlib压缩算法

LZ77、LZ78、霍夫曼编码、滑动窗口、Rabin-Karp算法、哈希链、I/O缓冲区

zlib是一个免费的开源软件库，用于无损数据压缩 和 减压。它是由Jean-loup Gailly（压缩）和Mark Adler（解压缩）用C语言编写的。zlib的第一个版本于1995年5月发布。Jean-loupGailly和Mark Adler也为gzip（GNU zip）。在后台，gzip使用zlib库。

压缩 zlib中使用的算法是 放气方法。deflate方法将输入数据编码为压缩数据。的减压 zlib中使用的算法是 膨胀 方法，这是一种解码过程，需要使用压缩的位流进行解压缩并正确生成原始的全尺寸数据或文件。

LZ77是基于字典的无损压缩算法。它也被称为LZ1。

基于字典的算法的基本思想是，通过引用该序列的先前出现来替换数据中特定字节序列的出现。

基于字典的压缩算法有两种主要类型：LZ77和LZ78。这两个算法以两个创建者Jakob Ziv和Abraham Lempel命名。LZ77（Lempel-Ziv77）和LZ78（Lempel-Ziv78）分别发表于1977年和1978年。

LZ77压缩算法通过使用 滑动窗口 查找重复的数据序列，并使用称为a的一对数字对每个重复的序列进行编码 长距离对。

滑动窗由两部分组成： 搜索缓冲区和 前瞻缓冲区。搜索缓冲区包含字典-最近编码的数据，而前瞻缓冲区包含要编码的输入数据序列的下一部分。

在LZ77算法中，压缩器通过搜索缓冲区进行搜索，直到找到与超前缓冲区中的第一个字符匹配为止。搜索缓冲区中可能存在多个匹配项，并且压缩程序将找到长度最长的一个匹配项。当。。。的时候最长的匹配 找到后，压缩器将其编码为三元组 （D，L，C） 哪里：

D =搜索光标到超前缓冲区起点的距离
L =最长匹配的长度
C =超前缓冲区中最长匹配的下一个字符
在三元组中添加第三个元素C的原因是为了处理在搜索缓冲区中找不到匹配项的情况。在这种情况下，D和L的值均为0，并且C是当前预读缓冲区中的第一个字符。

霍夫曼编码是一种统计压缩方法。它使用以下代码编码数据符号（例如字符）可变长度代码，代码长度基于相应符号的频率。

霍夫曼编码以及其他可变长度编码方法具有两个属性：

对更加频发发生的数据符号的代码比低频发生的数据符号 更短。
每个代码可以是 唯一解码。这要求代码是前缀码，表示一个符号的任何代码都不是其他符号的代码前缀。例如，如果将code“0”用作symbol “A”，则code“01”不能用于symbol“B”，因为code“0”是code“01”的前缀。前缀属性可确保在解码时确定符号边界在哪里没有歧义。
霍夫曼编码有两个步骤：

从原始数据符号构建霍夫曼树。霍夫曼树是一种二叉树结构。
遍历霍夫曼树并将代码分配给数据符号。
霍夫曼码可以是 固定（静态） 要么 动态。两者都用deflate方法。

可以通过检查大量数据集并找到典型的代码长度来创建固定的霍夫曼代码。使用固定霍夫曼编码时，所有输入数据符号均使用相同的编码。

动态霍夫曼码是通过将输入数据分为多个块，并为每个数据块生成代码来生成的。

zlib具有10个压缩级别（0-9）。不同级别的压缩性能不同压缩率 和 速度。级别0表示不压缩，zlib将输出原始数据。1级是最快的，但压缩率较低。级别9提供最高的压缩率，但压缩速度较慢。zlib使用的默认压缩级别为6。

https://blog.csdn.net/Rong_Toa/article/details/108986430