皮皮网

1.zlib使用范例
2.DEFLATE(RFC1951)速成解读 (三)---无压缩及固定huffman压缩
3.DEFLATE(RFC1951)速成解读 (一)---范式Huffman树
4.PNG编解码算法详解
5.数据压缩算法
6.[译] 理解 zip 和 gzip 压缩格式背后的算算法压缩算法

zlib使用范例

       以下是一个关于zlib库的使用示例，展示了如何压缩和解压缩HTTP gzip数据。法源首先，算算法我们定义了两个函数，法源用于压缩数据，算算法分别是法源H5联盟免公众号源码zcompress和gzcompress。这两个函数使用zlib库的算算法deflate函数，分别处理标准的法源deflate压缩和gzip头的添加。

       `zcompress`函数接受原始数据、算算法数据长度、法源压缩后的算算法数据缓冲区和缓冲区大小，通过deflateInit、法源deflate和deflateEnd等步骤进行压缩。算算法`gzcompress`函数在zcompress的法源基础上，增加了gzip头的算算法处理。

       解压缩部分，有两个函数：zdecompress和press。`zdecompress`用于解压缩zlib压缩的数据，通过inflateInit、inflate和inflateEnd进行。`press`是为了解析HTTP gzip格式的压缩数据，它在zdecompress的基础上，处理了gzip头的错误检查。

       示例代码中还包含了一个调试用的main函数，用于演示如何通过上述函数进行实际的数据压缩和解压缩。这个函数将一个字符串进行压缩，然后解压缩，最后输出原始数据和解压缩后的结果。

       总的来说，zlib库的使用涉及到压缩数据的初始化、压缩、解压缩和错误处理等步骤。在实际项目中，可以根据具体需求选择合适的压缩函数，并处理可能的错误情况。

扩展资料

       zlib是提供数据压缩用的函式库，由Jean-loup Gailly与Mark Adler所开发，初版0.9版在年5月1日发表。zlib使用DEFLATE算法，最初是为libpng函式库所写的，后来普遍为许多软件所使用。此函式库为自由软件，使用zlib授权。截至年3月，zlib是包含在Coverity的美国国土安全部赞助者选择继续审查的开源项目。

DEFLATE(RFC)速成解读 (三)---无压缩及固定huffman压缩

       位操作

       在探讨 DEFLATE(RFC) 的压缩算法之前，我们先对位操作进行简要定义。一个字节由8位二进制位组成，读取或写入这些位时，从低到高依次进行。源码超过8位举例来说，我们用二进制流表示 ，从低位开始读取，结果为字节序列A5 0F。

       定义函数 ReadBits(x, b) 和 WriteBits(x, b)。ReadBits(x, b) 从缓存区 x 中读取 b 个二进制位，按从低位到高位的顺序。WriteBits(x, b) 则用于写入 b 个二进制位到字节 x 中，同样按从低位到高位的顺序。

       压缩方式速读

       DEFLATE 的压缩过程分为多个块进行。例如，压缩字节的数据可能划分为3个块，每个块大小分别为、和字节。每个块的第一个位用于指示此块是否为最后一个块。接下来2个位指示块的压缩方式。

       采用三种压缩方式：无压缩、固定Huffman和动态Huffman。每种方式都有其适用场景。无压缩编码格式是最简单的，它只读取前3位，跳过之后的5位，然后读取无压缩块的长度。LZ压缩后的数据在此基础上进一步处理，用于固定和动态Huffman压缩。

       无压缩编码格式

       无压缩编码格式简单明了。在解析时，读取前3个位后，跳过后续的5位，接着读取无压缩块的长度。长度由后续的两个字节组成，格式为：无压缩数据长度 = (block[1] + (block[2] << 8))。然后，继续读取第三个和第四个字节，拼接为 nlen = (block[3] + (block[4] << 8))，确保 nlen + len 总和为。接下来，根据len读取后续的字节，这些字节是无压缩的。

       LZ压缩后的数据

       讨论完无压缩编码格式后，接下来涉及固定Huffman和动态Huffman压缩，这些算法用于处理LZ压缩后的数据。在DEFLATE中，每个符号按字节单位编码，范围为0-，但为了存储LZ压缩后的长度和位置，需要扩展符号表示范围，每个数字称为lz_code。

       编码/解码使用两套不同的红包互换程序源码Huffman树，分别为literal tree和distance tree。literal tree用于编码0-的lz_code，而distance tree较小，用于指示LZ的(length, distance)。

       解码时，首先使用literal tree解码得到lz_code。当lz_code为时，表示块的解压缩完成。对于其他大于小于的lz_code，表示一个LZ指示器（length, distance），需分别通过长度表和距离表解码。

       固定Huffman压缩

       固定Huffman压缩是基于统计意义生成的Huffman树，旨在节省存储Huffman树结构的空间。固定Huffman树的symbol（lit value）、bits length（bits）和code（codes）对照表如下。在C语言中构建代码如下。

       请注意两个关键细节：ReadBits是从低位读取位，而Huffman编码则是从高位读取。例如，读取二进制代码时，第一个读取的位是1，而不是0。symbol（lit value）的范围是0-，但动态Huffman的值范围是0-。确保在存储动态Huffman时，literal tree的bits_length_table长度不超过，否则在使用Zlib进行解码的库中可能会引发错误。

