具有相同概率的霍夫曼编码符号
Huffman Encoding symbols with same probability
我正在为一门关于信息传递的课程做练习。我们需要将霍夫曼编码为二进制代码字母表。
源字母表有四个符号，概率为：
- P(A) = 0.4
- P(B) = 0.3
- P(C) = 0.2
- P(D) = 0.1
所以对于霍夫曼，我取概率最低的两个符号，在这个例子中是C和D。我构建了一个有两片叶子的子树（C 和 D）。
列表中的下一个符号 B 的概率为 0.3。
我现在可以做两件事。要么用A&B构造第二颗子树，因为B出现的几率和子树CD的值一样。第二个选项是将 B 与子树 CD 放在一起，并创建一个更大的值为 0.6 的树。
在下图中，您可以看到我得到的两个选项。第一棵树正在制作两个子树并将它们放在一起。第二棵树是我们刚刚将 B 插入树中的地方
我现在的问题是我应该选择什么方法？为等概率创建一个新的子树？或者把等概率放入树中？
在这种情况下，您在应用哈夫曼算法时只有一个选择。在每一步中，您必须选择 两个 最低概率。在第二步，它们是 0.3 (B) 和 0.3 (C&D)。您不能在那一步使用 A，因为它的概率更高，为 0.4。所以你画的第一棵树是不正确的，因为它不是应用哈夫曼算法的结果。
你画的第二棵树也不对。或者至少画错了。二叉树在任何时刻都只能有两个分支。它不能有三个。正确的树是 A & (B & (C & D)).
我正在为一门关于信息传递的课程做练习。我们需要将霍夫曼编码为二进制代码字母表。
源字母表有四个符号，概率为：
- P(A) = 0.4
- P(B) = 0.3
- P(C) = 0.2
- P(D) = 0.1
所以对于霍夫曼，我取概率最低的两个符号，在这个例子中是C和D。我构建了一个有两片叶子的子树（C 和 D）。 列表中的下一个符号 B 的概率为 0.3。
我现在可以做两件事。要么用A&B构造第二颗子树，因为B出现的几率和子树CD的值一样。第二个选项是将 B 与子树 CD 放在一起，并创建一个更大的值为 0.6 的树。
在下图中，您可以看到我得到的两个选项。第一棵树正在制作两个子树并将它们放在一起。第二棵树是我们刚刚将 B 插入树中的地方
我现在的问题是我应该选择什么方法？为等概率创建一个新的子树？或者把等概率放入树中？
在这种情况下，您在应用哈夫曼算法时只有一个选择。在每一步中，您必须选择 两个 最低概率。在第二步，它们是 0.3 (B) 和 0.3 (C&D)。您不能在那一步使用 A，因为它的概率更高，为 0.4。所以你画的第一棵树是不正确的，因为它不是应用哈夫曼算法的结果。
你画的第二棵树也不对。或者至少画错了。二叉树在任何时刻都只能有两个分支。它不能有三个。正确的树是 A & (B & (C & D)).