Huffman Coding – Letter Encoding using Huffman Tree

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:

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.

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).

  

• Include 3 in a frequency list and discard 1 and 2. The new frequency list is –

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).

• Include 6 and discard the letters with frequencies 3 and 3 from the frequency list.

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).

• Include 11 and discard the letters with frequencies 6 and 5 from the frequency list.

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

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.

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