25 votes

Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\dfrac{1}{2}, \dfrac{1}{4}, \dfrac{1}{8}, \dfrac{1}{16}, \dfrac{1}{32}, \dfrac{1}{32}$, respectively.

What is the average length of the Huffman code for the letters $a, \,b, \,c, \,d, \,e, \,f$?

- $3$
- $2.1875$
- $2.25$
- $1.9375$

29 votes

Best answer

$$\begin{array}{|c|c|} \hline \textbf{Letter} & \textbf{Probability} \\\hline a & 1/2 \\\hline b & 1/4 \\\hline c & 1/8 \\\hline d & 1/16 \\\hline e & 1/32 \\\hline f & 1/32 \\\hline \end{array}$$

$\begin{array}{cc} \textbf{Prefix Code} & \textbf{Code Length} \\ a = 0 & 1 \\ b =10 & 2 \\ c = 110 & 3 \\ d = 1110 & 4 \\ e = 11110 & 5 \\ f = 11111 & 5 \end{array}$

Avg length $= \dfrac{1}{2} \times 1 + \dfrac{1}{4} \times 2+ \dfrac{1}{8} \times 3+ \dfrac{1}{16} \times 4+ \dfrac{1}{32} \times 5+ \dfrac{1}{32} \times 5 \\ = \dfrac{16 + 16 + 12 + 8 + 5 + 5}{32} \\ = 1.9375 $

Correct Answer: $D$

14 votes

Based on the probabilities, we can say the probable frequency of the letters will be

16, 8, 4, 2, 1, 1

Now, the Huffman tree can be constructed as follows:

Average length will be 1/2 * 1 + 1/4 * 2 + 1/8 * 3 + 1/16 * 4 + 1/32 * 5 + 1/32 * 5

= 62/32 = 1.9375

https://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html

0

Because not all the letters occur with same frequency or probability. Purpose of Huffman encoding is to represent the most occurring character with least number of bits. As u can see a has been represented with only 1 bit because it occurs the most with probability 1/2. So we need to multiply length of bits with the probability with which they occur.

0

After calculating like arjun sir, we can even multiply with probably frequencies like this: 16*1 + 8*1 + 4*3 + 2*4 +1*5*2 / 16+ 8+4+2+1+1 = 1.9375

1

@Arjun sir,

for such huffman coding question sometimes sees confusong, Sir can you please check this is right or wrong

1) Expected Length of Huffman Code for N chars (Frequencies given ) =

$\sum$(Bits needed for char * its frequency)

2) Average Length Of Huffman Code for N characters OR Average Bits needed for N characeters = (Assuming average over N characters)

[ $\sum$(Bits needed for char * its frequency) ] / Total characters