puff.c 霍夫曼解码是如何工作的？
puff.c How does the huffman decoding work?
我正在尝试解压缩原始 DEFLATE 数据流，以便了解 DEFLATE 解压缩的工作原理。我现在不关心性能。我只是想详细了解解压缩算法，所以我在网上搜索示例并偶然发现了 Mark Adler 的程序 puff.c。
我想解压这段原始的 DEFLATE 数据：
05 C1 01 01 00 00 08 C3 20 6E FF CE 13 44 D2 4D C2 03
它是用动态霍夫曼码压缩的单块。 RFC-1951 确实很好地概述了块的整体结构。区块头之后是4-19个3位整数，定义了码长字母表的码长；之后是 literal/length 的代码长度和距离字母表，最后是实际的压缩数据。到目前为止一切顺利...
我查看了 puff.c 以了解霍夫曼解码过程的实现应该是什么样子。
在函数 construct 中（第 340-379 行），创建了字母表的符号 table，然后将其用于解码过程。在函数 decode（第 235-255 行）中，使用符号 table 和代码长度频率的 table 对单个符号进行解码。这个功能让我很头疼。我不明白符号、码长频率和实际输入比特流之间的关系。还有支票
if (code - count < first) /* if length len, return symbol */
第 247 行对我来说纯粹是巫术。我在互联网上搜索了解码过程的详细解释，但没有找到如此深入的解释。
能否解释一下process/the解码函数？
Here 是 link 到 puff.c 以备不时之需。
关键是要了解 deflate 中使用的霍夫曼编码是 规范的 ，这意味着分配给符号的 0 和 1 的序列完全由位决定代码的长度和符号的排序。顺序在 RFC 中指定，例如，literal/length 代码以从 0 到 255 的文字字节开始，然后是单个 end-of-block 代码，然后是长度代码，从最短的开始到最长。对于任何给定的，比如说，在动态 header 中描述的 literal/length 代码，通常只有这些符号的一个子集会在块中实际使用并为它们定义代码。
deflate中的约定是将最短代码的第一个有序符号分配为全零。然后，对于该长度的剩余符号，代码按顺序递增为整数（即键）。为了增加到下一个长度，在前一个长度的最后一个符号之后的递增结果中附加一个零位（即加倍）。
对于解码，我只需要 a) 按位长顺序排序的编码符号列表，并在每个位长内按符号顺序排序，以及 b) 每个符号的数量位长，必须加起来等于列表中的符号数。
puff.c中使用的解码方案是从位长列表中最短的位长开始，得到那么多的位。现在我检查这些位的值 作为整数 是否小于或等于该长度的最后一个代码。如果是这样，我就拥有了当前代码的所有位，并且我可以通过索引到 a) 中的符号列表来 return 相应的符号。如果整数的值比上一个代码大，那么我知道我需要更多位来处理这个代码。我将流中的一位再附加到整数，并为下一个代码长度重复该过程。
由于比特在流中的存储顺序相反，所以这有点复杂。当我从连续的位构建整数时，我需要翻转顺序，以便我可以将结果解释为可以比较的整数。
所以，if (code - count < first)可以读作if (code < first + count)，或者if (code <= first + count - 1)，也就是code是否小于等于那个长度的最后一个码。如果是，我们就有代码，对应的符号是h->symbol[index + (code - first)]，其中index是当前长度的第一个符号在符号列表中的位置。
我正在尝试解压缩原始 DEFLATE 数据流，以便了解 DEFLATE 解压缩的工作原理。我现在不关心性能。我只是想详细了解解压缩算法，所以我在网上搜索示例并偶然发现了 Mark Adler 的程序 puff.c。
我想解压这段原始的 DEFLATE 数据：
05 C1 01 01 00 00 08 C3 20 6E FF CE 13 44 D2 4D C2 03
它是用动态霍夫曼码压缩的单块。 RFC-1951 确实很好地概述了块的整体结构。区块头之后是4-19个3位整数，定义了码长字母表的码长；之后是 literal/length 的代码长度和距离字母表，最后是实际的压缩数据。到目前为止一切顺利...
我查看了 puff.c 以了解霍夫曼解码过程的实现应该是什么样子。
在函数 construct 中（第 340-379 行），创建了字母表的符号 table，然后将其用于解码过程。在函数 decode（第 235-255 行）中，使用符号 table 和代码长度频率的 table 对单个符号进行解码。这个功能让我很头疼。我不明白符号、码长频率和实际输入比特流之间的关系。还有支票
if (code - count < first) /* if length len, return symbol */
第 247 行对我来说纯粹是巫术。我在互联网上搜索了解码过程的详细解释，但没有找到如此深入的解释。
能否解释一下process/the解码函数？
Here 是 link 到 puff.c 以备不时之需。
关键是要了解 deflate 中使用的霍夫曼编码是 规范的 ，这意味着分配给符号的 0 和 1 的序列完全由位决定代码的长度和符号的排序。顺序在 RFC 中指定，例如，literal/length 代码以从 0 到 255 的文字字节开始，然后是单个 end-of-block 代码，然后是长度代码，从最短的开始到最长。对于任何给定的，比如说，在动态 header 中描述的 literal/length 代码，通常只有这些符号的一个子集会在块中实际使用并为它们定义代码。
deflate中的约定是将最短代码的第一个有序符号分配为全零。然后，对于该长度的剩余符号，代码按顺序递增为整数（即键）。为了增加到下一个长度，在前一个长度的最后一个符号之后的递增结果中附加一个零位（即加倍）。
对于解码，我只需要 a) 按位长顺序排序的编码符号列表，并在每个位长内按符号顺序排序，以及 b) 每个符号的数量位长，必须加起来等于列表中的符号数。
puff.c中使用的解码方案是从位长列表中最短的位长开始，得到那么多的位。现在我检查这些位的值 作为整数 是否小于或等于该长度的最后一个代码。如果是这样，我就拥有了当前代码的所有位，并且我可以通过索引到 a) 中的符号列表来 return 相应的符号。如果整数的值比上一个代码大，那么我知道我需要更多位来处理这个代码。我将流中的一位再附加到整数，并为下一个代码长度重复该过程。
由于比特在流中的存储顺序相反，所以这有点复杂。当我从连续的位构建整数时，我需要翻转顺序，以便我可以将结果解释为可以比较的整数。
所以，if (code - count < first)可以读作if (code < first + count)，或者if (code <= first + count - 1)，也就是code是否小于等于那个长度的最后一个码。如果是，我们就有代码，对应的符号是h->symbol[index + (code - first)]，其中index是当前长度的第一个符号在符号列表中的位置。