如何正确绘制霍夫曼树

Question

我有以下符号和概率，我想为它们画一棵哈夫曼树：

s = 0.04 || i = 0.1 || n = 0.2 || b = 0.04 || a = 0.3 || d = 0.26 || ~ = 0.06

基于哈夫曼算法，我生成了如下树：

完成者：

1. 加入s + i
2. 加入 1 和 n
的结果
3. 加入~ + d
4. 加入b + a
5. 合并 3 和 4 的结果
6. 将 5 和 2 的结果相加

我的问题： 我做的对不对？如果是这样，最后的概率（6的结果）大于1是否可以接受？

谢谢

Answer 1

不，你做的不对，不，唯一可以接受的是最后的数字必须等于起始数字的总和。

总和与你的情况相符，因为 0.34 + 0.66 = 1，所以我不知道你为什么要问这个。顺便说一句，数字不一定是概率，所以总和不一定是1。数字通常是频率，即该符号出现的次数。

至于你的树，你必须始终连接 两个最低的数字 ，无论是叶子还是 sub-tree 的顶部。一开始是 s = 0.04 和 b = 0.04。你没有那样做，所以你的树不代表霍夫曼算法的应用。然后向那个 0.08 添加 ~ = 0.06。等等。