Question

Under a Huffman encoding of symbols with frequencies${\mathbf{f}}_{\mathbf{1}}\mathbf{,}{\mathbf{f}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathbf{f}}_{\mathbf{n}}$ , what is the longest a codeword could possibly be? Give an example set of frequencies that would produce this case.

Short answer

The longest codeword possible for symbols with frequencies ${\mathrm{f}}_1,{\mathrm{f}}_2,.....,{\mathrm{f}}_{\mathrm{n}}$is$\mathrm{n}-1$ .

Step-by-step solution

Prefix-free encoding

It is not possible to have a codeword be the prefix of another. If so, it will create ambiguity. Hence, Huffman codewords are found using prefix-free encoding. Prefix-free encoding is done by creating a full binary tree.

Generation of Huffman codewords

A Huffman encoding of n symbols has n leaves in the full binary tree. Each symbol will have codeword equal to the path from the root to leaf node. So, the frequency which is on the lowest level of tree has the longest codeword.

For example: Consider three symbols $(\mathrm{n}=3)$ $\mathrm{a},\mathrm{b},\mathrm{c}$with frequencies $\frac{1}{4},\frac{1}{4},\frac{1}{2}$respectively. The full binary tree representation is:

Here, the codewords for $\mathrm{a},\mathrm{b},\mathrm{c}$are $00,01,1$respectively. a and b have the longest codeword of length 2 . So, a Huffman encoding of 3 symbols has longest codeword of length 2.

Calculation of the longest codeword possible

Maximum height of a full binary tree with n nodes is$\mathbf{n}\mathbf{-}\mathbf{1}$. The length of the codeword of symbols is the height of full binary tree. Therefore, longest codeword possible for a Huffman encoding of symbols is $\mathrm{n}-1$.

Hence, a Huffman encoding of n symbols have a codeword with maximum length$\mathrm{n}-1$ .