algorithm - 我应该在 Huffman 树构建算法中为 DEFLATE 提供一致性检查吗？

Question

在 RFC-1951 中有一个简单的算法可以从代码长度列表中恢复霍夫曼树，描述如下:

     1)  Count the number of codes for each code length.  Let
         bl_count[N] be the number of codes of length N, N >= 1.

     2)  Find the numerical value of the smallest code for each
         code length:

            code = 0;
            bl_count[0] = 0;
            for (bits = 1; bits <= MAX_BITS; bits++) {
                code = (code + bl_count[bits-1]) << 1;
                next_code[bits] = code;
            }

     3)  Assign numerical values to all codes, using consecutive
         values for all codes of the same length with the base
         values determined at step 2. Codes that are never used
         (which have a bit length of zero) must not be assigned a
         value.

            for (n = 0;  n <= max_code; n++) {
                len = tree[n].Len;
                if (len != 0) {
                    tree[n].Code = next_code[len];
                    next_code[len]++;
                }

但是算法中没有任何数据一致性检查。另一方面，很明显长度列表可能无效。由于 4 位编码，长度值不能无效，但是，例如，对于某些代码长度，可以有比编码更多的代码。

提供数据验证的最小检查集是什么？或者由于我错过的某些原因不需要此类检查？

Answer 1

zlib 检查代码长度列表是否完整，即它是否用完了所有位模式，并且它没有溢出位模式。一个允许的异常(exception)是当存在单个长度为 1 的符号时，在这种情况下允许代码不完整(位 0 表示该符号，1 位未定义)。

这有助于 zlib 在流中更早地以更高的概率拒绝随机、损坏或编码不当的数据。这与此处另一个答案中建议的稳健性不同，您可以选择允许不完整的代码，并且仅在压缩数据中遇到未定义的代码时才返回错误。

为了计算完整性，您从代码中的位数 k=1 和可能的代码数 n=2 开始。有两种可能的一位代码。您从 n 中减去长度为 1 的代码的数量，n -= a[k]。然后递增 k 以查看两位代码，然后加倍 n。减去两位代码的个数。完成后，n 应该为零。如果在任何时候 n 变为负数，您可以就此停止，因为您有一组无效的代码长度。如果完成后 n 大于零，那么您的代码不完整。