3

什么是使霍夫曼树脱水的最佳方法，脱水我的意思是给定一棵霍夫曼树，以及每片叶子中的字符，如何有效地存储这棵树的结构，然后再重建它。

取下面的树：

---------------garbage------
 -------------/-------\------
 ------------A-------garbage-
 --------------------/-----\-
 -------------------B-------C-

一个想法可能是将符号存储在每个级别，然后使用此信息来重建树。在这种情况下：A1B2C2。那么我怎样才能首先获得关卡，并将每个关卡与角色相关联。

4

2 回答 2

5

您几乎可以肯定不需要存储树本身。您可以这样做，而且它不应该占用您认为的空间，但通常不是必需的。

如果您的霍夫曼代码是规范的，您只需要存储每个符号的位长，因为这是生成规范编码所需的所有信息。这是每个符号相对较少的位数，因此应该相当紧凑。您还可以进一步压缩该信息（请参阅Aki Suihkonen的答案）。

自然，代码的位长与树深度基本相同，所以我认为这大致就是您要问的。重要的部分是知道如何构建规范代码，给定长度 - 它不一定与遍历树产生的代码相同。您可以从中重新生成一棵树，但它不一定是您开始使用的树 - 但是通常除了首先确定代码长度之外您不需要树。

生成规范代码的算法相当简单：

  1. 获取您要为其生成代码的所有符号，首先按代码长度（最短的优先）排序，然后按符号本身排序。
  2. 从零长度代码开始。
  3. 如果下一个符号需要的位比代码中的当前位多，请在代码的右侧（最低有效位）添加零，直到达到正确的长度。
  4. 将代码与当前符号相关联，并递增代码。
  5. 循环回 (3)，直到您生成了所有符号。

取字符串“香蕉”。显然，使用了 3 个符号，“b”、“a”和“n”，计数分别为 1、3 和 2。

所以树可能看起来像这样：

    *
   / \
  * 一种
 / \
十亿

天真地，这可以给出代码：

a = 1
b = 00
n = 01

但是，如果您只是使用位长作为规范代码生成的输入，您将产生以下结果：

a = 0
b = 10
n = 11

它是一个不同的代码，但显然它会产生相同长度的压缩输出。此外，您只需要存储代码长度即可重现代码。

所以你只需要存储一个序列：

0... 1 2 0... 2 0...

其中“...”表示易于压缩的重复，并且值都将非常小（每个可能只有 4 位 - 请注意根本不存储符号）。这种表示将非常紧凑。

如果您确实必须存储树本身，则一种技术是遍历树并存储一个位以指示节点是内部节点还是叶节点，然后对于叶节点，存储符号代码。这对于不包含所有符号的树来说是相当紧凑的，即使对于相当完整的树来说也不算太糟糕。最坏情况的大小将是所有符号的总大小，加上尽可能多的单个位节点。对于标准的 8 位字节流，这将是 320 字节（代码为 256 字节，树结构本身为 511 位）。

方法是从根节点开始，对于每个节点：

  • 如果节点是父节点，则输出 0，然后输出左子节点，然后输出右子节点。
  • 如果节点是叶子，则输出1，然后输出符号

要重构，执行类似的递归过程，但显然是读取数据并选择是递归创建子代，还是读取符号，视情况而定。

对于上面的示例，树的比特流将类似于：

0, 0, 1, 'b', 1, 'n', 1, 'a'

这是树的 5 位，加上符号的 3 个字节，四舍五入到 4 个字节的存储空间。但是，随着您添加更多符号，它会迅速增长，而存储代码长度则不会。

于 2013-02-26T07:23:43.957 回答
2

zlib 规范解释说，存储霍夫曼树只需要每个符号的位长。例如，如果为 A=101、B=111、C=110、D=01 构建一棵树，则只需计算位长并根据长度重新生成树，以便关键字是连续的 --> A=101， B=110，C=111，D=01。（或以下代码产生的任何内容）

设置bl_count[2]=1, bl_count[3]=3和迭代：

code = 0;   // From z-lib specification, RFC 1951
bl_count[0] = 0;
for (bits = 1; bits <= MAX_BITS; bits++) {
    code = (code + bl_count[bits-1]) << 1;
    next_code[bits] = code;
}

由于最大符号长度将小于 16，因此每个符号最多需要 4 位来存储这些长度：3、3、3、2 == 0011 0011 0011 0010；然而，zlib/deflate 做得更好——它运行长度使用转义符号对这些符号进行编码，例如 16 == run of 3、17: run of 4 等，以进一步压缩符号长度流。RLE 也采用零长度的情况，即缺少字符。

于 2013-02-27T07:49:29.550 回答