Question

给定某英文文本,采用哈夫曼编码方法时的总编码长度为________位?

Answer 1

先统计一下每个字母的出现的次数

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