Huff man Coding

HI GUYS!

In this blog we are going to discuss about Huffman coding and its working.

HUFFMAN CODING

Huffman coding is a technique to compress the data to smaller size without losing any details from that data. It is generally used to compress the data where characters are occurring frequently. This was first developed by David Huffman.

WORKING OF HUFFMAN CODING

Let the string below is to be sent over a network.

string

Each character occurs of 8 bits here in this example we have 15 characters given in above string. Thus, the total will be 8*15=120 bits. So, 120 bits will be required to send this string

Now using Huffman coding technique, we will compress this string to a smaller size to do so we have to create a tree using the frequency for the character and also have to generate codes for each character. This data will be encoded, then it has to be decode by using the same Huffaman tree this process will be done by using the concept of prefix code i.e. a code of a character should not be present in the prefix of any other code of a character.

THE STEPS FOR HUFFAMAN CODING:

1. we have to calculate the frequency of each character given in the string.

character with frequency

2. now we have to put all the frequency of given string in increasing order which are stored in priority queue.

frequency in increasing order

3. Now we have to make leaf node of each character

4. In this step we will assign minimum frequencies to the left child of the root node and right child to the maximum frequency.

5. Now we have to compare the root node with the character left within the string and minimum character will be added with that node.

6. We have to repeat this for all characters

7. Now for the tree we will be assigning the value 0 and 1 for each node

8. We will assign 0 to the left nodes and 1 to the right nodes.

Assign 0 to the left edge and 1 to the right edge

Assign 0 to the left edge and 1 to the right edge

Now the table given below is the result of the Huffman tree in which we have taken the values of code and the size of the particular character.

At first we have the total size of 120 bits. After encoding we are left with the size of 75 bits.

DECODING OF THE CODE

For decoding we have to traverse through the tree to find the character.

Let 101 is a code that we have to decode, in the figure given below we will find the character for it.

Decoding

Now here we can see that the code 101 is referred to the character D.

Huffman Coding Algorithm

Pseudocode for Huffman coding.

COMPLEXITY OF HUFFMAN

Based on the frequency the time complexity of the character is given by 0(nlog n).

The minimum frequency for the priority queue will be 2*(n-1)

APPLICATIONS OF HUFFMAN CODING

· It is used for text and fax transmissions.

· Used in compression formats like GZIP and PKZIP.