Chapter 11.2, Problem 30E

Suppose that m is a positive integer with m>2 An m-ary Huffman code for a set of N symbols can be constructed analogously to the construction of a binary Huffman code. At the initial step, ((N - i) mod (m — 1)) + 1 trees consisting of a single vertex with least weights are combined into a rooted tree with these vertices as leaves. At each subsequent step, the m trees of least weight are combined into an mary tree.

30. Consider the three symbols A, B, and C with frequencies A: 0.80, B: 0.19, C: 0.01.

a) Construct a Huffman code for these three symbols.

b) Form a new set of nine symbols by grouping together blocks of two symbols, AA, AB, AC, BA, BB, BC, CA,

CB, and CC. Construct a Huffman code for these nine symbols, assuming that the occurrences of symbols in

the original text are independent.

c) Compare the average number of bits required to encode text using the Huffinan code for the three symbols

in part (a) and the Huffman code for the nine blocks of two symbols constructed in part (b). Which is more

efficient?