Skip to main content

Hamming decoding example

Implementation of Hamming decoding using a priority queue in Java. Hamming codes are a type of error-correcting code used to detect and correct single-bit errors in data transmission. This example demonstrates how to decode Hamming-encoded data using a Huffman tree-based approach.

Problem Statement

The task involves decoding Hamming-encoded data using a priority queue and a Huffman tree. Given a Hamming-encoded string and a Huffman tree, the goal is to decode the original data by traversing the tree based on the encoded bits.

Explanation with an Example

Suppose you have a Hamming-encoded string: "1110100100111111111011011010110000" and a Huffman tree built from a given dataset. The goal is to decode the Hamming-encoded string to retrieve the original data.

Idea to Solve

To solve this problem, the code constructs a Huffman tree using a given dataset and then uses this tree to decode the Hamming-encoded string. It decodes the Hamming-encoded data by traversing the Huffman tree based on the bits of the encoded string. Whenever it reaches a leaf node in the tree, it records the corresponding character and continues traversal from the root.

Pseudocode

TreeNode class:
    Define a class TreeNode with integer frequency, char data, left, and right attributes

QNode class:
    Define a class QNode with TreeNode node, next, and prev attributes

PriorityQueue class:
    Define a class PriorityQueue with QNode front, rear, and size attributes
    Implement enQueue, isEmpty, peek, deQueue, printQdata methods

HuffmanCodes class:
    Implement printTree method to print the Huffman tree and their codes
    Implement buildHuffmanCodes method to build the Huffman tree using a priority queue
    Implement getCode method to get the codes for each character in the tree
    Implement enCodingText method to encode the given text using the Huffman tree
    Implement deCodingText method to decode the Hamming-encoded text using the Huffman tree

Main:
    Create an instance of HuffmanCodes
    Given input data as a Hamming-encoded string
    Construct Huffman tree using the given data
    Get encode using the Huffman tree
    Get decode using Hamming-encoded string and the Huffman tree
    Display the original data, Huffman tree, encode, and decode

Algorithm Explanation

  1. Create a TreeNode class to represent nodes in the Huffman tree.
  2. Create a QNode class to represent nodes in the priority queue.
  3. Create a PriorityQueue class to implement priority queue operations.
  4. Create a HuffmanCodes class to implement methods for building the Huffman tree, getting codes, encoding text, and decoding text.
  5. Inside the main method, create an instance of HuffmanCodes and given input Hamming-encoded data.
  6. Build the Huffman tree using the given data.
  7. Encode the original data using the Huffman tree and get the encoded string.
  8. Decode the Hamming-encoded string using the Huffman tree and get the decoded data.
  9. Display the original data, the Huffman tree with codes, the encoded string, and the decoded data.

Code Solution