DEFLATE(RFC)速成解读 (一)---范式Huffman树

       本文旨在解读DEFLATE算法中的范式Huffman树部分，关注点在于数据结构的处理以及RFC中的细节问题。DEFLATE算法结合了Huffman算法和LZ算法，实现数据的压缩与解压。重点讨论了范式Huffman树的构造与应用，旨在帮助读者快速了解RFC中的关键点与坑点。

       对于序列"a, b, c, c, c, d, d, d, d, d",通过计算频率，我们构建了一个典型的Huffman树。每个字母编码为特定的"Code"，如a为, b为。通常，我们需要保存每个symbol对应的code和code的位长度。然而，范式Huffman树简化了这一过程，通过规范code的内容，确保每个code的值是确定的，因此只需保存位长度即可重建Huffman树，节省了存储空间。

       范式Huffman树的重建过程如下：首先保存每个symbol的位长，计算位长频率，构建next_code表。next_code通过位长和频率计算得出，源码生成到执行然后根据频率构造code。因此，范式Huffman树仅需位长信息即可重建，大大节省了存储空间。

       思考：位长序列是否一定能生成合法的Huffman树？答案是否定的。Huffman树的原则是，短的code不会与长的code重合。例如，code序列{ , , , }是合法的，而{ , , }则存在冲突（与的前三个bit相同）。因此，使用位长构造Huffman树时，必须检查生成的code是否存在冲突，若存在冲突，则无法构造合法的Huffman树。

PNG编解码算法详解

       PNG是便携式网络图型（Portable Network Graphics）的缩写，因其透明通道、无损压缩特性，广泛应用于设计、游戏、网页、app开发中。PNG与GIF格式有较大关联，其压缩过程无损，可准确还原图像，封装多种pixfmt格式数据，是一种可扩展的封装格式。PNG文件由一个8字节的PNG文件署名、按照特定结构组织的多个数据块组成。关键数据块定义了4个标准数据块，每个PNG文件都必须包含它们。PNG文件包含四个典型数据块，增加acTL、fcTL、fdAT即形成APNG动图格式。

       每个数据块按特定方式排列，包括数据块长度、块类型、块数据和CRC校验码。一个典型的PNG文件的十六进制表示如下：

       （1）PNG signature：0x, 0x, 0x4E, 0x, 0x0D, 0x0A, 0x1A, 0x0A

       （2）IHDR：文件头数据块包含PNG文件中存储的图像数据的基本信息，包括分辨率、比特深度、色彩模式、压缩方法，必须作为第一个数据块出现在PNG数据流中，且一个PNG数据流中只能有一个文件头数据块。

       （3）IDAT：图像数据块存储实际的数据，数据流中可包含多个连续顺序的图像数据块。IDAT存放着图像真正的memcache线程源码剖析数据信息。

       （4）IEND：图像结束数据用来标记PNG文件或数据流已结束，且必须放在文件尾部。

       IDAT的压缩过程包括Filter和deflate两部分。Filter对像素进行过滤，无压缩损失，通过差分编码减少存储所需的比特数。deflate算法结合了LZ和Hoffman算法，用于像素数据压缩，通过字典方式压缩数据，以标记代替重复字符。

       对于PNG格式数据，实际项目应用可选择opencv、libpng等库进行编解码。PNG格式提供了丰富的功能和兼容性，适用于各种图像处理和存储需求。

