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