2

我正在开发一个文件压缩程序。我们目前正在实施 .ZIP 存档器标准，以便在生成压缩的 .ZIP 存档器时，任何其他有信誉的压缩器（例如 7zip）都可以完美地理解/解压缩它。

我们现在正在开发基于RFC 1951
的 DEFLATE 算法 我们有 LZ77 的变体和带有固定代码的 Huffman 编码，可以完美地工作并与 RFC 兼容，因此可以使用 Literal-Length + Distance 值。

在动态霍夫曼编码中，我目前能够从一些压缩数据（通过另一个可靠的压缩器压缩）中提取霍夫曼树，但是当开始解压缩真实数据时，我得到的值不正确。
可能我以错误的方式阅读树木。

我还没有特别找到有人准确解释这些树的值存储在压缩数据上的方式的任何地方。

我假设编码数据遵循相同的文字长度值 (0~285) + 距离 (0~30) 以及其对应的每个文字/距离的额外位，如 RFC 中所解释的那样，与固定霍夫曼编码的方式相同。

将其存储在固定霍夫曼编码上的方式是，霍夫曼代码与代码的最高有效位一起存储在内存中的最低有效位上。这样，您就可以逐位向下浏览编码树。
霍夫曼码的额外位以另一种方式存储。

动态霍夫曼编码是否以相同的方式存储它们？

有什么我遗漏的或我应该注意的吗？

4

2 回答 2

9

首先，您不需要做您正在做的事情，因为它已经在zlib中为您完成，这是一个允许商业使用的免费压缩库。zlib 根据 RFC 1951 提供了 deflate 压缩和 inflate 解压缩的实现。您还可以使用 minizip，它作为第三方贡献包含在 zlib 源代码包或libzip中，以使用 zlib 处理 zip 文件。

如果您打算自己做，那么您可以查看 puff.c，也在 zlib 发行版中，它是为了补充 RFC 1951 的目的而编写的放气解码器。

RFC 1951 实际上确实准确地解释了格式。你只需要仔细阅读它。puff.c 可能有助于加速学习过程。

非固定霍夫曼编码的正确术语是“动态”。不是“自适应”的。原因是术语“自适应霍夫曼”指的是其他东西——一种在放气格式中没有使用的特殊技术——当你在数据中移动时，霍夫曼树实际上会变形。deflate 使用的动态霍夫曼编码将数据分解为块，并为每个块发送完整的霍夫曼代码，该代码在整个块中是恒定的。

是的，动态霍夫曼码和额外位的存储顺序与固定霍夫曼码相同。棘手的部分是了解 Huffman 码是如何在每个块的 deflate 流标头中传输的。

于 2012-05-06T17:50:23.477 回答
1

我认为您可能对霍夫曼代码额外位的存储方式有误。RFC1951 关于额外位的表示如下：

额外的位应解释为以最高有效位在前存储的机器整数，例如，位 1110 表示值 14。

额外的位是霍夫曼代码的一部分，因此以相同的顺序读取；除其他外，这意味着将有许多长度和距离值范围进行编码，这些值具有连续的霍夫曼代码（即，如果长度/文字字母表的代码 269 以位串“1010”结束，那么长度为 19-22将分别具有代码 101000、101001、101010 和 101011。）

于 2013-06-20T14:49:13.227 回答