#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
#define EMPTY_STRING ""
// A Tree node
struct Node
{
char ch;
int freq;
Node *left, *right;
};
// Function to allocate a new tree node
Node* getNode(char ch, int freq, Node* left, Node* right)
{
Node* node = new Node();
node->ch = ch;
node->freq = freq;
node->left = left;
node->right = right;
return node;
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(const Node* l, const Node* r) const
{
// the highest priority item has the lowest frequency
return l->freq > r->freq;
}
};
// Utility function to check if Huffman Tree contains only a single node
bool isLeaf(Node* root) {
return root->left == nullptr && root->right == nullptr;
}
// Traverse the Huffman Tree and store Huffman Codes in a map.
void encode(Node* root, string str, unordered_map<char, string> &huffmanCode)
{
if (root == nullptr) {
return;
}
// found a leaf node
if (isLeaf(root)) {
huffmanCode[root->ch] = (str != EMPTY_STRING) ? str : "1";
}
encode(root->left, str + "0", huffmanCode);
encode(root->right, str + "1", huffmanCode);
}
// Traverse the Huffman Tree and decode the encoded string
void decode(Node* root, int &index, string str)
{
if (root == nullptr) {
return;
}
// found a leaf node
if (isLeaf(root))
{
cout << root->ch;
return;
}
index++;
if (str[index] == '0') {
decode(root->left, index, str);
}
else {
decode(root->right, index, str);
}
}
// Builds Huffman Tree and decodes the given input text
void buildHuffmanTree(string text)
{
// base case: empty string
if (text == EMPTY_STRING) {
return;
}
// count the frequency of appearance of each character
// and store it in a map
unordered_map<char, int> freq;
for (char ch: text) {
freq[ch]++;
}
// Create a priority queue to store live nodes of the Huffman tree
priority_queue<Node*, vector<Node*>, comp> pq;
// Create a leaf node for each character and add it
// to the priority queue.
for (auto pair: freq) {
pq.push(getNode(pair.first, pair.second, nullptr, nullptr));
}
// do till there is more than one node in the queue
while (pq.size() != 1)
{
// Remove the two nodes of the highest priority
// (the lowest frequency) from the queue
Node* left = pq.top(); pq.pop();
Node* right = pq.top(); pq.pop();
// create a new internal node with these two nodes as children and
// with a frequency equal to the sum of the two nodes' frequencies.
// Add the new node to the priority queue.
int sum = left->freq + right->freq;
pq.push(getNode('\0', sum, left, right));
}
// `root` stores pointer to the root of Huffman Tree
Node* root = pq.top();
// Traverse the Huffman Tree and store Huffman Codes
// in a map. Also, print them
unordered_map<char, string> huffmanCode;
encode(root, EMPTY_STRING, huffmanCode);
cout << "Huffman Codes are:\n" << endl;
for (auto pair: huffmanCode) {
cout << pair.first << " " << pair.second << endl;
}
cout << "\nThe original string is:\n" << text << endl;
// Print encoded string
string str;
for (char ch: text) {
str += huffmanCode[ch];
}
cout << "\nThe encoded string is:\n" << str << endl;
cout << "\nThe decoded string is:\n";
if (isLeaf(root))
{
// Special case: For input like a, aa, aaa, etc.
while (root->freq--) {
cout << root->ch;
}
}
else {
// Traverse the Huffman Tree again and this time,
// decode the encoded string
int index = -1;
while (index < (int)str.size() - 1) {
decode(root, index, str);
}
}
}
// Huffman coding algorithm implementation in C++
int main()
{
string text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
return 0;
}
Output:
Huffman Codes are:
c 11111
h 111100
f 11101
r 11100
t 11011
p 110101
i 1100
g 0011
l 00101
a 010
o 000
d 10011
H 00100
. 111101
s 0110
m 0111
e 110100
101
n 1000
u 10010
The original string is:
Huffman coding is a data compression algorithm.
The encoded string is:
00100100101110111101011101010001011111100010011110010000011101110001101010101011001101011011010101111110000111110101111001101000110011011000001000101010001010011000111001100110111111000111111101
The decoded string is:
Huffman coding is a data compression algorithm
Comments