Exercise 2.71 · 习题

Exercise 2.71: Suppose we have a Huffman tree
for an alphabet of n symbols, and that the relative frequencies of the
symbols are 1
,
2
,
4
,
…
,

2

n

−

1. Sketch the tree for n

=

5; for

n

=

10. In such a tree (for general n) how many bits are required to

encode the most frequent symbol? The least frequent symbol?

练习 2.71：假设我们有一棵 n 个符号字母表的哈夫曼树，各符号的相对频率为 1, 2, 4, …, 2^(n-1)。画出 n=5 和 n=10 时的树。在这样的树中（对一般的 n），编码最高频符号需要多少位？编码最低频符号需要多少位？