Huffman's Coding Greedy Algorithm

[5173 views]

What is Huffman's Coding Greedy Algorithm?

The prefix codes, means the codes (bit sequences) which are assigned in such a way that the code assigned to one character is not the prefix of code assigned to any other character. This is how the Huffman Coding makes sure that there is no ambiguity when decoding the generated bitstream.

Let us understand the prefix codes with a counter example. Let us consider four characters a, b, c and d, and their corresponding variable length codes be 00, 01, 0 and 1. This coding leads to ambiguity because code assigned to c is the prefix of codes which are assigned to a and b. If the compressed bit stream is 0001, the de-compressed output may be “cccd” or “ccb” or “acd” or “ab”.

Application of Huffman Coding:

Image Reference: Geeks for Geeks

Huffman's Coding Greedy Flowchart:

Image Reference:Geeks for Geeks

Huffman's Coding Greedy Pseudocode:

1. n=|C| 2. Q ? C 3. for i=1 to n-1 4. do 5. z= allocate-Node () 6. x= left[z]=Extract-Min(Q) 7. y= right[z] =Extract-Min(Q) 8. f [z]=f[x]+f[y] 9. Insert (Q, z) 10. return Extract-Min (Q)

Huffman's Coding Greedy Algorithm Implementation in Java:

import java.util.PriorityQueue; import java.util.Scanner; import java.util.Comparator; class HuffmanNode { int data; char c; HuffmanNode left; HuffmanNode right; } class MyComparator implements Comparator< HuffmanNode> { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } public class Huffman { public static void printCode(HuffmanNode root, String s) { /* If Condition to check for the condition */ if (root.left == null && root.right == null && Character.isLetter(root.c)) { System.out.println(root.c + ":" + s); return; } printCode(root.left, s + "0"); printCode(root.right, s + "1"); } // main function public static void main(String[] args) { Scanner s = new Scanner(System.in); // number of characters. int n = 6; /* Array to store the following characters */ char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' }; int[] charfreq = { 5, 9, 12, 13, 16, 45 }; // creating a priority queue q. // makes a min-priority queue(min-heap). PriorityQueue< HuffmanNode> q = new PriorityQueue< HuffmanNode>(n, new MyComparator()); /* Iteration of loop */ for (int i = 0; i < n; i++) { // creating a Huffman node object // and add it to the priority queue. HuffmanNode hn = new HuffmanNode(); hn.c = charArray[i]; hn.data = charfreq[i]; hn.left = null; hn.right = null; // add functions adds // the huffman node to the queue. q.add(hn); } // create a root node HuffmanNode root = null; // from the heap each time until // its size reduces to 1, extract until // all the nodes are extracted. while (q.size() > 1) { // first min extract. HuffmanNode x = q.peek(); q.poll(); // second min extarct. HuffmanNode y = q.peek(); q.poll(); // new node f which is equal HuffmanNode f = new HuffmanNode(); // to the sum of the frequency of the two nodes // assigning values to the f node. f.data = x.data + y.data; f.c = '-'; // first extracted node as left child. f.left = x; // second extracted node as the right child. f.right = y; root = f; // add this node to the priority-queue. q.add(f); } // print the codes by traversing the tree printCode(root, ""); } }