The Gateway to Computer Science Excellence
+21 votes
2.2k views

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$?

  1. $3$
  2. $2.1875$
  3. $2.25$
  4. $1.9375$
in Algorithms by Veteran (105k points)
edited by | 2.2k views
0
And what is Q.76?
0

2 Answers

+28 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$

by Boss (17k points)
edited by
+13 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

by Veteran (425k points)
+2
Why isn't average length (sum of lenghts of a,b,c,d,e,f)$/6$ ?
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
0

@ 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

 

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,508 answers
195,534 comments
100,975 users