我写了一个程序，把一篇文章编码成霍夫曼码，输出一个码表。
H:000 d:1011 e:100 l:11 o:01 r:1010 w:001 Total bits:27 Encoded code:000100111101001011010111011
我想编写一个程序，将文件作为输入并对其进行解码。
但我不知道如何重建它。
我的问题是如何重建霍夫曼树？
最佳答案
如果代码是以规范方式构建的，则无需重建霍夫曼树，这使得较短的代码在数值上小于较长的代码。有许多方法可以任意将 0 和 1 分配给霍夫曼二叉树的每个分支，并且所有方法都会导致相同的代码最优性。从众多选择中选择一个在解码和传输代码方面具有优势。
霍夫曼算法所需的唯一信息是代码长度，即每个符号的位数。这样，您就可以构造一个规范的霍夫曼代码，从较短的代码推进到较长的代码，并在任何给定的代码长度内按词汇顺序对符号进行排序(例如，按 H、e、w 的顺序对所有长度为 3 的代码进行排序)。在码长内排序的目的是为了减少发送给接收方的数据量，以便重构码。
然后你得到这个替代代码:
l:00
o:01
H:100
e:101
w:110
d:1110
r:1111
现在解码可以用两个简单的表来完成，一个只是按顺序排列的那些符号，即“loHewdr”，以及你进入下一个代码长度的代码值。步长为0000从一位到两位，1000到三位，1110到四位。您为最长的代码读取了足够的位(如果需要，在末尾附加零，但不要在后续步骤中将它们用作代码的开头)。然后，如果该值小于下一个代码长度的起始值，则将该值用作表中的索引，同时考虑代码中的当前位数。否则将直到下一个值的值的数量添加到索引中，然后检查下一步。计算跳过的值的数量还需要跟踪当前步骤中代码中的位数。
一旦你解码了一个符号，你就知道它有多少位。从流中删除这些位并重复。
这种方法还有一个优势，即对于最短的代码来说速度最快，这是最常见的。由此产生的解码速度非常好。 (还有其他表驱动方法更快，但要复杂得多。)
关于c++ - 通过哈夫曼表重建哈夫曼树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13903050/