Huffman Coding

Huffman coding is an important coding wherein,

1. Fixed the probability of each character
2. Arrange the character frequency in ascending order.
3. Create a new node where the left child is the lowest in the sorted list and the right child is the second lowest in the sorted list.
4. Chop of that two elements in the sorted list as they ate now part of one node and add the probabilities. The result is the probability of the new node.
5. Perform insertion sort on the list with the new node.
6. Repeat step 3, 4 and 5 until you have just one node left.

Huffman Coding Algorithm:

    Given an alphabetical 'A' with frequency distribution { f(a): a ∈ A }, the binary Huffman tree is constructed using priority 'Q', of nodes with frequencies as keys.
Huffman(A)
{
    n = |A|;
    Q = A;
    for i = 1 to n-1
    {
        z = new_node;
        left[z] = Extract_min(Q);
        right[z] = Ectract_min(Q);
        f[z] = f[left[z]] + f[right[z]];
        Insert(Q, Z);
    }
    return Extract_min(Q);
}

There is two variance of Huffman Coding:
1) Fixed Length Coding
2) Variable Length Coding

In Fixed Length Coding method, a fixed number of bits will be achieved for each character.
In Variable Length Coding method, the most frequently used character will have less number of bits while the least use character will be represented by more number of bits.