Huffman Coding – Letter Encoding using Huffman Tree

In the previous article, we learned about the Huffman Tree and Algorithm in Data Structures, In this article, we will learn about the Huffman coding in Data Structures.

252

An important application of the Huffman Tree is coding letters or other elements such as pixels in the minimum possible space. This application of coding the symbols is called Huffman Coding. The result of coding comes out to be the compressed string.

Huffman Coding Example

Suppose we have five letters A, B, C, D, and E with their frequencies of occurrence in a particular string, say, BAACDEBAADDCAACDD. Suppose all the letters are of a fixed size of 4 bits each with the following values:

Letter Code in bits
A 1010
B 1110
C 0101
D 1100
E 0011

The above string will be decoded as –

1110 1010 1010 0101 1100 0011 1110 1010 1010 1100 1100 0101 1010 1010 0101 1100 1100

Then the total length of the coded string = (letters of string) * (size of a letter)

                                                                       = 17*4

                                                                       = 68.

Instead of giving a fixed size length to each letter, it will be better to give a variable number of bits, which will drastically reduce the size of a code.

In the above string, suppose the weightage of the letter is given, depending upon their frequencies to occur, for example, the letter ‘A’ occurs 6 times in the string.

Letter A B C D E
Frequency 6 2 3 5 1

Construct a Huffman tree from the above table :

  • Two least frequencies are 1 and 2 of E and V respectively. Draw a tree with (1 + 2 = 3).

    huffman tree 1
    Huffman tree 1
  • Include 3 in a frequency list and discard 1 and 2. The new frequency list is –
Letter N A C D
Frequency 3 6 3 5

Choose two letters N (newly added to the list) and C with least frequencies 3 and 3 respectively. Draw a tree with (3+3 = 6).

huffman tree 2
Huffman tree 2
  • Include 6 and discard the letters with frequencies 3 and 3 from the frequency list.
Letter N A D
Frequency 6 6 5

Choose two letters N ( add newly in the list) and D with least frequencies 6 and 5 respectively. Draw a tree with (6+5 = 11).

huffman tree 3

  • Include 11 and discard the letters with frequencies 6 and 5 from the frequency list.
Letter N A
Frequency 11 6

Draw a tree with (11 + 6 = 17).

huffman tree 4

Suppose moving left one level will give a value 0 and moving right one level will give a value 1. Draw the table of letters with codes with the help of a defined rule from the Huffman Tree.

Letter Code
A 0
B 0001
C 001
D 01
E 0000

The code for the string (earlier mentioned) BAACDEBAADDCAACDD will be 001 0 0 001 01 0000 0001 0 0 01 01 001 0 0 001 01 01. This time the length of the Huffman code is drastically reduced to size of 37 bits, much less than the fixed size code of 68 bits. It is quite obvious that this variable length code is optimally compressed to almost half the fixed length code.

So, in this article, we learned about one of the very useful applications of Huffman Coding. This encoding is used widely all over the world and is quite popular.

Attempt Free Data Structures MCQ Test

Previous QuizHuffman Tree and Huffman Algorithm
Next QuizKth smallest element using quick select algorithm

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.