c++ - 哈夫曼树的存储与重建

Question

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

拿下面的树:

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

一个想法可能是在每个级别存储符号，然后使用此信息重建树。在这种情况下:A1B2C2。那么如何才能先获取关卡，并将每个关卡与角色关联起来。

Answer 1

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

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

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

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

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

以字符串“banana”为例。显然使用了 3 个符号，'b'、'a' 和 'n'，计数分别为 1、3 和 2。

所以这棵树可能看起来像这样:

    *   / \  *   a / \b   n

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

a = 1b = 00n = 01

但是，如果您只是简单地使用位长度作为规范代码生成的输入，您将生成以下内容:

a = 0b = 10n = 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 个字节的存储空间。然而，随着您添加更多符号，它会迅速增长，而存储代码长度则不会。