Question

Prove the following two properties of the Huffman encoding scheme.

(a) If some character occurs with frequency more than $\frac{\mathbf{2}}{\mathbf{5}}$, then there is guaranteed to be a codeword of length 1 .

(b) If all characters occur with frequency less than$\frac{\mathbf{1}}{\mathbf{3}}$ , then there is guaranteed to be no codeword of length 1 .

Short answer

(a). It is proved that, Huffman codeword has length 1 if some of the frequencies are greater than $\frac{2}{5}$.

(b). It is proved that, Huffman codeword does not have a codeword of length 1 if all the frequencies are less than$\frac{1}{3}$ .

Step-by-step solution

Sum of frequencies

Sum of all the frequencies of a Huffman tree must be 1.Sum of frequencies in the left subtree and right subtree is 1.

Proof by contradiction method

(a)

A contradiction for the case is considered here. Let the full binary bree does not have codeword of length 1. Therefore, the root of the tree will not have frequencies as its children. Left child of the root be I and right child of the root be r . Assume children of l are a and b , children of r are c and d, where $\mathrm{a},\mathrm{b},\mathrm{c},\mathrm{d}$are the frequencies.

Sum of frequencies is 1.

$\mathrm{l}+\mathrm{r}=1$

It is given that at least one character has frequency greater than $\frac{2}{5}$. Let value of is greater than $\frac{2}{5}$. Then value of r is:

localid="1657263872844" $$\begin{gathered} \mathrm{l}+\mathrm{r}=1 \\ \mathrm{r}=1-l \\ \mathrm{r}<1-\frac{2}{5} \\ r<\frac{3}{5} \end{gathered}$$

Hence, r should be less than $\frac{3}{5}$. If r is less than then $\frac{3}{5}$one of the children of r should be maximum $\frac{3}{10}$. If that is the case then that child of r will be less than and should be in the left subtree which is a clear violation of the case discussed. Hence, Huffman codeword has length 1 if some of the frequencies are greater than $\frac{2}{5}$.

Proof by contradiction method

(b)

A contradiction for the case is considered here. Let the full binary bree has a codeword of length 1 . So, the root of the tree has a child of frequency less than$\frac{1}{3}$ . Let the left subtree be l and right subtree be r . Let value of r is less than$\frac{1}{3}$ .

Sum of the frequencies is 1 .

$$\begin{gathered} \mathrm{l}+\mathrm{r}=1 \\ l=1-r \\ l>1-\frac{1}{3} \\ l>\frac{2}{3} \end{gathered}$$

Thus, l should be greater than $\frac{2}{3}$. If l is greater than$\frac{2}{3}$ then one of the children of l should be greater than$\frac{1}{3}$ . But all frequencies should be less than $\frac{1}{3}$which clearly violates the contradiction. Hence, Huffman codeword does not have a codeword of length 1 if all the frequencies are less than$\frac{1}{3}$ .

Thus, the two statements are proved.