数据压缩算法

       LZ算法简介与实现

       LZ算法，由Lempel和Ziv于年提出，是一种基于字典的通用数据压缩算法。它采用字典方式压缩，通过字典记录重复出现的数据片段并用标记表示，以此实现数据压缩。

       算法使用前向缓冲区和滑动窗口。数据先读入前向缓冲区，然后滑动窗口移动并将其数据与缓冲区数据进行匹配。缓冲区和窗口中的数据形成字典，用于查找重复数据。找到最长匹配时，将其编码为标记，包括偏移量、匹配长度和下一个字符。若找不到匹配，则编码当前字符。压缩过程循环进行直到处理完所有数据。

       LZ算法效率取决于滑动窗口和前向缓冲区大小以及数据熵。它通常比Huffman编码有更高的压缩比，但压缩过程较慢。解压缩过程则相对快速，因为每个标记明确指示了滑动窗口中所需字符的位置。

       LZ算法通过维护滑动窗口和前向缓冲区，不断更新字典，将重复数据转换为标记进行压缩。解压缩时，根据标记还原原始数据。

       LZ算法实现了压缩数据的编码和解码过程，通过比较滑动窗口和前向缓冲区中的数据，找到最长匹配，使用标记表示，实现压缩。解压缩则通过反向解析标记还原数据。

       LZO与LZ4算法

       LZO算法是块压缩算法，属于LZ压缩家族，旨在提供快速压缩和解压缩性能，不追求极高的压缩比。相比之下，LZ4算法在解压速度上表现更优，特点是面向字节操作，解压速度可达MB/s。

       LZ4算法有多种格式，其中lz4_block_format和lz4_frame_format分别适用于不同场景。lz4_block_format适用于通用场景，主要由多个序列组成，每个序列包含字面量和匹配副本，由令牌、字面量长度、偏移量和匹配长度组成。

       Deflate算法与压缩模型

       Deflate是zip压缩文件的默认算法，广泛用于其他压缩文件如7z、xz等。实际上，Deflate是一种用于数据流压缩的算法。压缩器有三种模型：不压缩数据、使用LZ算法加哈夫曼编码，以及自定义压缩树。

       Deflate算法结合LZ压缩与哈夫曼编码，适应于流式压缩需求。三种压缩模型分别对应不同场景，旨在优化压缩效率和压缩比。

       信息熵与压缩

       数据可以压缩的原因在于数据通常存在冗余性和特定特性。通过分析数据熵，可以将重复数据用较少位表示，实现压缩。基于字典编码也常用于数据压缩，通过替换重复短语减少存储空间。

       gzip与zlib

       gzip和zlib都是基于LZ算法与哈夫曼编码的无损数据压缩格式。gzip在deflate格式基础上增加了文件头和尾信息。zlib则采用zlib头、deflate编码内容和zlib尾信息。

       GZIP格式内部通常采用DEFLATE数据格式，而DEFLATE采用LZ压缩算法压缩数据。压缩和解压缩过程分别针对数据和文件头尾信息进行。

