<< 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.