赫夫曼树中的歧义
赫夫曼树中的歧义
提问于 2022-02-22 19:52:40
我想为四个符号a，b，c，d创建一个Huffman树，频率为5,4,3,2。
为了简单起见，我将忽略符号标签本身，只关注频率标签。
第一步，创建4个单顶点树，其根被标记为频率为5,4,3,2。
接下来，将根被标记为2,3的两个单顶点树合并成一个三顶点树，其根被标记为3+2=5，其子树被标记为2,3。
下一步是将标记为4的树与另外两棵树中的一棵合并，这两棵树的根都被标记为频率5。
我们选哪一个？
这两种选择导致了非常不同的树和赫夫曼密码。具体来说，一种选择导致码字长度为1,2,3,3的代码，而另一选择导致码字长度2,2,2,2。
在这种情况下，以前的代码不可能是正确的，因为它的预期码字长度更长.这将违反赫夫曼密码的著名最优性。
，什么是构造树的通用处方，总是产生最优的哈夫曼代码？
回答 1
Stack Overflow用户
发布于 2022-02-22 20:42:01
马克·阿德勒澄清了这一点。为了记录在案，
上述两种码的预期码字长度正好是2位。
第一个代码：$5/14 *1+ 4/14 *2+ 3/14 *3+ 2/14 *3= 2$
第二个代码：$5/14 *2+ 4/14 *2+ 3/14 *2+ 2/14 *2= 2$
我想，无论我用哪种方式打破联系，最终的代码都是最优的！
谢谢马克！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/71227504
复制相关文章
相似问题
腾讯云开发者