[译] 理解 zip 和 gzip 压缩格式背后的压缩算法

       众所周知，在网络传输数据时，每个字节都需要占用流量，这意味着需要支付费用。尽管存在多种压缩算法，但zip算法可能是最流行的。gzip算法虽然与zip同名，但却是另一种不同的算法。gzip算法在HTTP协议中也得到了广泛应用。尽管各种压缩算法适用于不同场景，但它们的底层都是基于DEFLATE算法。DEFLATE是一种结合了LZ算法和哈夫曼编码的无损数据压缩算法。

       LZ算法是一种用于文本压缩的无损压缩技术。该算法通过使用编码器或解码器中已经出现过的匹配数据信息来替换当前数据，从而实现压缩功能。

       LZ算法并非在整个文本中同时查找重复的字母，而是首先设置一个固定大小的搜索缓冲区，例如（在实际场景中，这个缓冲区的大小通常是几十KB）。在逐一对文本中的字母进行编码时，首先会判断当前字母是否出现在前面缓冲区的个字母中。如果能找到匹配的字母，就记录下当前字母与找到的字母的偏移量d，这样就完成了一个字母编码的第一阶段。接下来，用当前在编码字母邻近的下一个字母与缓冲区中匹配上字母邻近的下一字母进行匹配，如果匹配上就继续进行下一个字母的匹配，如此循环往复，直到缓冲区个字母匹配完或者邻近的字母未匹配上，就结束匹配过程。完成上述过程后，将当前位置匹配上的连续字母替换成与缓冲区字母的偏移量以及这段连续字母的个数l。这样，字母编码的第二阶段就完成了。

       让我们用一个例子来看看它是如何工作的：

       首先，最简单的方法就是直接替换第二次出现的O为指向第一次出现的O的一个标记，或者替换第二次出现的RTO为指向第一次出现的RTO。

       下面更具体地描述一下这个过程。假定我们设置的缓冲区大小是4，把这4个长度的缓冲区看成是一个滑动窗口沿着正文文本向右滑动：

       滑动窗口随着编码的迭代一步步向右移动，前面4步中滑动窗口内的字母都没有发现重复。到了第5步，滑动窗口内字母O已经出现重复了，然后查看字母O右侧的R，发现滑动窗口中匹配字母O右侧相邻的字母并非R，便不再继续向右进行匹配，将第2个O替换成(1, 1)（表示：滑动窗口中匹配的字母离当前字母偏移距离为1，匹配上的连续字母长度为1）。在第6步中，滑动窗口中字母R与其左边第4个字母匹配上了，继续检查下一个字母T的匹配情况，然后发现滑动窗口中RT也匹配上了。然后继续下一个字母O，在滑动窗口中匹配RTO也匹配上了，并且到此为止，因为下一个字母匹配上了。滑动窗口中匹配上的字母与当前字母的偏移距离为4，同时有连续3个字母匹配上了，所以这里将匹配上的3个字母替换成(4, 3)。接着在第7步中，字母R与偏移距离3出的字母匹配上，但是接下来的RR并未匹配上，在第8步中发现最近的匹配上的R的偏移距离为1。最终整段文本经过编码的结果如下：

       压缩过的文本其实是由一系列的这种(d, 1)标记对和字母组成，标记对无法直接找到相匹配的字母。在解压过程中，字母保持不变，这种标记对转换为其指向位置的字母。下面看一个解压的例子：

       字母abc保持不变，标记对(3, 2)表示从当前位置向左移动3个单位，然后取出2个字母，因此其转换为ab。现在原始文本变成了这样abcab(1, 1)，最后一个标记对表示从当前位置向左移动1个单位，然后取出1个字母，因此转换为b。最终解压完成的文本为abcabb。

       在用LZ消除文本中重复的字母后，再使用哈夫曼编码进行第二次压缩。这种方法用较短的编码代替较常用的字母，用较长的编码代替较少用的字母，从而减少了文本的总长度。

       让我们用一个简单的示例文本来看看它是如何工作的。

       这个例子中，我们希望能无损地压缩这段文本。通常一个字母占用8字节，所以这段文本总长度有字节。在这段文本中，我们发现其中字母F只出现了1次，而字母E出现了7次。哈夫曼编码正是利用了这一特性，通过减少出现频率高的字母本身的字节长度，来减少整个文本所占的总长度。

       要采用哈夫曼编码压缩文章，首先需要统计各个文本中各个字母的出现频率。上述例子中的字母频率如下：

       我们需要使用文本中的字母作为叶子节点来构建一颗二叉树，通过这棵二叉树来编码文本中的每一个字母。从出现频率最小的字母：P和F开始，让其作为底层的叶子节点，将其频率相加的值作为父节点，这样便得到了如下的二叉树：

       重复上面的步骤，依次使用频率最小的字母：U和O以及R和T，最后剩下频率最高的字母E先单独放着。

       接下来使用上面得到的4个二叉树作为子节点来创建一颗更大的二叉树，将上面的二叉树的根节点的频率值递增排序，优先使用根节点频率值小的二叉树作为新的二叉树子节点。这里使用U和O、R和T这组二叉树组成了如下的一颗二叉树：

       这时候还有3颗二叉树，根节点分别为：9、9、7（第一个9是上一步创建的二叉树），同样的，将根节点频率值最小的两个作为子节点创建新的二叉树如下：

       现在剩下一颗将根节点值为的大二叉树和根节点值为9叶子节点为R、T的二叉树，将其作为子节点创建一颗新的二叉树如下：

       现在我们要做的就是根据这棵二叉树来对文本进行编码。依次从跟节点访问各个字母，遇到左分支当成0，遇到右分支当成1，按照字母沿着二叉树访问路径的顺序所将这些0、1连接起来。比如，从根节点到字母E先后需要经过1次左分支和1次右分支，所以字母E的编码为。字母U需要经过4次左分支，其编码为；F需要经过2次左分支和2次右分支，其编码为。可以发现，在这里例子中出现频率非常高的字母E编码后位数比出现频率较少的字母F编码后位数要少。经过这样的编码处理，最终压缩过的文本如下：

       这段压缩后的文本长度只有位，远比原始的位长度小。

       假如收到这样一段压缩过的文本，我们希望能够解压它让其变得可以理解。我们都知道一段未压缩过的文本中的一个字符占用8位，上面说过经过哈夫曼编码压缩后一个字符的位数并不是固定8位的，所以并不清楚一段数据（比如：）是表示1个字符、2个字符或者3个字符，因此这段压缩过的文本将如何解压呢？

       这一步不存在任何奇迹，要准确解压还需要上面编码中构建的二叉树。得到这个用于编码的二叉树有两种方案，第一种是其和压缩后的文本放一起作为原始文本的压缩结果，这可能会导致压缩后的文本比原始文本还要大；第二种方案是使用预先定义好的二叉树。我们知道各个字母在英语中的使用频率，完全可以根据这个频率来构建上述的二叉树。使用这种预先定义的公共字母频率二叉树压缩部分文本的结果可能比根据文本内容字母频率二叉树压缩的效果差一些，但是这样不再需要将字母频率二叉树保存到压缩后的文件中。总而言之，这两种方案各有优缺点。

       虽然本文没有深入的分析各种压缩算法原理的细节和对应的实现，但是经过上述讲解你应该已经对文本如何被压缩成zip和gzip等格式有了大概的认识。希望本文能满足你对压缩算法神秘面纱的好奇心：）

       *从技术上来说，zip压缩格式是支持使用其他的压缩算法的，但是DEFLATE是其中最常用的一种。

       如果发现译文存在错误或其他需要改进的地方，欢迎到掘金翻译计划对译文进行修改并PR，也可获得相应奖励积分。文章开头的本文永久链接即为本文在GitHub上的MarkDown链接。

       掘金翻译计划是一个翻译优质互联网技术文章的社区，文章来源为掘金上的英文分享文章。内容覆盖Android、iOS、前端、后端、区块链、产品、设计、人工智能等领域，想要查看更多优质译文请持续关注掘金翻译计划、官方微博、知乎专栏。

deflate是什么意思？

       Deflate是一种压缩数据的算法，该算法是由雅克·德维特斯和菲利普·韦格纳在年设计开发的。它的出现解决了传统的压缩算法存在的一些问题，比如缺乏互操作性和效率低下等问题。Deflate算法能在不影响数据完整性的情况下减小数据的大小，从而加速数据传输和降低存储成本。

       Deflate算法被广泛应用于计算机网络协议和文件压缩等领域。例如，它是HTTP协议中用于压缩数据的一种标准算法。大文件使用Deflate进行压缩后，可以减小其文件大小以便更快地传输。另外，Deflate算法是ZIP压缩格式的默认压缩算法，使用Deflate压缩文件后，可以在极大程度上减小ZIP文件的大小，从而节省存储空间。

       虽然Deflate算法可以大大减小数据的大小，但它也有其限制和局限性。首先，较小的文件往往没有多大的压缩效果。其次，对于包含大量随机数据或者无法重复的文件，Deflate算法并不是一种好的压缩算法。此外，Deflate算法压缩的效率往往依赖于具体的数据结构和压缩方式。因此，使用Deflate算法进行数据压缩时，需要考虑到具体的应用环境和使用场景，从而选择不同的压缩方式来达到最佳的压缩效果。