Huffman Algorithm

Huffman coding is a lossless data compression algorithm and derives this table based on the estimated frequency of occurrence for each possible value of the source symbol.

Write a program to implement Huffman code for given string?

Algorithm Explanation

	Build Huffman Tree from input characters.
	Input an array of unique characters along with their frequency of occurrences and output to Huffman Tree.
	Create a leaf node for inserting each unique character and build a min heap of all leaf nodes. Extract two nodes with the minimum frequency from the minimum heap.
	Create new internal node with frequency is equal to the sum of the two nodes frequencies for each node in the heap
	Traverse the tree starting from the root and display the char and Huffman code.

Source Code

package com.dsacode.DataStructre.priorityqueue;
 
import java.util.PriorityQueue;
 
abstract class HuffmanTree implements Comparable < HuffmanTree > {
    public final int frequency;
    public HuffmanTree(int freq) { frequency = freq; }
  
    public int compareTo(HuffmanTree tree) {
        return frequency - tree.frequency;
    }
}
  
class HuffmanLeaf extends HuffmanTree {
    public final char value;
  
    public HuffmanLeaf(int freq, char val) {
        super(freq);
        value = val;
    }
}
  
class HuffmanNode extends HuffmanTree {
    public final HuffmanTree left, right;
  
    public HuffmanNode(HuffmanTree l, HuffmanTree r) {
        super(l.frequency + r.frequency);
        left = l;
        right = r;
    }
}
  
 
public class HuffmanPriorityQueue {
 
     
    public static HuffmanTree buildTree(int[] charFreqs) {
        PriorityQueue < HuffmanTree > trees = new PriorityQueue < HuffmanTree >();
     
        for (int i = 0; i < charFreqs.length; i++)
            if (charFreqs[i] > 0)
                trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));
  
         
        while (trees.size() > 1) {
            HuffmanTree a = trees.poll();
            HuffmanTree b = trees.poll();
            trees.offer(new HuffmanNode(a, b));
        }
        return trees.poll();
    }
  
    public static void printCodes(HuffmanTree tree, StringBuffer prefix) {
        assert tree != null;
        if (tree instanceof HuffmanLeaf) {
            HuffmanLeaf leaf = (HuffmanLeaf)tree;
            System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix);
        } else if (tree instanceof HuffmanNode) {
            HuffmanNode node = (HuffmanNode)tree;
 
            prefix.append('0');
            printCodes(node.left, prefix);
            prefix.deleteCharAt(prefix.length()-1);
  
            prefix.append('1');
            printCodes(node.right, prefix);
            prefix.deleteCharAt(prefix.length()-1);
        }
    }
  
    public static void main(String[] args) {
        String test = "Hello world";
  
        int[] charFreqs = new int[256];
 
        for (char c : test.toCharArray())
            charFreqs[c]++;
  
  
        HuffmanTree tree = buildTree(charFreqs);
  
  
        System.out.println("SYMBOL\tWEIGHT\tHUFFMAN CODE");
        printCodes(tree, new StringBuffer());
    }
}

Output

SYMBOL  WEIGHT  HUFFMAN CODE
o   2   00
e   1   010
d   1   011
l   3   10
    1   1100
w   1   1101
r   1   1110
H   1   1111