给定某英文文本,采用哈夫曼编码方法时的总编码长度为位?给定某英文文本为“thisisanidealstring”,采用哈夫曼编码方法时的总编码长度为位.答案是79位,我想问是怎么算出来的? 数学
网友回答
【答案】 先统计一下每个字母的出现的次数
t:2 h:1 i: 4 s:3 _:4 a:2 n:2 d:1 e:1 l:1 r:1 g:1
然后构造哈夫曼树
23
/ \
15 8
/ \ / \
7 8 i4 _4
/ \ / \
s3 4 4 4
/ \ / \ / \
2 2 2 t2 a2 n2
/ \ / \ / \
h1 d1 e1 l1 r1 g1
所以对应的所有叶子结点的路径长度 * 出现次数 之和便是总编码长度
WPL = 3 * 3 + 5* （1+1+1+1+1+1） + 4*（2+2+2） + 2*（4 + 4） = 79