Deflate压缩块的结构

我在理解 Deflate 算法时遇到困难（RFC 1951 https://www.rfc-editor.org/rfc/rfc1951).

TL; DR如何解析Deflate压缩块4be4 0200?

我创建了一个包含字母和换行符的文件a\n在里面，然后运行gzip a.txt。结果文件a.txt.gz:

1f8b 0808 fe8b eb55 0003 612e 7478 7400

4be4 0200

07a1 eadd 0200 0000

我知道第一行是带有附加信息的标题，最后一行是 CRC32 加上输入的大小（RFC 1951 https://www.ietf.org/rfc/rfc1951.txt）。这两个不给我带来麻烦。

但是我如何解释压缩块本身（中间线）？

这是它的十六进制和二进制表示：

4be4 0200

0100 1011
1110 0100
0000 0010
0000 0000

据我了解，不知何故这些：

每个压缩数据块以 3 个标头位开始，其中包含以下数据：

• 第一位 BFINAL
• 接下来的 2 位 BTYPE

...实际上最终到达了end第一个字节：0100 1011。 （我将跳过这个问题，为什么有人将实际上位于其他内容尾部的东西称为“标题”。）

据我所知，RFC 包含一些内容应该是对此的解释：

• 数据元素按以下顺序打包成字节 增加字节内的位数，即开始 与字节的最低有效位。
• 霍夫曼码以外的数据元素被打包 从数据的最低有效位开始 元素。
• 霍夫曼代码从最重要的开始打包 代码的重要位。

换句话说，如果将压缩数据打印为 字节序列，从第一个字节开始right边际并继续left，与最 像往常一样，左侧每个字节的有效位是 能够从右到左解析结果，宽度固定 元素以正确的 MSB 到 LSB 顺序和霍夫曼代码 位反转顺序（即，代码的第一位 相对 LSB 位置）。

但遗憾的是我不明白这个解释。

回到我的数据。 OK，那么BFINAL就设置好了，那么BTYPE又是什么呢？ 10还是01？

如何解释该压缩块中的其余数据？

首先让我们看看压缩数据的十六进制表示形式为一系列字节（而不是您问题中的一系列 16 位大端值）：

4b e4 02 00

现在让我们将十六进制字节转换为二进制：

01001011 11100100 00000010 000000000

根据 RFC，这些位是“从字节的最低有效位开始”打包的。字节的最低有效位是该字节的最右边的位。所以第一个字节的第一位是这样的：

01001011 11100100 00000010 000000000
       ^
       first bit

第二位是这个：

01001011 11100100 00000010 000000000
      ^
      second bit

第三位：

01001011 11100100 00000010 000000000
     ^
     third bit

等等。一旦您检查了第一个字节中的所有位，您就可以从第二个字节的最低有效位开始。所以第九位是这样的：

01001011 11100100 00000010 000000000
                ^
                ninth bit

最后一点，即三十秒的一点，是这样的：

01001011 11100100 00000010 000000000
                           ^
                           last bit

BFINAL 值是压缩数据中的第一位，因此包含在上面标记为“第一位”的单个位中。它的值为 1，表示这是压缩数据中的最后一个块。

BTYPE 值存储在数据的接下来两位中。这些是上面标记为“第二位”和“第三位”的位。唯一的问题是两者中哪一位是最低有效位，哪一位是最高有效位。根据 RFC，“霍夫曼代码以外的数据元素被打包 从数据元素的最低有效位开始。”这意味着这两个位中的第一个，即标记为“第二位”的位，是最低有效位。这意味着 BTYPE 的值为01以二进制形式。因此表明该块是使用固定霍夫曼码压缩的。

这是最容易完成的部分。解码压缩块的其余部分更加困难（并且对于更现实的示例，更加困难）。正确解释如何做到这一点将使这个答案对于本网站来说太长（并且您的问题太宽泛）。不过，我会给你一个提示，数据中接下来的三个元素是霍夫曼代码 10010001（'a'）、00111010（'\n'）和 0000000（流结束）。其余 6 位未使用，并且不是压缩数据的一部分。

请注意，要了解如何解码 deflate 压缩数据，您必须了解什么霍夫曼码 https://en.wikipedia.org/wiki/Huffman_coding是。您正在遵循的 RFC 假设您这样做。你还应该知道如何LZ77压缩 https://en.wikipedia.org/wiki/LZ77_and_LZ78#LZ77有效，尽管该文档或多或少解释了您需要了解的内容。