c++ - 通过霍夫曼表重建霍夫曼树

Question

我编写了一个程序来将一篇文章编码为霍夫曼代码并输出一个代码表。

小时：000
d:1011
电子：100
升：11
o:01
转：1010
w:001
总位数：27
编码：000100111101001011010111011

我想编写一个程序，将文件作为输入并对其进行解码。

但我不知道如何重建它。

我的问题是如何重建霍夫曼树？

Answer 1

如果代码是以规范方式构建的，则无需重建 Huffman 树，这会使较短的代码在数值上小于较长的代码。有许多方法可以任意将 0 和 1 分配给 Huffman 二叉树的每个分支，并且所有方法都会导致代码具有相同的最优性。从众多选项中选择一个可以在解码和传送代码方面提供优势。

霍夫曼算法所需的唯一信息是代码长度，即每个符号的位数。这样，您可以构建一个规范的霍夫曼代码，从较短的代码推进到较长的代码，并在任何给定的代码长度内按词汇顺序对符号进行排序（例如，按 H、e、w 的顺序对所有长度为 3 的代码进行排序）。在代码长度内排序的目的是减少要发送到接收器以重构代码的数据量。

然后你到达这个替代代码：

l:00
o:01
H:100
e:101
w:110
d:1110
r:1111

现在解码可以用两个简单的表来完成，一个是按顺序排列的那些符号，即“loHewdr”，以及你升级到下一个代码长度的代码值。步骤是0000从一位到两位，1000到三位，1110再到四位。您为最长的代码读取了足够多的位（如果需要，在末尾附加零，但不要在后续步骤中将它们用作代码的开头）。然后，如果该值小于下一个代码长度的开始值，则将该值用作表中的索引，同时考虑代码中的当前位数。否则，将直到下一个值的值的数量添加到索引中，然后检查下一步。计算跳过的值的数量还需要跟踪当前步骤中代码中的位数。

一旦你解码了一个符号，你就知道它有多少位。从流中删除这些位并重复。

这种方法还具有对最常见的最短代码最快的优势。由此产生的解码速度非常好。（还有其他更快的表驱动方法，但它们要复杂得多。）

Answer 2

我的问题是如何重建霍夫曼树？

这将是一棵二叉树。创建一个根节点，将所有代码以 开头的字母0放入左子树，将 以开头的字母1放入右子树。冲洗并重复（递归），删除每个代码的第一个数字。一旦你用完了任何特定代码中的数字，就为相应的字母创建一个叶节点。