Huffman Coding Problem

A file contains the following characters with the frequencies as shown. If Huffman coding is used for data compression, determine-

  1. Huffman code for each character
  2. Average code length
  3. Length of Huffman encoded message (in bits)               

                                                                                                                                                                                                                                                                                                        

                Characters 

 

Frequencies

         a       10       
         e        15
         i       12
         o        3
        u        4
         s        13
         t          1

 

Solution-

First, let us construct the Huffman tree using the steps we have learned above

 Step 01:

step 02:-

 

 

step 03:-

 

 

step 04:-

 

 

step 05:-

 

 

step 06:-

 

step 07:-

 

 

After we have constructed the Huffman tree, we will assign weights to all the edges. Let us assign weight ‘0’ to the left edges and weight ‘1’ to the right edges.

 

Note:

  • We can also assign weight ‘1’ to the left edges and weight ‘0’ to the right edges.
  • The only thing to keep in mind is that we must follow the same convention at the time of decoding which we adopted at the time of encoding.

After assigning weight ‘0’ to the left edges and weight ‘1’ to the right edges, we get-

 

 

 

1. Huffman code for the characters-

We will traverse the Huffman tree from the root node to all the leaf nodes one by one and and will write the Huffman code for all the characters-

 

  • a = 111
  • e = 10
  • i = 00
  • o = 11001
  • u = 1101
  • s = 01
  • t = 11000

From here, we can observe-

  • Characters occurring less frequently in the text are assigned the larger codes.
  • Characters occurring more frequently in the text are assigned the smaller codes.

2. Average code length-

We know,

Average code length  = ∑ ( frequencyi x code lengthi ) / ∑ ( frequencyi )

                                        = { (10 x 3) + (15 x 2) + (12 x 2) + (3 x 5) + (4 x 4) + (13 x 2) + (1 x 5) } / (10 + 15 + 12 + 3 + 4 + 13 + 1)

                                         = 2.52

 

3. Length of Huffman encoded message-

 

We know-

Total number of bits in Huffman encoded the message = Total number of characters in the message x Average code length per character

                                                                                                                   = 58 x 2.52

                                                                                                                    = 146.16

                                                                                                                      ≅ 147 bits

 

To gain a better understanding of the concepts and to practice more problems of Huffman Coding.

 

Answer
0Comment