Huffman Coding-

· Huffman Coding is a popular Greedy algorithm.

· Used for non-loss of data compression.

· Uses code of variable length code.

· Provides a variable length code for all characters.

· The length of the character code depends on how often it appears in a given text.

· The character that occurs most often receives very little code.

· A character that occurs less often gets a much larger code.

· Also known as Huffman Encoding.

Basic Law-

Huffman Coding uses a law known as the origin code.

This is to protect against ambiguity while coding.

Ensures that the code assigned to any character is not the beginning of the code assigned to any other character.

Big Steps in Huffman Coding-

There are two major steps in Huffman Coding-

Creating a Huffman Tree from Input characters.

Giving character codes by crossing the Huffman Tree.

Huffman Tree-

The steps involved in building a Huffman Tree are as follows-

Step-01:

Create a leaf node for each letter of the text.

The character leaf code contains the recurring frequency of that character

Step-02:

Arrange all nodes according to the increasing frequency of their frequency.

Step-03:

Considering the first two nodes with low frequency,

Create a new internal node.

The frequency of this new node is the total frequency of those two nodes.

Create the first node as the left child and the other node as the right child for the newly created node.

Step-04:

Continue repeating Step-02 and Step-03 until all the nodes form a single tree.

The tree that was finally found is the desirable Huffman tree.

Time complexity

The time complexity analysis of Huffman Coding is as follows-

· extractMin( ) is called 2 x (n-1) times if there are n nodes.

· As extractMin( ) calls minHeapify( ), it takes O(logn) time.

Thus, Overall time complexity of Huffman Coding becomes O(nlogn).

Here, n is the number of unique characters in the given text.