<< Previous exercise (2.70) | Index | Next exercise (2.72) >>

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?

NB: We will use letters from the alphabet to represent the symbols.

Example with n=5:

{a b c d e} 31 / \ {a b c d} 15 e 16 / \ {a b c} 7 d 8 / \ {a b} 3 c 4 / \ a 1 b 2

The tree for n=10 looks similar, only larger.

The minimum number of bits to construct a symbol (i.e. the minimum depth to reach a leaf) for such trees is 1, for the symbol of weight 2^n-1.

The maximum number of bits will be n-1, for the two symbols of least weight.

For any n,the most frequent symbol code is 0.It's straightforward.

And the least frequent symbol,if n is infinite,we can simular merge process:

1,2,4,8,16,...,n

3,4,8,16,...,n

7,8,16,...,n

We can discover the merge process is regulation and also straightforward. Imagining tree picture.The least frequent symbol code is (* n 1) (left corresponds 0,right corresponds 1.)

In this problem, the shapes of huffman trees are same. Every node's left/right branch only have one node. That's because 1 + 2^2 + 2^3 + ... + 2^(n-2) = 2^(n-1)-1 < 2^(n-1). so every time we add a symbol into the Huffman tree, we make the symbol be the brother of the root node of the Huffman tree.