/*
    Java Program 
    Hamming decoding example
*/
import java.util.HashMap;
import java.util.Map;
class TreeNode
{
	public int first;
	public char second;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int first, char second)
	{
		this.first = first;
		this.second = second;
		this.left = null;
		this.right = null;
	}
}
class QNode
{
	public TreeNode n;
	public QNode next;
	public QNode prev;
	public QNode(TreeNode n)
	{
		this.n = n;
		this.prev = null;
		this.next = null;
	}
}
class PriorityQueue
{
	public QNode front;
	public QNode rear;
	public int size;
	public PriorityQueue()
	{
		this.front = null;
		this.rear = null;
		this.size = 0;
	}
	// Add a node into queue Priority queue
	public void enQueue(TreeNode auxiliary)
	{
		//Create a dynamic node
		QNode node = new QNode(auxiliary);
		node.n = auxiliary;
		if (this.front == null)
		{
			// When adding a first node of queue
			this.front = node;
			this.rear = node;
		}
		else if (this.front.n.first >= auxiliary.first)
		{
			// Add node at beginning position
			node.next = this.front;
			this.front.prev = node;
			this.front = node;
		}
		else if (this.rear.n.first <= auxiliary.first)
		{
			// Add node at last position
			node.prev = this.rear;
			this.rear.next = node;
			this.rear = node;
		}
		else
		{
			QNode temp = this.front;
			// Find the location of inserting priority node
			while (temp.n.first < auxiliary.first)
			{
				temp = temp.next;
			}
			// Add node
			node.next = temp;
			node.prev = temp.prev;
			temp.prev = node;
			if (node.prev != null)
			{
				node.prev.next = node;
			}
		}
		this.size = this.size + 1;
	}
	public boolean isEmpty()
	{
		if (this.size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Get a front element of queue
	public TreeNode peek()
	{
		if (this.isEmpty() == true)
		{
			System.out.print("\n Empty Queue \n");
			// When Queue is empty
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
	public int isSize()
	{
		return this.size;
	}
	// Remove a front node of a queue
	public void deQueue()
	{
		if (this.isEmpty() == false)
		{
			QNode temp = this.front;
			if (this.front == this.rear)
			{
				// When queue contains only one node
				this.rear = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
				this.front.prev = null;
			}
			// Change queue size
			this.size--;
		}
	}
	// Print elements of queue
	public void printQdata()
	{
		QNode node = this.front;
		System.out.print("\n Queue Element ");
		while (node != null)
		{
			System.out.print("\n " + node.n.first + " " + node.n.second);
			node = node.next;
		}
		System.out.print("\n");
	}
}
public class HuffmanCodes
{
	// Display Huffman code
	public void printTree(TreeNode node, String result)
	{
		if (node == null)
		{
			return;
		}
		if (node.left == null && node.right == null)
		{
			System.out.print("\n " + node.second + " " + node.first + " : " + result);
			return;
		}
		printTree(node.left, result + "0");
		printTree(node.right, result + "1");
	}
	// Construct Huffman Code Tree
	public TreeNode buildHuffmanCodes(String data, int n)
	{
		PriorityQueue q = new PriorityQueue();
		TreeNode root = null;
		TreeNode n1 = null;
		TreeNode n2 = null;
		int i = 0;
		// Use to get A to Z character
		int[] frequency = new int[26];
		for (i = 0; i < 26; ++i)
		{
			frequency[i] = 0;
		}
		for (i = 0; i < n; ++i)
		{
			frequency[data.charAt(i) - 'A']++;
		}
		// First add all elements into priority queue
		for (i = 0; i < 26; ++i)
		{
			if (frequency[i] > 0)
			{
				root = new TreeNode(frequency[i], (char)(i + 65));
				q.enQueue(root);
			}
		}
		// q.printQdata();
		// Execute loop until the priority queue contains more than 1 node
		while (q.isSize() > 1)
		{
			// Get first smallest node  
			n1 = q.peek();
			//Remove a front element
			q.deQueue();
			// Get second smallest node
			n2 = q.peek();
			// Remove a front element
			q.deQueue();
			// Make new node using two smallest node
			root = new TreeNode(n1.first + n2.first, ' ');
			// Add new node into priority queue 
			q.enQueue(root);
			// Set left and right child
			root.left = n1;
			root.right = n2;
		}
		q.deQueue();
		return root;
	}
	// Put the leaf node information  to given map
	public void getCode(TreeNode node, Map < Character, String > m, String result)
	{
		if (node == null)
		{
			return;
		}
		if (node.left == null && node.right == null)
		{
			// Add Initialize leaf node value and generated code result
			m.put(node.second, result);
			return;
		}
		// Recursively, visiting left and right subtree to select
		getCode(node.left, m, result + "0");
		getCode(node.right, m, result + "1");
	}
	// Get encoding text by using generated tree
	public String enCodingText(TreeNode root, String data, int n)
	{
		Map < Character, String > map = new HashMap < > ();
		// Find the path from root to leaf nodes
		getCode(root, map, "");
		String encode = "";
		for (int i = 0; i < n; i++)
		{
			encode += map.get(data.charAt(i));
		}
		return encode;
	}
	// Returns the decode of given encode and tree
	public String deCodingText(TreeNode root, String encode)
	{
		int n = encode.length();
		String decode = "";
		TreeNode auxiliary = root;
		// Execute loop through by encode length
		for (int i = 0; i < n; i++)
		{
			if (encode.charAt(i) == '0')
			{
				// Visit to left child
				auxiliary = auxiliary.left;
			}
			else
			{
				// Visit to right child
				auxiliary = auxiliary.right;
			}
			if (auxiliary.left == null && auxiliary.right == null)
			{
				// When get leaf node
				decode += auxiliary.second;
				// Start with root of tree
				auxiliary = root;
			}
		}
		// Return decoded text
		return decode;
	}
	public static void main(String[] args)
	{
		HuffmanCodes task = new HuffmanCodes();
		// Given input data
		String data = "ABEECAAAABBBEAEEEE";
		int n = data.length();
		// Construct  Tree
		TreeNode root = task.buildHuffmanCodes(data, n);
		// Get encode
		String encode = task.enCodingText(root, data, n);
		// Get decode using encode
		String decode = task.deCodingText(root, encode);
		// Display result
		System.out.print("\n Data : " + data);
		//  Print all leaf node information
		task.printTree(root, "");
		// Display encode text
		System.out.print("\n Encode : " + encode);
		// Display decode text
		System.out.print("\n Decode : " + decode);
	}
}

Output

 Data : ABEECAAAABBBEAEEEE
 E 7 : 0
 C 1 : 100
 B 4 : 101
 A 6 : 11
 Encode : 1110100100111111111011011010110000
 Decode : ABEECAAAABBBEAEEEE
// Include header file
#include <iostream>
#include <map> 
#include <string.h>
using namespace std;
/*
    C++ Program 
    Hamming decoding example
*/
class TreeNode
{
	public: 
    int first;
	char second;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int first, char second)
	{
		this->first = first;
		this->second = second;
		this->left = NULL;
		this->right = NULL;
	}
};
class QNode
{
	public: TreeNode *n;
	QNode *next;
	QNode *prev;
	QNode(TreeNode *n)
	{
		this->n = n;
		this->prev = NULL;
		this->next = NULL;
	}
};
class PriorityQueue
{
	public: QNode *front;
	QNode *rear;
	int size;
	PriorityQueue()
	{
		this->front = NULL;
		this->rear = NULL;
		this->size = 0;
	}
	// Add a node into queue Priority queue
	void enQueue(TreeNode *auxiliary)
	{
		//Create a dynamic node
		QNode *node = new QNode(auxiliary);
		node->n = auxiliary;
		if (this->front == NULL)
		{
			// When adding a first node of queue
			this->front = node;
			this->rear = node;
		}
		else if (this->front->n->first >= auxiliary->first)
		{
			// Add node at beginning position
			node->next = this->front;
			this->front->prev = node;
			this->front = node;
		}
		else if (this->rear->n->first <= auxiliary->first)
		{
			// Add node at last position
			node->prev = this->rear;
			this->rear->next = node;
			this->rear = node;
		}
		else
		{
			QNode *temp = this->front;
			// Find the location of inserting priority node
			while (temp->n->first < auxiliary->first)
			{
				temp = temp->next;
			}
			// Add node
			node->next = temp;
			node->prev = temp->prev;
			temp->prev = node;
			if (node->prev != NULL)
			{
				node->prev->next = node;
			}
		}
		this->size = this->size + 1;
	}
	bool isEmpty()
	{
		if (this->size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Get a front element of queue
	TreeNode *peek()
	{
		if (this->isEmpty() == true)
		{
			// When Queue is empty
			cout << "\n Empty Queue \n";
			return NULL;
		}
		else
		{
			return this->front->n;
		}
	}
	int isSize()
	{
		return this->size;
	}
	// Remove a front node of a queue
	void deQueue()
	{
		if (this->isEmpty() == false)
		{
			QNode *temp = this->front;
			if (this->front == this->rear)
			{
				// When queue contains only one node
				this->rear = NULL;
				this->front = NULL;
			}
			else
			{
				this->front = this->front->next;
				this->front->prev = NULL;
			}
			// Change queue size
			this->size--;
		}
	}
	// Print elements of queue
	void printQdata()
	{
		QNode *node = this->front;
		cout << "\n Queue Element ";
		while (node != NULL)
		{
			cout << "\n " << node->n->first << " " << node->n->second;
			node = node->next;
		}
		cout << "\n";
	}
};
class HuffmanCodes
{
	public:
		// Display Huffman code
		void printTree(TreeNode *node, string result)
		{
			if (node == NULL)
			{
				return;
			}
			if (node->left == NULL && node->right == NULL)
			{
				cout << "\n " << node->second << " " << node->first << " : " << result;
				return;
			}
			this->printTree(node->left, result + "0");
			this->printTree(node->right, result + "1");
		}
	// Construct Huffman Code Tree
	TreeNode *buildHuffmanCodes(string data, int n)
	{
		PriorityQueue q = PriorityQueue();
		TreeNode *root = NULL;
		TreeNode *n1 = NULL;
		TreeNode *n2 = NULL;
		int i = 0;
		// Use to get A to Z character
		int frequency[26];
		for (i = 0; i < 26; ++i)
		{
			frequency[i] = 0;
		}
		for (i = 0; i < n; ++i)
		{
			frequency[data[i] - 'A']++;
		}
		// First add all elements into priority queue
		for (i = 0; i < 26; ++i)
		{
			if (frequency[i] > 0)
			{
				root = new TreeNode(frequency[i], (char)(i + 65));
				q.enQueue(root);
			}
		}
		// q.printQdata();
		// Execute loop until the priority queue contains more than 1 node
		while (q.isSize() > 1)
		{
			// Get first smallest node
			n1 = q.peek();
			//Remove a front element
			q.deQueue();
			// Get second smallest node
			n2 = q.peek();
			// Remove a front element
			q.deQueue();
			// Make new node using two smallest node
			root = new TreeNode(n1->first + n2->first, ' ');
			// Add new node into priority queue
			q.enQueue(root);
			// Set left and right child
			root->left = n1;
			root->right = n2;
		}
		q.deQueue();
		return root;
	}
	// Put the leaf node information  to given map
	void getCode(TreeNode *node, map< char, string > &m, string result)
	{
		if (node == NULL)
		{
			return;
		}
		if (node->left == NULL && node->right == NULL)
		{
			// Add Initialize leaf node value and generated code result
          	m[node->second] = result;
			return;
		}
		// Recursively, visiting left and right subtree to select
		this->getCode(node->left, m, result + "0");
		this->getCode(node->right, m, result + "1");
	}
	// Get encoding text by using generated tree
	string enCodingText(TreeNode *root, string data, int n)
	{
		map< char, string > m;
		// Find the path from root to leaf nodes
		this->getCode(root, m, "");
		string encode = "";
		for (int i = 0; i < n; i++)
		{
			encode += m[data[i]];
		}
		return encode;
	}
	// Returns the decode of given encode and tree
	string deCodingText(TreeNode *root, string encode)
	{
		// Return decoded text
		int n = encode.size();
		string decode = "";
		TreeNode *auxiliary = root;
		// Execute loop through by encode length
		for (int i = 0; i < n; i++)
		{
			if (encode[i] == '0')
			{
				// Visit to left child
				auxiliary = auxiliary->left;
			}
			else
			{
				// Visit to right child
				auxiliary = auxiliary->right;
			}
			if (auxiliary->left == NULL && auxiliary->right == NULL)
			{
				// When get leaf node
				decode += auxiliary->second;
				// Start with root of tree
				auxiliary = root;
			}
		}
		return decode;
	}
};
int main()
{
	HuffmanCodes task = HuffmanCodes();
	// Given input data
	string data = "ABEECAAAABBBEAEEEE";
	int n = data.size();
	// Construct  Tree
	TreeNode *root = task.buildHuffmanCodes(data, n);
	// Get encode
	string encode = task.enCodingText(root, data, n);
	// Get decode using encode
	string decode = task.deCodingText(root, encode);
	// Display result
	cout << "\n Data : " << data;
	//  Print all leaf node information
	task.printTree(root, "");
	// Display encode text
	cout << "\n Encode : " << encode;
	// Display decode text
	cout << "\n Decode : " << decode;
	return 0;
}

Output

 Data : ABEECAAAABBBEAEEEE
 E 7 : 0
 C 1 : 100
 B 4 : 101
 A 6 : 11
 Encode : 1110100100111111111011011010110000
 Decode : ABEECAAAABBBEAEEEE
// Include namespace system
using System;
using System.Collections.Generic;
/*
    C# Program 
    Hamming decoding example
*/
public class TreeNode
{
	public int first;
	public char second;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int first, char second)
	{
		this.first = first;
		this.second = second;
		this.left = null;
		this.right = null;
	}
}
public class QNode
{
	public TreeNode n;
	public QNode next;
	public QNode prev;
	public QNode(TreeNode n)
	{
		this.n = n;
		this.prev = null;
		this.next = null;
	}
}
public class PriorityQueue
{
	public QNode front;
	public QNode rear;
	public int size;
	public PriorityQueue()
	{
		this.front = null;
		this.rear = null;
		this.size = 0;
	}
	// Add a node into queue Priority queue
	public void enQueue(TreeNode auxiliary)
	{
		//Create a dynamic node
		QNode node = new QNode(auxiliary);
		node.n = auxiliary;
		if (this.front == null)
		{
			// When adding a first node of queue
			this.front = node;
			this.rear = node;
		}
		else if (this.front.n.first >= auxiliary.first)
		{
			// Add node at beginning position
			node.next = this.front;
			this.front.prev = node;
			this.front = node;
		}
		else if (this.rear.n.first <= auxiliary.first)
		{
			// Add node at last position
			node.prev = this.rear;
			this.rear.next = node;
			this.rear = node;
		}
		else
		{
			QNode temp = this.front;
			// Find the location of inserting priority node
			while (temp.n.first < auxiliary.first)
			{
				temp = temp.next;
			}
			// Add node
			node.next = temp;
			node.prev = temp.prev;
			temp.prev = node;
			if (node.prev != null)
			{
				node.prev.next = node;
			}
		}
		this.size = this.size + 1;
	}
	public Boolean isEmpty()
	{
		if (this.size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Get a front element of queue
	public TreeNode peek()
	{
		if (this.isEmpty() == true)
		{
			// When Queue is empty
			Console.Write("\n Empty Queue \n");
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
	public int isSize()
	{
		return this.size;
	}
	// Remove a front node of a queue
	public void deQueue()
	{
		if (this.isEmpty() == false)
		{
			QNode temp = this.front;
          	temp.n = null;
			if (this.front == this.rear)
			{
				// When queue contains only one node
				this.rear = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
				this.front.prev = null;
			}
			// Change queue size
			this.size--;
		}
	}
	// Print elements of queue
	public void printQdata()
	{
		QNode node = this.front;
		Console.Write("\n Queue Element ");
		while (node != null)
		{
			Console.Write("\n " + node.n.first + " " + node.n.second);
			node = node.next;
		}
		Console.Write("\n");
	}
}
public class HuffmanCodes
{
	// Display Huffman code
	public void printTree(TreeNode node, String result)
	{
		if (node == null)
		{
			return;
		}
		if (node.left == null && node.right == null)
		{
			Console.Write("\n " + node.second + " " + node.first + " : " + result);
			return;
		}
		printTree(node.left, result + "0");
		printTree(node.right, result + "1");
	}
	// Construct Huffman Code Tree
	public TreeNode buildHuffmanCodes(String data, int n)
	{
		PriorityQueue q = new PriorityQueue();
		TreeNode root = null;
		TreeNode n1 = null;
		TreeNode n2 = null;
		int i = 0;
		// Use to get A to Z character
		int[] frequency = new int[26];
		for (i = 0; i < 26; ++i)
		{
			frequency[i] = 0;
		}
		for (i = 0; i < n; ++i)
		{
			frequency[data[i] - 'A']++;
		}
		// First add all elements into priority queue
		for (i = 0; i < 26; ++i)
		{
			if (frequency[i] > 0)
			{
				root = new TreeNode(frequency[i], (char)(i + 65));
				q.enQueue(root);
			}
		}
		// q.printQdata();
		// Execute loop until the priority queue contains more than 1 node
		while (q.isSize() > 1)
		{
			// Get first smallest node
			n1 = q.peek();
			//Remove a front element
			q.deQueue();
			// Get second smallest node
			n2 = q.peek();
			// Remove a front element
			q.deQueue();
			// Make new node using two smallest node
			root = new TreeNode(n1.first + n2.first, ' ');
			// Add new node into priority queue
			q.enQueue(root);
			// Set left and right child
			root.left = n1;
			root.right = n2;
		}
		q.deQueue();
		return root;
	}
	// Put the leaf node information  to given map
	public void getCode(TreeNode node, Dictionary <char, String> m, String result)
	{
		if (node == null)
		{
			return;
		}
		if (node.left == null && node.right == null)
		{
			// Add Initialize leaf node value and generated code result
			m[node.second] = result;
			return;
		}
		// Recursively, visiting left and right subtree to select
		getCode(node.left, m, result + "0");
		getCode(node.right, m, result + "1");
	}
	// Get encoding text by using generated tree
	public String enCodingText(TreeNode root, String data, int n)
	{
        Dictionary <char, String> map = new Dictionary < char, String> ();
		
		// Find the path from root to leaf nodes
		getCode(root, map, "");
		String encode = "";
		for (int i = 0; i < n; i++)
		{
			encode += map[data[i]];
		}
		return encode;
	}
	// Returns the decode of given encode and tree
	public String deCodingText(TreeNode root, String encode)
	{
		// Return decoded text
		int n = encode.Length;
		String decode = "";
		TreeNode auxiliary = root;
		// Execute loop through by encode length
		for (int i = 0; i < n; i++)
		{
			if (encode[i] == '0')
			{
				// Visit to left child
				auxiliary = auxiliary.left;
			}
			else
			{
				// Visit to right child
				auxiliary = auxiliary.right;
			}
			if (auxiliary.left == null && auxiliary.right == null)
			{
				// When get leaf node
				decode += auxiliary.second;
				// Start with root of tree
				auxiliary = root;
			}
		}
		return decode;
	}
	public static void Main(String[] args)
	{
		HuffmanCodes task = new HuffmanCodes();
		// Given input data
		String data = "ABEECAAAABBBEAEEEE";
		int n = data.Length;
		// Construct  Tree
		TreeNode root = task.buildHuffmanCodes(data, n);
		// Get encode
		String encode = task.enCodingText(root, data, n);
		// Get decode using encode
		String decode = task.deCodingText(root, encode);
		// Display result
		Console.Write("\n Data : " + data);
		//  Print all leaf node information
		task.printTree(root, "");
		// Display encode text
		Console.Write("\n Encode : " + encode);
		// Display decode text
		Console.Write("\n Decode : " + decode);
	}
}

Output

 Data : ABEECAAAABBBEAEEEE
 E 7 : 0
 C 1 : 100
 B 4 : 101
 A 6 : 11
 Encode : 1110100100111111111011011010110000
 Decode : ABEECAAAABBBEAEEEE
<?php
/*
    Php Program 
    Hamming decoding example
*/
class TreeNode
{
	public $first;
	public $second;
	public $left;
	public $right;

	function __construct($first, $second)
	{
		$this->first = $first;
		$this->second = $second;
		$this->left = null;
		$this->right = null;
	}
}
class QNode
{
	public $n;
	public $next;
	public $prev;

	function __construct($n)
	{
		$this->n = $n;
		$this->prev = null;
		$this->next = null;
	}
}
class PriorityQueue
{
	public $front;
	public $rear;
	public $size;

	function __construct()
	{
		$this->front = null;
		$this->rear = null;
		$this->size = 0;
	}
	// Add a node into queue Priority queue
	public	function enQueue($auxiliary)
	{
		//Create a dynamic node
		$node = new QNode($auxiliary);
		$node->n = $auxiliary;
		if ($this->front == null)
		{
			// When adding a first node of queue
			$this->front = $node;
			$this->rear = $node;
		}
		else if ($this->front->n->first >= $auxiliary->first)
		{
			// Add node at beginning position
			$node->next = $this->front;
			$this->front->prev = $node;
			$this->front = $node;
		}
		else if ($this->rear->n->first <= $auxiliary->first)
		{
			// Add node at last position
			$node->prev = $this->rear;
			$this->rear->next = $node;
			$this->rear = $node;
		}
		else
		{
			$temp = $this->front;
			// Find the location of inserting priority node
			while ($temp->n->first < $auxiliary->first)
			{
				$temp = $temp->next;
			}
			// Add node
			$node->next = $temp;
			$node->prev = $temp->prev;
			$temp->prev = $node;
			if ($node->prev != null)
			{
				$node->prev->next = $node;
			}
		}
		$this->size = $this->size + 1;
	}
	public	function isEmpty()
	{
		if ($this->size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Get a front element of queue
	public	function peek()
	{
		if ($this->isEmpty() == true)
		{
			// When Queue is empty
			echo "\n Empty Queue \n";
			return null;
		}
		else
		{
			return $this->front->n;
		}
	}
	public	function isSize()
	{
		return $this->size;
	}
	// Remove a front node of a queue
	public	function deQueue()
	{
		if ($this->isEmpty() == false)
		{
			$temp = $this->front;
			$temp->n = null;
			if ($this->front == $this->rear)
			{
				// When queue contains only one node
				$this->rear = null;
				$this->front = null;
			}
			else
			{
				$this->front = $this->front->next;
				$this->front->prev = null;
			}
			// Change queue size
			$this->size--;
		}
	}
	// Print elements of queue
	public	function printQdata()
	{
		$node = $this->front;
		echo "\n Queue Element ";
		while ($node != null)
		{
			echo "\n ". $node->n->first ." ". $node->n->second;
			$node = $node->next;
		}
		echo "\n";
	}
}
class HuffmanCodes
{
	// Display Huffman code
	public	function printTree($node, $result)
	{
		if ($node == null)
		{
			return;
		}
		if ($node->left == null && $node->right == null)
		{
			echo "\n ". $node->second ." ". $node->first ." : ". $result;
			return;
		}
		$this->printTree($node->left, $result ."0");
		$this->printTree($node->right, $result ."1");
	}
	// Construct Huffman Code Tree
	public	function buildHuffmanCodes($data, $n)
	{
		$q = new PriorityQueue();
		$root = null;
		$n1 = null;
		$n2 = null;
		$i = 0;
		// Use to get A to Z character
		$frequency = array_fill(0, 26, 0);
	
		for ($i = 0; $i < $n; ++$i)
		{
			$frequency[ord($data[$i]) - ord('A')]++;
		}
		// First add all elements into priority queue
		for ($i = 0; $i < 26; ++$i)
		{
			if ($frequency[$i] > 0)
			{
				$root = new TreeNode($frequency[$i], chr($i + 65));
				$q->enQueue($root);
			}
		}
		// q.printQdata();
		// Execute loop until the priority queue contains more than 1 node
		while ($q->isSize() > 1)
		{
			// Get first smallest node
			$n1 = $q->peek();
			//Remove a front element
			$q->deQueue();
			// Get second smallest node
			$n2 = $q->peek();
			// Remove a front element
			$q->deQueue();
			// Make new node using two smallest node
			$root = new TreeNode($n1->first + $n2->first, ' ');
			// Add new node into priority queue
			$q->enQueue($root);
			// Set left and right child
			$root->left = $n1;
			$root->right = $n2;
		}
		$q->deQueue();
		return $root;
	}
	// Put the leaf node information  to given map
	public	function getCode($node, &$m, $result)
	{
		if ($node == null)
		{
			return;
		}
		if ($node->left == null && $node->right == null)
		{
			// Add Initialize leaf node value and generated code result
			$m[$node->second] = $result;
			return;
		}
		// Recursively, visiting left and right subtree to select
		$this->getCode($node->left, $m, $result ."0");
		$this->getCode($node->right, $m, $result ."1");
	}
	// Get encoding text by using generated tree
	public	function enCodingText($root, $data, $n)
	{
		$map = array();
		// Find the path from root to leaf nodes
		$this->getCode($root, $map, "");
		$encode = "";
		for ($i = 0; $i < $n; $i++)
		{
			$encode .= $map[$data[$i]];
		}
		return $encode;
	}
	// Returns the decode of given encode and tree
	public	function deCodingText($root, $encode)
	{
		// Return decoded text
		$n = strlen($encode);
		$decode = "";
		$auxiliary = $root;
		// Execute loop through by encode length
		for ($i = 0; $i < $n; $i++)
		{
			if ($encode[$i] == '0')
			{
				// Visit to left child
				$auxiliary = $auxiliary->left;
			}
			else
			{
				// Visit to right child
				$auxiliary = $auxiliary->right;
			}
			if ($auxiliary->left == null && $auxiliary->right == null)
			{
				// When get leaf node
				$decode .= $auxiliary->second;
				// Start with root of tree
				$auxiliary = $root;
			}
		}
		return $decode;
	}
}

function main()
{
	$task = new HuffmanCodes();
	// Given input data
	$data = "ABEECAAAABBBEAEEEE";
	$n = strlen($data);
	// Construct  Tree
	$root = $task->buildHuffmanCodes($data, $n);
	// Get encode
	$encode = $task->enCodingText($root, $data, $n);
	// Get decode using encode
	$decode = $task->deCodingText($root, $encode);
	// Display result
	echo "\n Data : ". $data;
	//  Print all leaf node information
	$task->printTree($root, "");
	// Display encode text
	echo "\n Encode : ". $encode;
	// Display decode text
	echo "\n Decode : ". $decode;
}
main();

Output

 Data : ABEECAAAABBBEAEEEE
 E 7 : 0
 C 1 : 100
 B 4 : 101
 A 6 : 11
 Encode : 1110100100111111111011011010110000
 Decode : ABEECAAAABBBEAEEEE
/*
    Node Js Program 
    Hamming decoding example
*/
class TreeNode
{
	constructor(first, second)
	{
		this.first = first;
		this.second = second;
		this.left = null;
		this.right = null;
	}
}
class QNode
{
	constructor(n)
	{
		this.n = n;
		this.prev = null;
		this.next = null;
	}
}
class PriorityQueue
{
	constructor()
	{
		this.front = null;
		this.rear = null;
		this.size = 0;
	}
	// Add a node into queue Priority queue
	enQueue(auxiliary)
	{
		//Create a dynamic node
		var node = new QNode(auxiliary);
		node.n = auxiliary;
		if (this.front == null)
		{
			// When adding a first node of queue
			this.front = node;
			this.rear = node;
		}
		else if (this.front.n.first >= auxiliary.first)
		{
			// Add node at beginning position
			node.next = this.front;
			this.front.prev = node;
			this.front = node;
		}
		else if (this.rear.n.first <= auxiliary.first)
		{
			// Add node at last position
			node.prev = this.rear;
			this.rear.next = node;
			this.rear = node;
		}
		else
		{
			var temp = this.front;
			// Find the location of inserting priority node
			while (temp.n.first < auxiliary.first)
			{
				temp = temp.next;
			}
			// Add node
			node.next = temp;
			node.prev = temp.prev;
			temp.prev = node;
			if (node.prev != null)
			{
				node.prev.next = node;
			}
		}
		this.size = this.size + 1;
	}
	isEmpty()
	{
		if (this.size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Get a front element of queue
	peek()
	{
		if (this.isEmpty() == true)
		{
			// When Queue is empty
			process.stdout.write("\n Empty Queue \n");
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
	isSize()
	{
		return this.size;
	}
	// Remove a front node of a queue
	deQueue()
	{
		if (this.isEmpty() == false)
		{
			var temp = this.front;
			temp.n = null;
			if (this.front == this.rear)
			{
				// When queue contains only one node
				this.rear = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
				this.front.prev = null;
			}
			// Change queue size
			this.size--;
		}
	}
	// Print elements of queue
	printQdata()
	{
		var node = this.front;
		process.stdout.write("\n Queue Element ");
		while (node != null)
		{
			process.stdout.write("\n " + node.n.first + " " + node.n.second);
			node = node.next;
		}
		process.stdout.write("\n");
	}
}
class HuffmanCodes
{
	// Display Huffman code
	printTree(node, result)
	{
		if (node == null)
		{
			return;
		}
		if (node.left == null && node.right == null)
		{
			process.stdout.write("\n " + node.second + " " + node.first + " : " + result);
			return;
		}
		this.printTree(node.left, result + "0");
		this.printTree(node.right, result + "1");
	}
	// Construct Huffman Code Tree
	buildHuffmanCodes(data, n)
	{
		var q = new PriorityQueue();
		var root = null;
		var n1 = null;
		var n2 = null;
		var i = 0;
		// Use to get A to Z character frequency
		var frequency = Array(26).fill(0);
		for (i = 0; i < n; ++i)
		{
			frequency[(data[i]).charCodeAt(0) - ('A').charCodeAt(0)]++;
		}
		// First add all elements into priority queue
		for (i = 0; i < 26; ++i)
		{
			if (frequency[i] > 0)
			{
				root = new TreeNode(frequency[i], String.fromCharCode((i + 65)));
				q.enQueue(root);
			}
		}
		// q.printQdata();
		// Execute loop until the priority queue contains more than 1 node
		while (q.isSize() > 1)
		{
			// Get first smallest node
			n1 = q.peek();
			//Remove a front element
			q.deQueue();
			// Get second smallest node
			n2 = q.peek();
			// Remove a front element
			q.deQueue();
			// Make new node using two smallest node
			root = new TreeNode(n1.first + n2.first, ' ');
			// Add new node into priority queue
			q.enQueue(root);
			// Set left and right child
			root.left = n1;
			root.right = n2;
		}
		q.deQueue();
		return root;
	}
	// Put the leaf node information  to given map
	getCode(node, m, result)
	{
		if (node == null)
		{
			return;
		}
		if (node.left == null && node.right == null)
		{
			// Add Initialize leaf node value and generated code result
         	m.set(node.second, result);
			return;
		}
		// Recursively, visiting left and right subtree to select
		this.getCode(node.left, m, result + "0");
		this.getCode(node.right, m, result + "1");
	}
	// Get encoding text by using generated tree
	enCodingText(root, data, n)
	{
		
		var map = new Map();
		// Find the path from root to leaf nodes
		this.getCode(root, map, "");
		var encode = "";
		for (var i = 0; i < n; i++)
		{
			encode += map.get(data[i]);
		}
		return encode;
	}
	// Returns the decode of given encode and tree
	deCodingText(root, encode)
	{
		// Return decoded text
		var n = encode.length;
		var decode = "";
		var auxiliary = root;
		// Execute loop through by encode length
		for (var i = 0; i < n; i++)
		{
			if (encode[i] == '0')
			{
				// Visit to left child
				auxiliary = auxiliary.left;
			}
			else
			{
				// Visit to right child
				auxiliary = auxiliary.right;
			}
			if (auxiliary.left == null && auxiliary.right == null)
			{
				// When get leaf node
				decode += auxiliary.second;
				// Start with root of tree
				auxiliary = root;
			}
		}
		return decode;
	}
}

function main()
{
	var task = new HuffmanCodes();
	// Given input data
	var data = "ABEECAAAABBBEAEEEE";
	var n = data.length;
	// Construct  Tree
	var root = task.buildHuffmanCodes(data, n);
	// Get encode
	var encode = task.enCodingText(root, data, n);
	// Get decode using encode
	var decode = task.deCodingText(root, encode);
	// Display result
	process.stdout.write("\n Data : " + data);
	//  Print all leaf node information
	task.printTree(root, "");
	// Display encode text
	process.stdout.write("\n Encode : " + encode);
	// Display decode text
	process.stdout.write("\n Decode : " + decode);
}
main();

Output

 Data : ABEECAAAABBBEAEEEE
 E 7 : 0
 C 1 : 100
 B 4 : 101
 A 6 : 11
 Encode : 1110100100111111111011011010110000
 Decode : ABEECAAAABBBEAEEEE
#  Python 3 Program 
#  Hamming decoding example

class TreeNode :
	
	def __init__(self, first, second) :
		self.first = first
		self.second = second
		self.left = None
		self.right = None
	

class QNode :
	
	def __init__(self, n) :
		self.n = n
		self.prev = None
		self.next = None
	

class PriorityQueue :
	
	def __init__(self) :
		self.front = None
		self.rear = None
		self.size = 0
	
	#  Add a node into queue Priority queue
	def enQueue(self, auxiliary) :
		# Create a dynamic node
		node = QNode(auxiliary)
		node.n = auxiliary
		if (self.front == None) :
			#  When adding a first node of queue
			self.front = node
			self.rear = node
		
		elif(self.front.n.first >= auxiliary.first) :
			#  Add node at beginning position
			node.next = self.front
			self.front.prev = node
			self.front = node
		
		elif(self.rear.n.first <= auxiliary.first) :
			#  Add node at last position
			node.prev = self.rear
			self.rear.next = node
			self.rear = node
		else :
			temp = self.front
			#  Find the location of inserting priority node
			while (temp.n.first < auxiliary.first) :
				temp = temp.next
			
			#  Add node
			node.next = temp
			node.prev = temp.prev
			temp.prev = node
			if (node.prev != None) :
				node.prev.next = node
			
		
		self.size = self.size + 1
	
	def isEmpty(self) :
		if (self.size == 0) :
			return True
		else :
			return False
		
	
	#  Get a front element of queue
	def peek(self) :
		if (self.isEmpty() == True) :
			#  When Queue is empty
			print("\n Empty Queue ")
			return None
		else :
			return self.front.n
		
	
	def isSize(self) :
		return self.size
	
	#  Remove a front node of a queue
	def deQueue(self) :
		if (self.isEmpty() == False) :
			temp = self.front
			temp.n = None
			if (self.front == self.rear) :
				#  When queue contains only one node
				self.rear = None
				self.front = None
			else :
				self.front = self.front.next
				self.front.prev = None
			
			#  Change queue size
			self.size -= 1
		
	
	#  Print elements of queue
	def printQdata(self) :
		node = self.front
		print("\n Queue Element ", end = "")
		while (node != None) :
			print("\n ", node.n.first ," ", node.n.second, end = "")
			node = node.next
		
		print(end = "\n")
	

class HuffmanCodes :
	#  Display Huffman code
	def printTree(self, node, result) :
		if (node == None) :
			return
		
		if (node.left == None and node.right == None) :
			print("\n ", node.second ," ", node.first ," : ", result, end = "")
			return
		
		self.printTree(node.left, result+"0")
		self.printTree(node.right, result+"1")
	
	#  Construct Huffman Code Tree
	def buildHuffmanCodes(self, data, n) :
		q = PriorityQueue()
		root = None
		n1 = None
		n2 = None
		i = 0
		#  Use to get A to Z character
		frequency = [0] * (26)
		while (i < n) :
			frequency[ord(data[i]) - ord('A')] += 1
			i += 1
		
		#  First add all elements into priority queue
		i = 0
		while (i < 26) :
			if (frequency[i] > 0) :
				root = TreeNode(frequency[i], chr((i + 65)))
				q.enQueue(root)
			
			i += 1
		
		#  q.printQdata()
		#  Execute loop until the priority queue contains more than 1 node
		while (q.isSize() > 1) :
			#  Get first smallest node
			n1 = q.peek()
			# Remove a front element
			q.deQueue()
			#  Get second smallest node
			n2 = q.peek()
			#  Remove a front element
			q.deQueue()
			#  Make new node using two smallest node
			root = TreeNode(n1.first + n2.first, ' ')
			#  Add new node into priority queue
			q.enQueue(root)
			#  Set left and right child
			root.left = n1
			root.right = n2
		
		q.deQueue()
		return root
	
	#  Put the leaf node information  to given map
	def getCode(self, node, m, result) :
		if (node == None) :
			return
		
		if (node.left == None and node.right == None) :
			#  Add Initialize leaf node value and generated code result
			m[node.second] = result
			return
		
		#  Recursively, visiting left and right subtree to select
		self.getCode(node.left, m, result+"0")
		self.getCode(node.right, m, result+"1")
	
	#  Get encoding text by using generated tree
	def enCodingText(self, root, data, n) :
		map = {}
		#  Find the path from root to leaf nodes
		self.getCode(root, map, "")
		encode = ""
		i = 0
		while (i < n) :
			encode += map[data[i]]
			i += 1
		
		return encode
	
	#  Returns the decode of given encode and tree
	def deCodingText(self, root, encode) :
		#  Return decoded text
		n = len(encode)
		decode = ""
		auxiliary = root
		#  Execute loop through by encode length
		i = 0
		while (i < n) :
			if (encode[i] == '0') :
				#  Visit to left child
				auxiliary = auxiliary.left
			else :
				#  Visit to right child
				auxiliary = auxiliary.right
			
			if (auxiliary.left == None and auxiliary.right == None) :
				#  When get leaf node
				decode += auxiliary.second
				#  Start with root of tree
				auxiliary = root
			
			i += 1
		
		return decode
	

def main() :
	task = HuffmanCodes()
	#  Given input data
	data = "ABEECAAAABBBEAEEEE"
	n = len(data)
	#  Construct  Tree
	root = task.buildHuffmanCodes(data, n)
	#  Get encode
	encode = task.enCodingText(root, data, n)
	#  Get decode using encode
	decode = task.deCodingText(root, encode)
	#  Display result
	print("\n Data : ", data, end = "")
	#   Print all leaf node information
	task.printTree(root, "")
	#  Display encode text
	print("\n Encode : ", encode, end = "")
	#  Display decode text
	print("\n Decode : ", decode, end = "")

if __name__ == "__main__": main()

Output

 Data :  ABEECAAAABBBEAEEEE
  E   7  :  0
  C   1  :  100
  B   4  :  101
  A   6  :  11
 Encode :  1110100100111111111011011010110000
 Decode :  ABEECAAAABBBEAEEEE
#  Ruby Program 
#  Hamming decoding example

class TreeNode  
	# Define the accessor and reader of class TreeNode  
	attr_reader :first, :second, :left, :right
	attr_accessor :first, :second, :left, :right
 
	
	def initialize(first, second) 
		self.first = first
		self.second = second
		self.left = nil
		self.right = nil
	end

end

class QNode  
	# Define the accessor and reader of class QNode  
	attr_reader :n, :next, :prev
	attr_accessor :n, :next, :prev
 
	
	def initialize(n) 
		self.n = n
		self.prev = nil
		self.next = nil
	end

end

class PriorityQueue  
	# Define the accessor and reader of class PriorityQueue  
	attr_reader :front, :rear, :size
	attr_accessor :front, :rear, :size
 
	
	def initialize() 
		self.front = nil
		self.rear = nil
		self.size = 0
	end

	#  Add a node into queue Priority queue
	def enQueue(auxiliary) 
		# Create a dynamic node
		node = QNode.new(auxiliary)
		node.n = auxiliary
		if (self.front == nil) 
			#  When adding a first node of queue
			self.front = node
			self.rear = node
		elsif(self.front.n.first >= auxiliary.first) 
			#  Add node at beginning position
			node.next = self.front
			self.front.prev = node
			self.front = node
		elsif(self.rear.n.first <= auxiliary.first) 
			#  Add node at last position
			node.prev = self.rear
			self.rear.next = node
			self.rear = node
		else 
			temp = self.front
			#  Find the location of inserting priority node
			while (temp.n.first < auxiliary.first) 
				temp = temp.next
			end

			#  Add node
			node.next = temp
			node.prev = temp.prev
			temp.prev = node
			if (node.prev != nil) 
				node.prev.next = node
			end

		end

		self.size = self.size + 1
	end

	def isEmpty() 
		if (self.size == 0) 
			return true
		else 
			return false
		end

	end

	#  Get a front element of queue
	def peek() 
		if (self.isEmpty() == true) 
			#  When Queue is empty
			print("\n Empty Queue \n")
			return nil
		else 
			return self.front.n
		end

	end

	def isSize() 
		return self.size
	end

	#  Remove a front node of a queue
	def deQueue() 
		if (self.isEmpty() == false) 
			temp = self.front
			temp.n = nil
			if (self.front == self.rear) 
				#  When queue contains only one node
				self.rear = nil
				self.front = nil
			else 
				self.front = self.front.next
				self.front.prev = nil
			end

			#  Change queue size
			self.size -= 1
		end

	end

	#  Print elements of queue
	def printQdata() 
		node = self.front
		print("\n Queue Element ")
		while (node != nil) 
			print("\n ", node.n.first ," ", node.n.second)
			node = node.next
		end

		print("\n")
	end

end

class HuffmanCodes 
	#  Display Huffman code
	def printTree(node, result) 
		if (node == nil) 
			return
		end

		if (node.left == nil && node.right == nil) 
			print("\n ", node.second ," ", node.first ," : ", result)
			return
		end

		self.printTree(node.left, result+"0")
		self.printTree(node.right, result+"1")
	end

	#  Construct Huffman Code Tree
	def buildHuffmanCodes(data, n) 
		q = PriorityQueue.new()
		root = nil
		n1 = nil
		n2 = nil
		i = 0
		#  Use to get A to Z character
		frequency = Array.new(26) {0}
		while (i < n) 
			frequency[(data[i]).ord - ('A').ord] += 1
			i += 1
		end

		#  First add all elements into priority queue
		i = 0
		while (i < 26) 
			if (frequency[i] > 0) 
				root = TreeNode.new(frequency[i], ((i + 65)).chr)
				q.enQueue(root)
			end

			i += 1
		end

		#  q.printQdata()
		#  Execute loop until the priority queue contains more than 1 node
		while (q.isSize() > 1) 
			#  Get first smallest node
			n1 = q.peek()
			# Remove a front element
			q.deQueue()
			#  Get second smallest node
			n2 = q.peek()
			#  Remove a front element
			q.deQueue()
			#  Make new node using two smallest node
			root = TreeNode.new(n1.first + n2.first, ' ')
			#  Add new node into priority queue
			q.enQueue(root)
			#  Set left and right child
			root.left = n1
			root.right = n2
		end

		q.deQueue()
		return root
	end

	#  Put the leaf node information  to given map
	def getCode(node, m, result) 
		if (node == nil) 
			return
		end

		if (node.left == nil && node.right == nil) 
			#  Add Initialize leaf node value and generated code result
			m[node.second] = result
			return
		end

		#  Recursively, visiting left and right subtree to select
		self.getCode(node.left, m, result+"0")
		self.getCode(node.right, m, result+"1")
	end

	#  Get encoding text by using generated tree
	def enCodingText(root, data, n) 
		map = Hash.new 
		#  Find the path from root to leaf nodes
		self.getCode(root, map, "")
		encode = ""
		i = 0
		while (i < n) 
			encode += map[data[i]]
			i += 1
		end

		return encode
	end

	#  Returns the decode of given encode and tree
	def deCodingText(root, encode) 
		#  Return decoded text
		n = encode.length()
		decode = ""
		auxiliary = root
		#  Execute loop through by encode length
		i = 0
		while (i < n) 
			if (encode[i] == '0') 
				#  Visit to left child
				auxiliary = auxiliary.left
			else 
				#  Visit to right child
				auxiliary = auxiliary.right
			end

			if (auxiliary.left == nil && auxiliary.right == nil) 
				#  When get leaf node
				decode += auxiliary.second
				#  Start with root of tree
				auxiliary = root
			end

			i += 1
		end

		return decode
	end

end

def main() 
	task = HuffmanCodes.new()
	#  Given input data
	data = "ABEECAAAABBBEAEEEE"
	n = data.length()
	#  Construct  Tree
	root = task.buildHuffmanCodes(data, n)
	#  Get encode
	encode = task.enCodingText(root, data, n)
	#  Get decode using encode
	decode = task.deCodingText(root, encode)
	#  Display result
	print("\n Data : ", data)
	#   Print all leaf node information
	task.printTree(root, "")
	#  Display encode text
	print("\n Encode : ", encode)
	#  Display decode text
	print("\n Decode : ", decode)
end

main()

Output

 Data : ABEECAAAABBBEAEEEE
 E 7 : 0
 C 1 : 100
 B 4 : 101
 A 6 : 11
 Encode : 1110100100111111111011011010110000
 Decode : ABEECAAAABBBEAEEEE
import scala.collection.mutable.Map
/*
    Scala Program 
    Hamming decoding example
*/
class TreeNode(var first: Int , var second: Character , var left: TreeNode , var right: TreeNode)
{
	def this(first: Int, second: Char)
	{
		this(first, second, null, null);
	}
}
class QNode(var n: TreeNode , var next: QNode , var prev: QNode)
{
	def this(n: TreeNode)
	{
		this(n, null, null);
	}
}
class PriorityQueue(var front: QNode , var rear: QNode , var size: Int)
{
	def this()
	{
		this(null, null, 0);
	}
	// Add a node into queue Priority queue
	def enQueue(auxiliary: TreeNode): Unit = {
		//Create a dynamic node
		var node: QNode = new QNode(auxiliary);
		node.n = auxiliary;
		if (this.front == null)
		{
			// When adding a first node of queue
			this.front = node;
			this.rear = node;
		}
		else if (this.front.n.first >= auxiliary.first)
		{
			// Add node at beginning position
			node.next = this.front;
			this.front.prev = node;
			this.front = node;
		}
		else if (this.rear.n.first <= auxiliary.first)
		{
			// Add node at last position
			node.prev = this.rear;
			this.rear.next = node;
			this.rear = node;
		}
		else
		{
			var temp: QNode = this.front;
			// Find the location of inserting priority node
			while (temp.n.first < auxiliary.first)
			{
				temp = temp.next;
			}
			// Add node
			node.next = temp;
			node.prev = temp.prev;
			temp.prev = node;
			if (node.prev != null)
			{
				node.prev.next = node;
			}
		}
		this.size = this.size + 1;
	}
	def isEmpty(): Boolean = {
		if (this.size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Get a front element of queue
	def peek(): TreeNode = {
		if (this.isEmpty() == true)
		{
			// When Queue is empty
			print("\n Empty Queue \n");
			return null;
		}
		else
		{
			return this.front.n;
		}
	}
	def isSize(): Int = {
		return this.size;
	}
	// Remove a front node of a queue
	def deQueue(): Unit = {
		if (this.isEmpty() == false)
		{
			var temp: QNode = this.front;
			temp.n = null;
			if (this.front == this.rear)
			{
				// When queue contains only one node
				this.rear = null;
				this.front = null;
			}
			else
			{
				this.front = this.front.next;
				this.front.prev = null;
			}
			// Change queue size
			this.size -= 1;
		}
	}
	// Print elements of queue
	def printQdata(): Unit = {
		var node: QNode = this.front;
		print("\n Queue Element ");
		while (node != null)
		{
			print("\n " + node.n.first + " " + node.n.second);
			node = node.next;
		}
		print("\n");
	}
}
class HuffmanCodes
{
	// Display Huffman code
	def printTree(node: TreeNode, result: String): Unit = {
		if (node == null)
		{
			return;
		}
		if (node.left == null && node.right == null)
		{
			print("\n " + node.second + " " + node.first + " : " + result);
			return;
		}
		this.printTree(node.left, result + "0");
		this.printTree(node.right, result + "1");
	}
	// Construct Huffman Code Tree
	def buildHuffmanCodes(data: String, n: Int): TreeNode = {
		var q: PriorityQueue = new PriorityQueue();
		var root: TreeNode = null;
		var n1: TreeNode = null;
		var n2: TreeNode = null;
		var i: Int = 0;
		// Use to get A to Z character
		var frequency: Array[Int] = Array.fill[Int](26)(0);
		while (i < n)
		{
			frequency(data(i) - 'A') += 1;
			i += 1;
		}
		// First add all elements into priority queue
		i = 0;
		while (i < 26)
		{
			if (frequency(i) > 0)
			{
				root = new TreeNode(frequency(i), ((i + 65)).toChar);
				q.enQueue(root);
			}
			i += 1;
		}
		// q.printQdata();
		// Execute loop until the priority queue contains more than 1 node
		while (q.isSize() > 1)
		{
			// Get first smallest node
			n1 = q.peek();
			//Remove a front element
			q.deQueue();
			// Get second smallest node
			n2 = q.peek();
			// Remove a front element
			q.deQueue();
			// Make new node using two smallest node
			root = new TreeNode(n1.first + n2.first, ' ');
			// Add new node into priority queue
			q.enQueue(root);
			// Set left and right child
			root.left = n1;
			root.right = n2;
		}
		q.deQueue();
		return root;
	}
	// Put the leaf node information  to given map
	def getCode(node: TreeNode, m: Map[Character, String], result: String): Unit = {
		if (node == null)
		{
			return;
		}
		if (node.left == null && node.right == null)
		{
			// Add Initialize leaf node value and generated code result
			m(node.second) = result;
			return;
		}
		// Recursively, visiting left and right subtree to select
		this.getCode(node.left, m, result + "0");
		this.getCode(node.right, m, result + "1");
	}
	// Get encoding text by using generated tree
	def enCodingText(root: TreeNode, data: String, n: Int): String = {
        var map: Map[Character, String] = Map();
		// Find the path from root to leaf nodes
		this.getCode(root, map, "");
		var encode: String = "";
		var i: Int = 0;
		while (i < n)
		{
			encode += map.get(data(i)).get;
			i += 1;
		}
		return encode;
	}
	// Returns the decode of given encode and tree
	def deCodingText(root: TreeNode, encode: String): String = {
		// Return decoded text
		var n: Int = encode.length();
		var decode: String = "";
		var auxiliary: TreeNode = root;
		// Execute loop through by encode length
		var i: Int = 0;
		while (i < n)
		{
			if (encode(i) == '0')
			{
				// Visit to left child
				auxiliary = auxiliary.left;
			}
			else
			{
				// Visit to right child
				auxiliary = auxiliary.right;
			}
			if (auxiliary.left == null && auxiliary.right == null)
			{
				// When get leaf node
				decode += auxiliary.second;
				// Start with root of tree
				auxiliary = root;
			}
			i += 1;
		}
		return decode;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: HuffmanCodes = new HuffmanCodes();
		// Given input data
		var data: String = "ABEECAAAABBBEAEEEE";
		var n: Int = data.length();
		// Construct  Tree
		var root: TreeNode = task.buildHuffmanCodes(data, n);
		// Get encode
		var encode: String = task.enCodingText(root, data, n);
		// Get decode using encode
		var decode: String = task.deCodingText(root, encode);
		// Display result
		print("\n Data : " + data);
		//  Print all leaf node information
		task.printTree(root, "");
		// Display encode text
		print("\n Encode : " + encode);
		// Display decode text
		print("\n Decode : " + decode);
	}
}

Output

 Data : ABEECAAAABBBEAEEEE
 E 7 : 0
 C 1 : 100
 B 4 : 101
 A 6 : 11
 Encode : 1110100100111111111011011010110000
 Decode : ABEECAAAABBBEAEEEE
/*
    Swift 4 Program 
    Hamming decoding example
*/
class TreeNode
{
	var first: Int;
	var second: Character;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ first: Int, _ second: Character)
	{
		self.first = first;
		self.second = second;
		self.left = nil;
		self.right = nil;
	}
}
class QNode
{
	var n: TreeNode? ;
	var next: QNode? ;
	var prev: QNode? ;
	init(_ n: TreeNode? )
	{
		self.n = n;
		self.prev = nil;
		self.next = nil;
	}
}
class PriorityQueue
{
	var front: QNode? ;
	var rear: QNode? ;
	var size: Int;
	init()
	{
		self.front = nil;
		self.rear = nil;
		self.size = 0;
	}
	// Add a node into queue Priority queue
	func enQueue(_ auxiliary: TreeNode? )
	{
		//Create a dynamic node
		let node: QNode? = QNode(auxiliary);
		node!.n = auxiliary;
		if (self.front == nil)
		{
			// When adding a first node of queue
			self.front = node;
			self.rear = node;
		}
		else if (self.front!.n!.first >= auxiliary!.first)
		{
			// Add node at beginning position
			node!.next = self.front;
			self.front!.prev = node;
			self.front = node;
		}
		else if (self.rear!.n!.first <= auxiliary!.first)
		{
			// Add node at last position
			node!.prev = self.rear;
			self.rear!.next = node;
			self.rear = node;
		}
		else
		{
			var temp: QNode? = self.front;
			// Find the location of inserting priority node
			while (temp!.n!.first < auxiliary!.first)
			{
				temp = temp!.next;
			}
			// Add node
			node!.next = temp;
			node!.prev = temp!.prev;
			temp!.prev = node;
			if (node!.prev  != nil)
			{
				node!.prev!.next = node;
			}
		}
		self.size = self.size + 1;
	}
	func isEmpty()->Bool
	{
		if (self.size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Get a front element of queue
	func peek()->TreeNode?
	{
		if (self.isEmpty() == true)
		{
			// When Queue is empty
			print("\n Empty Queue ");
			return nil;
		}
		else
		{
			return self.front!.n;
		}
	}
	func isSize()->Int
	{
		return self.size;
	}
	// Remove a front node of a queue
	func deQueue()
	{
		if (self.isEmpty() == false)
		{
			let temp: QNode? = self.front;
			temp!.n = nil;
			if (self.front === self.rear)
			{
				// When queue contains only one node
				self.rear = nil;
				self.front = nil;
			}
			else
			{
				self.front = self.front!.next;
				self.front!.prev = nil;
			}
			// Change queue size
			self.size -= 1;
		}
	}
	// Print elements of queue
	func printQdata()
	{
		var node: QNode? = self.front;
		print("\n Queue Element ", terminator: "");
		while (node  != nil)
		{
			print("\n ", node!.n!.first ," ", node!.n!.second, terminator: "");
			node = node!.next;
		}
		print(terminator: "\n");
	}
}
class HuffmanCodes
{
	// Display Huffman code
	func printTree(_ node: TreeNode? , _ result : String)
	{
		if (node == nil)
		{
			return;
		}
		if (node!.left == nil && node!.right == nil)
		{
			print("\n ", node!.second ," ", node!.first ," : ", result, terminator: "");
			return;
		}
		self.printTree(node!.left, result+"0");
		self.printTree(node!.right, result+"1");
	}
	// Construct Huffman Code Tree
	func buildHuffmanCodes(_ data: [Character], _ n: Int)->TreeNode?
	{
		let q: PriorityQueue = PriorityQueue();
		var root: TreeNode? = nil;
		var n1: TreeNode? = nil;
		var n2: TreeNode? = nil;
		var i: Int = 0;
		// Use to get A to Z character
		var frequency: [Int] = Array(repeating: 0, count: 26);
        var index = 0;
		while (i < n)
		{
           index = Int(UnicodeScalar(String(data[i]))!.value  -  UnicodeScalar("A")!.value);
			frequency[index] = frequency[index] + 1;
			i += 1;
		}
		// First add all elements into priority queue
		i = 0;
		while (i < 26)
		{
			if (frequency[i] > 0)
			{
				root = TreeNode(frequency[i], Character(UnicodeScalar(UInt8((i + 65)))));
				q.enQueue(root);
			}
			i += 1;
		}
		// q.printQdata();
		// Execute loop until the priority queue contains more than 1 node
		while (q.isSize() > 1)
		{
			// Get first smallest node
			n1 = q.peek();
			//Remove a front element
			q.deQueue();
			// Get second smallest node
			n2 = q.peek();
			// Remove a front element
			q.deQueue();
			// Make new node using two smallest node
			root = TreeNode(n1!.first + n2!.first, " ");
			// Add new node into priority queue
			q.enQueue(root);
			// Set left and right child
			root!.left = n1;
			root!.right = n2;
		}
		q.deQueue();
		return root;
	}
	// Put the leaf node information  to given map
	func getCode(_ node: TreeNode? ,_ m: inout [Character: String] , _ result: String)
	{
		if (node == nil)
		{
			return;
		}
		if (node!.left == nil && node!.right == nil)
		{
			// Add Initialize leaf node value and generated code result
			m[node!.second] = result;
			return;
		}
		// Recursively, visiting left and right subtree to select
		self.getCode(node!.left, &m, result+"0");
		self.getCode(node!.right, &m, result+"1");
	}
	// Get encoding text by using generated tree
	func enCodingText(_ root: TreeNode? , _ data : [Character], _ n: Int)->String
	{
		
		var map = [Character: String]();
		// Find the path from root to leaf nodes
		self.getCode(root, &map, "");
		var encode: String = "";
		var i: Int = 0;
		while (i < n)
		{
			encode += map[data[i]]! ;
			i += 1;
		}
		return encode;
	}
	// Returns the decode of given encode and tree
	func deCodingText(_ root: TreeNode? , _ encode : [Character])->String
	{
		// Return decoded text
		let n: Int = encode.count;
		var decode: String = "";
		var auxiliary: TreeNode? = root;
		// Execute loop through by encode length
		var i: Int = 0;
		while (i < n)
		{
			if (encode[i] == "0")
			{
				// Visit to left child
				auxiliary = auxiliary!.left;
			}
			else
			{
				// Visit to right child
				auxiliary = auxiliary!.right;
			}
			if (auxiliary!.left == nil && auxiliary!.right == nil)
			{
				// When get leaf node
				decode += String(auxiliary!.second);
				// Start with root of tree
				auxiliary = root;
			}
			i += 1;
		}
		return decode;
	}
}
func main()
{
	let task: HuffmanCodes = HuffmanCodes();
	// Given input data
	let data: String = "ABEECAAAABBBEAEEEE";
	let n: Int = data.count;
  	let d = Array(data);
	// Construct  Tree
	let root: TreeNode? = task.buildHuffmanCodes(d, n);
	// Get encode
	let encode: String = task.enCodingText(root, d, n);
	// Get decode using encode
	let decode: String = task.deCodingText(root, Array(encode));
	// Display result
	print("\n Data : ", data, terminator: "");
	//  Print all leaf node information
	task.printTree(root, "");
	// Display encode text
	print("\n Encode : ", encode, terminator: "");
	// Display decode text
	print("\n Decode : ", decode, terminator: "");
}
main();

Output

 Data :  ABEECAAAABBBEAEEEE
  E   7  :  0
  C   1  :  100
  B   4  :  101
  A   6  :  11
 Encode :  1110100100111111111011011010110000
 Decode :  ABEECAAAABBBEAEEEE
/*
    Kotlin Program 
    Hamming decoding example
*/
class TreeNode
{
	var first: Int;
	var second: Char;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(first: Int, second: Char)
	{
		this.first = first;
		this.second = second;
		this.left = null;
		this.right = null;
	}
}
class QNode
{
	var n: TreeNode ? ;
	var next: QNode ? ;
	var prev: QNode ? ;
	constructor(n: TreeNode ? )
	{
		this.n = n;
		this.prev = null;
		this.next = null;
	}
}
class PriorityQueue
{
	var front: QNode ? ;
	var rear: QNode ? ;
	var size: Int;
	constructor()
	{
		this.front = null;
		this.rear = null;
		this.size = 0;
	}
	// Add a node into queue Priority queue
	fun enQueue(auxiliary: TreeNode ): Unit
	{
		//Create a dynamic node
		var node: QNode = QNode(auxiliary);
		node.n = auxiliary;
		if (this.front == null)
		{
			// When adding a first node of queue
			this.front = node;
			this.rear = node;
		}
		else if (this.front?.n!!.first >= auxiliary.first)
		{
			// Add node at beginning position
			node.next = this.front;
			this.front?.prev = node;
			this.front = node;
		}
		else if (this.rear?.n!!.first <= auxiliary.first)
		{
			// Add node at last position
			node.prev = this.rear;
			this.rear?.next = node;
			this.rear = node;
		}
		else
		{
			var temp: QNode ? = this.front;
			// Find the location of inserting priority node
			while (temp?.n!!.first < auxiliary.first)
			{
				temp = temp.next;
			}
			// Add node
			node.next = temp;
			node.prev = temp.prev;
			temp.prev = node;
			if (node.prev != null)
			{
				node.prev?.next = node;
			}
		}
		this.size = this.size + 1;
	}
	fun isEmpty(): Boolean
	{
		if (this.size == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	// Get a front element of queue
	fun peek(): TreeNode ?
	{
		if (this.isEmpty() == true)
		{
			// When Queue is empty
			print("\n Empty Queue \n");
			return null;
		}
		else
		{
			return this.front?.n;
		}
	}
	fun isSize(): Int
	{
		return this.size;
	}
	// Remove a front node of a queue
	fun deQueue(): Unit
	{
		if (this.isEmpty() == false)
		{
			var temp: QNode ? = this.front;
			temp?.n = null;
			if (this.front == this.rear)
			{
				// When queue contains only one node
				this.rear = null;
				this.front = null;
			}
			else
			{
				this.front = this.front?.next;
				this.front?.prev = null;
			}
			// Change queue size
			this.size -= 1;
		}
	}
	// Print elements of queue
	fun printQdata(): Unit
	{
		var node: QNode ? = this.front;
		print("\n Queue Element ");
		while (node != null)
		{
			print("\n " + node.n?.first + " " + node.n?.second);
			node = node.next;
		}
		print("\n");
	}
}
class HuffmanCodes
{
	// Display Huffman code
	fun printTree(node: TreeNode ? , result : String): Unit
	{
		if (node == null)
		{
			return;
		}
		if (node.left == null && node.right == null)
		{
			print("\n " + node.second + " " + node.first + " : " + result);
			return;
		}
		this.printTree(node.left, result + "0");
		this.printTree(node.right, result + "1");
	}
	// Construct Huffman Code Tree
	fun buildHuffmanCodes(data: String, n: Int): TreeNode ?
	{
		var q: PriorityQueue = PriorityQueue();
		var root: TreeNode ? = null;
		var n1: TreeNode ? ;
		var n2: TreeNode ? ;
		var i: Int = 0;
		// Use to get A to Z character
		var frequency: Array < Int > = Array(26)
		{
			0
		};
		while (i < n)
		{
			frequency[data[i] - 'A'] += 1;
			i += 1;
		}
		// First add all elements into priority queue
		i = 0;
		while (i < 26)
		{
			if (frequency[i] > 0)
			{
				root = TreeNode(frequency[i], (i + 65).toChar());
				q.enQueue(root);
			}
			i += 1;
		}
		// q.printQdata();
		// Execute loop until the priority queue contains more than 1 node
		while (q.isSize() > 1)
		{
			// Get first smallest node
			n1 = q.peek();
			//Remove a front element
			q.deQueue();
			// Get second smallest node
			n2 = q.peek();
			// Remove a front element
			q.deQueue();
			// Make new node using two smallest node
			root = TreeNode(n1!!.first + n2!!.first, ' ');
			// Add new node into priority queue
			q.enQueue(root);
			// Set left and right child
			root.left = n1;
			root.right = n2;
		}
		q.deQueue();
		return root;
	}
	// Put the leaf node information  to given map
	fun getCode(node: TreeNode ? , m: MutableMap <Char, String> , result : String): Unit
	{
		if (node == null)
		{
			return;
		}
		if (node.left == null && node.right == null)
		{
			// Add Initialize leaf node value and generated code result
			m.put(node.second, result);
			return;
		}
		// Recursively, visiting left and right subtree to select
		this.getCode(node.left, m, result + "0");
		this.getCode(node.right, m, result + "1");
	}
	// Get encoding text by using generated tree
	fun enCodingText(root: TreeNode ? , data : String, n: Int): String
	{
		var map = mutableMapOf<Char, String>();
		// Find the path from root to leaf nodes
		this.getCode(root, map, "");
		var encode: String = "";
		var i: Int = 0;
		while (i < n)
		{
			encode += map.get(data[i]);
			i += 1;
		}
		return encode;
	}
	// Returns the decode of given encode and tree
	fun deCodingText(root: TreeNode ? , encode : String): String
	{
		// Return decoded text
		var n: Int = encode.count();
		var decode: String = "";
		var auxiliary: TreeNode ? = root;
		// Execute loop through by encode length
		var i: Int = 0;
		while (i < n)
		{
			if (encode[i] == '0')
			{
				// Visit to left child
				auxiliary = auxiliary?.left;
			}
			else
			{
				// Visit to right child
				auxiliary = auxiliary?.right;
			}
			if (auxiliary?.left == null && auxiliary?.right == null)
			{
				// When get leaf node
				decode += auxiliary!!.second;
				// Start with root of tree
				auxiliary = root;
			}
			i += 1;
		}
		return decode;
	}
}
fun main(args: Array < String > ): Unit
{
	var task: HuffmanCodes = HuffmanCodes();
	// Given input data
	var data: String = "ABEECAAAABBBEAEEEE";
	var n: Int = data.count();
	// Construct  Tree
	var root: TreeNode ? = task.buildHuffmanCodes(data, n);
	// Get encode
	var encode: String = task.enCodingText(root, data, n);
	// Get decode using encode
	var decode: String = task.deCodingText(root, encode);
	// Display result
	print("\n Data : " + data);
	//  Print all leaf node information
	task.printTree(root, "");
	// Display encode text
	print("\n Encode : " + encode);
	// Display decode text
	print("\n Decode : " + decode);
}

Output

 Data : ABEECAAAABBBEAEEEE
 E 7 : 0
 C 1 : 100
 B 4 : 101
 A 6 : 11
 Encode : 1110100100111111111011011010110000
 Decode : ABEECAAAABBBEAEEEE

Resultant Output Explanation

  1. Display the given original data.
  2. Print the characters from the Huffman tree along with their codes.
  3. Display the encoded string using the Huffman tree.
  4. Display the decoded data obtained from the Hamming-encoded string using the Huffman tree.

Time Complexity

  1. Building Huffman Tree: O(n log n) - Constructing the Huffman tree using a priority queue.
  2. Getting Codes: O(n) - Generating codes for each character in the Huffman tree.
  3. Encoding Text: O(n) - Encoding the original data using the Huffman tree.
  4. Decoding Text: O(n) - Decoding the Hamming-encoded string using the Huffman tree.

The overall time complexity of this solution is mainly dominated by building the Huffman tree, which is O(n log n), where n is the number of characters in the input data. The code effectively constructs the Huffman tree, encodes, and decodes the data using Hamming decoding with the Huffman tree.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment