帮忙看看哈弗曼编码

学术版

helin2010 @ 2024-09-20 10:10:20

假设字母表 { a , b , c , d , e } {a,b,c,d,e} 在字符串出现的频率分别为 1 0 % 10%, 1 5 % 15%, 3 0 % 30%, 1 6 % 16%, 2 9 % 29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码,字母 d d 的编码长度( )位。

我在网上看到了解题方法,依次选择两个最小的频率画,最后连接成二叉树。想问一下,是将小的数放在左边节点 并在与父节点连接处写上0,大的放在右边节点 并在与父节点连接处写上1,然后找到要算的字母对应的数,然后从根节点开始记录 直到所对应数的地方 的连接处上的0或1的数字,组成二进制数,然后转换成十进制,是吗?


by Hagasei @ 2024-09-20 10:19:27

问的是编码长度,只需要二进制串长度(树上深度)即可


by Hagasei @ 2024-09-20 10:20:33

然后左右儿子是不分的(两个数选一个当左儿子选一个当右儿子即可),所以 haffman tree 会有很多棵,不过不会影响答案


by xyw114514 @ 2024-09-20 15:26:56

2


|