Huffman Coding Algorithm

In this tutorial, we’ll be discussing and implementing the Huffman Coding Algorithm in Java.

Huffman Coding

The Huffman Coding Algorithm was discovered by David A. Huffman in the 1950s. The purpose of the Algorithm is lossless data compression.

This algorithm is commonly used in JPEG Compression.

Now traditionally to encode/decode a string, we can use ASCII values. But this doesn’t compress it. The number of bits involved in encoding the string isn’t reduced.

Unlike ASCII codes, Huffman codes use lesser number of bits.

The principle of Huffman code is based on the frequency of each data item.

Every data item is assigned a variable length of prefix code (typically a binary string).

The length of each prefix code is based on the frequency such that the most commonly occurring data has the smallest prefix code.

No two different data items would have the same prefix. Hence the prefixes are known as Prefix Codes. This is important to make sure decoded string is the same as the original string.

The more often the data is used the lesser bits it takes up.

The Huffman algorithm is a greedy algorithm. Since at every stage it looks for the best available option.

A Disadvantage of Huffman codes is that a minor change in any bit of the encoded string would break the whole message.

The basic idea of the Huffman Algorithm is building a Tree from bottom up.

The steps involved in building the Huffman Tree are:

  • Get Frequency of each character and store it in a Map.
  • Create a node for each character with its frequency and insert it into a Min Priority Queue.
  • Extract the two nodes with the minimum frequency from the priority queue.
  • Create a new node by merging these two nodes as children and with weight equal to the sum of the two nodes frequencies.
  • Add this back to the Priority Queue.
  • Repeat till the Priority Queue has only one node left. That node becomes the root of the Huffman Tree.

Once the tree is built, to find the prefix code of each character we traverse the tree as:

  • Starting at the top when you go left, append 0 to the prefix code string.
  • When you go right, append 1.
  • Stop when you have reached the Leaf nodes.
  • The string of 0 and 1s created till now is the prefix code of that particular Node in the tree.

During decoding, we just need to print the character of each leaf traversed by the above prefix code in the Huffman tree.

All Input characters are present only in the leaves of the Huffman tree.

An example of a Huffman tree is given below:

huffman coding algorithm

The string to be encoded needs the prefix codes for all the characters built in a bottom-up manner.

The internal node of any two Nodes should have a non-character set to it.

Huffman Coding Algorithm Implementation

The code for the HuffmanNode class is given below:


class HuffmanNode implements Comparable<HuffmanNode> {
    int frequency;
    char data;
    HuffmanNode left, right;

    public int compareTo(HuffmanNode node) {
        return frequency - node.frequency;
    }
}

It holds the character and its frequency.

The comparable interface is implemented. This would be used when comparing the values in the PriorityQueue in order to get the minimum value always.

The code for the HuffmanCodeSolution.java class is given below:


package com.journaldev.huffmancoding;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

public class HuffmanCodeSolution {

	private static Map<Character, String> charPrefixHashMap = new HashMap<>();
	static HuffmanNode root;

	public static void main(String[] args) {

		String test = "ABCD1%$^";
		System.out.println("Original Text = "+test);
		String s = encode(test);
		decode(s);

	}

	private static HuffmanNode buildTree(Map<Character, Integer> freq) {

		PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>();
		Set<Character> keySet = freq.keySet();
		for (Character c : keySet) {

			HuffmanNode huffmanNode = new HuffmanNode();
			huffmanNode.data = c;
			huffmanNode.frequency = freq.get(c);
			huffmanNode.left = null;
			huffmanNode.right = null;
			priorityQueue.offer(huffmanNode);
		}
		assert priorityQueue.size() > 0;

		while (priorityQueue.size() > 1) {

			HuffmanNode x = priorityQueue.peek();
			priorityQueue.poll();

			HuffmanNode y = priorityQueue.peek();
			priorityQueue.poll();

			HuffmanNode sum = new HuffmanNode();

			sum.frequency = x.frequency + y.frequency;
			sum.data = '-';

			sum.left = x;

			sum.right = y;
			root = sum;

			priorityQueue.offer(sum);
		}

		return priorityQueue.poll();
	}


	private static void setPrefixCodes(HuffmanNode node, StringBuilder prefix) {

		if (node != null) {
			if (node.left == null && node.right == null) {
				charPrefixHashMap.put(node.data, prefix.toString());

			} else {
				prefix.append('0');
				setPrefixCodes(node.left, prefix);
				prefix.deleteCharAt(prefix.length() - 1);

				prefix.append('1');
				setPrefixCodes(node.right, prefix);
				prefix.deleteCharAt(prefix.length() - 1);
			}
		}

	}

	private static String encode(String test) {
		Map<Character, Integer> freq = new HashMap<>();
		for (int i = 0; i < test.length(); i++) {
			if (!freq.containsKey(test.charAt(i))) {
				freq.put(test.charAt(i), 0);
			}
			freq.put(test.charAt(i), freq.get(test.charAt(i)) + 1);
		}

		System.out.println("Character Frequency Map = " + freq);
		root = buildTree(freq);

		setPrefixCodes(root, new StringBuilder());
		System.out.println("Character Prefix Map = " + charPrefixHashMap);
		StringBuilder s = new StringBuilder();

		for (int i = 0; i < test.length(); i++) {
			char c = test.charAt(i);
			s.append(charPrefixHashMap.get(c));
		}

		return s.toString();
	}

	private static void decode(String s) {

		StringBuilder stringBuilder = new StringBuilder();

		HuffmanNode temp = root;

		System.out.println("Encoded: " + s);

		for (int i = 0; i < s.length(); i++) {
			int j = Integer.parseInt(String.valueOf(s.charAt(i)));

			if (j == 0) {
				temp = temp.left;
				if (temp.left == null && temp.right == null) {
					stringBuilder.append(temp.data);
					temp = root;
				}
			}
			if (j == 1) {
				temp = temp.right;
				if (temp.left == null && temp.right == null) {
					stringBuilder.append(temp.data);
					temp = root;
				}
			}
		}

		System.out.println("Decoded string is " + stringBuilder.toString());

	}
}

class HuffmanNode implements Comparable<HuffmanNode> {
	int frequency;
	char data;
	HuffmanNode left, right;

	public int compareTo(HuffmanNode node) {
		return frequency - node.frequency;
	}
}

So our string to be compressed and encoded/decoded is “ABA11$A”.

In encoding method we store the frequencies of each character in a map first.

Then we call the buildTree method using the approach discussed before.

We save the prefix code for each character in a HashMap inside the setPrefixCode method.

In the decode method, we just traverse the encoded string left or right based on 0 or 1. Once we reach the leaf, we append that leaf data to the StringBuilder and again start from the top for the remaining encoded string.

Following is the output of the above program:

Huffman Coding Algorithm Implementation Example

You can checkout complete code and more DS & Algorithm examples from our GitHub Repository.

Reference: Wikipedia

Comments

  1. Giov anni says:

    Is this the adaptive or static one ?

  2. Gio Vanni says:

    Is this the adaptive Huffman code or the static one ?

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages