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
- Create a TreeNode class to represent nodes in the Huffman tree.
- Create a QNode class to represent nodes in the priority queue.
- Create a PriorityQueue class to implement priority queue operations.
- Create a HuffmanCodes class to implement methods for building the Huffman tree, getting codes, encoding text, and decoding text.
- Inside the main method, create an instance of HuffmanCodes and given input Hamming-encoded data.
- Build the Huffman tree using the given data.
- Encode the original data using the Huffman tree and get the encoded string.
- Decode the Hamming-encoded string using the Huffman tree and get the decoded data.
- 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
- Display the given original data.
- Print the characters from the Huffman tree along with their codes.
- Display the encoded string using the Huffman tree.
- Display the decoded data obtained from the Hamming-encoded string using the Huffman tree.
Time Complexity
- Building Huffman Tree: O(n log n) - Constructing the Huffman tree using a priority queue.
- Getting Codes: O(n) - Generating codes for each character in the Huffman tree.
- Encoding Text: O(n) - Encoding the original data using the Huffman tree.
- 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.
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