DEFLATE 区块 Header

Question

我有几个关于 DEFLATE 块的 header 的问题，特别是关于这一部分：

               5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286)
               5 Bits: HDIST, # of Distance codes - 1        (1 - 32)
               4 Bits: HCLEN, # of Code Length codes - 4     (4 - 19)

               (HCLEN + 4) x 3 bits: code lengths for the code length
                  alphabet given just above, in the order: 16, 17, 18,
                  0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15

                  These code lengths are interpreted as 3-bit integers
                  (0-7); as above, a code length of 0 means the
                  corresponding symbol (literal/length or distance code
                  length) is not used.

               HLIT + 257 code lengths for the literal/length alphabet,
                  encoded using the code length Huffman code

               HDIST + 1 code lengths for the distance alphabet,
                  encoded using the code length Huffman code

HLIT、HDIST 和 HCLEN 是否必须分别至少为 257、1 和 4？例如，如果我的未压缩数据仅包含 26 个不同的字节，则只有 26 个 literal/length 代码（前提是 LZ77 阶段没有插入长度 codes/back 引用）。但是，26 - 257 会产生一个负数，即如何将其存储为 5 位？
在 (HCLEN + 4) x 3 bits、HLIT + 257 code lengths 和 HDIST + 1 code lengths 部分中，如果其中一个代码未使用，是否应该向 DEFLATE 块发送任何内容？例如，如果代码长度代码中的 14 未使用，应该发出三个零位、一个零位还是什么都不发出？
在HLIT + 257 code lengths和HDIST + 1 code lengths段中，每个码长应该是多少位？

感谢您的帮助！

Answer 1

是的。这是长度列表中表示的代码数。如果长度为零，则该符号没有代码。因此，在您给出的示例中，literal/length 代码的 header 中将有 257 个长度，但其中只有 27 个是 non-zero。（第 27 个用于 end-of-block 符号。）
如果代码未使用，则 header 的该部分具有三个零位，用于代码长度代码符号，或霍夫曼代码为零，用于 literal/length 或距离符号。
这些是可变位长的霍夫曼码，用码长码描述。

它在 RFC 中说：

     A code length of 0 indicates that the corresponding symbol in
     the literal/length or distance alphabet will not occur in the
     block, and should not participate in the Huffman code
     construction algorithm given earlier.

它还在你自己的问题中复制的内容中说：

           HLIT + 257 code lengths for the literal/length alphabet,
              encoded using the code length Huffman code

           HDIST + 1 code lengths for the distance alphabet,
              encoded using the code length Huffman code

DEFLATE 区块 Header

DEFLATE Block Header

compression

zip

gzip

deflate

huffman-code