search
Log In
25 votes
3.1k 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
edited by
3.1k views
0
And what is Q.76?

3 Answers

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$


edited by
0
If multiplied with probability directly then don't divide by $\mathbf{100}$
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

3
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
1

@ 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

 

1 vote
The letters a, b, c, d, e, f have probabilities 
1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. 

                 1
               /   \
              /     \
             1/2    a(1/2)
            /  \
           /    \
          1/4  b(1/4) 
         /   \
        /     \
       1/8   c(1/8) 
      /  \
     /    \
   1/16  d(1/16)
  /  \
 e    f
The average length = (1*1/2 + 2*1/4 + 3*1/8 + 4*1/16 + 5*1/32 + 5*1/32)
                   = 1.9375 
Answer:

Related questions

22 votes
1 answer
1
4.2k views
Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \frac{1}{32}$, respectively. Which of the following is the Huffman code for the letter $a, \,b, \,c, \,d, \,e, \,f$? $0$, $10$, $110$ ... $11$, $10$, $011$, $010$, $001$, $000$ $11$, $10$, $01$, $001$, $0001$, $0000$ $110$, $100$, $010$, $000$, $001$, $111$
asked Sep 22, 2014 in Algorithms Kathleen 4.2k views
0 votes
1 answer
2
609 views
Consider the following message: The number of bits required for huffman encoding of the above message are __________? My Strategy:- But the answer given is 52bits i used standard Algorithem Made Easy Solution :-
asked Apr 30, 2018 in Algorithms Na462 609 views
0 votes
0 answers
3
250 views
in Huffman Code, we get extract the minimum at each time, but my minimum is creating duplicate, then which one i choose? i am getting the same avg.no.of bits for every Huffman tree, but the problem is my tree is changing therefore representing the character also changed, if some one asks convert the message ... $\frac{12}{30} $
asked Jul 26, 2018 in Algorithms Shaik Masthan 250 views
...