哈夫曼編碼。對教材P167中習題5.18,思考并完成問題a-d。
題目如下所示:
根據上訴的給出的條件得出英文字母表的哈夫曼樹如下:
a.根據葉子節點在其父節點的左側為0, 在右側為1,可知這些字母的最優Huffman編碼是:
/* 字母表的最優Huffman編碼
e: 001
blank: 110
n: 0000
i: 0001
s: 0100
h: 0101
r: 0110
a: 1000
o: 1010
t: 1110
c: 01110
u: 01111
l: 10011
d: 11110
f: 100100
w: 100101
y: 101100
g: 100101
b: 100110
p: 100111
m: 111110
v: 1111110
k: 11111110
x: 1111111100
j: 1111111101
q: 1111111110
z: 1111111111
*/
b.由 a可得: (3*2+4*8+5*4+6*7+7+8+10*4)/27≈ 5.74 ,即每個字母的編碼平均需要6位。
c.結果肯定比熵(約為5.74)要大,因為在計算熵的時候允許有小數個比特,而實際上每個字元的編碼長度都必需為整數。
d.不是,因為還可以把字首,字尾或者整個單詞的本身組合起來考慮。