Huffman Decoding (Reverse Huffman Coding) in C++

In this tutorial, we are going to discuss Huffman Decoding in C++. Firstly we are going to have an introduction. Secondly, we will be having a demonstration by coding in C++.

Introduction to Huffman decoding

Huffman coding is a method in which we will enter the symbols with there frequency and the output will be the binary code for each symbol. This method is used for the compression of data. This is a lossless compression of data. Once the symbols are converted to the binary codes they will be replaced in the original data.

To get the data out of the compressed we have to perform decompression on the compressed data. To perform decompression on the data we need frequencies and the compressed data.

In this tutorial, we will be using the Huffman tree to solve the problem.

We require these steps for decompression of data:

  1. Start from root till we reach leaves.
  2. If the current bit is zero, move left.
  3. If the current bit is one then move right.
  4. When we reach leaf node we print the character and again start at first step.

Code to implement Huffman decoding

#include <bits/stdc++.h> 
#define MAX_TREE_HT 256 
using namespace std; 

map<char, string> codes; 

map<char, int> freq; 

struct MinHeapNode 
{ 
    char data;          
    int freq;           
    MinHeapNode *left, *right; 
  
    MinHeapNode(char data, int freq) 
    { 
        left = right = NULL; 
        this->data = data; 
        this->freq = freq; 
    } 
}; 

struct compare 
{ 
    bool operator()(MinHeapNode* l, MinHeapNode* r) 
    { 
        return (l->freq > r->freq); 
    } 
}; 

void printCodes(struct MinHeapNode* root, string str) 
{ 
    if (!root) 
        return; 
    if (root->data != '$') 
        cout << root->data << ": " << str << "\n"; 
    printCodes(root->left, str + "0"); 
    printCodes(root->right, str + "1"); 
} 

void storeCodes(struct MinHeapNode* root, string str) 
{ 
    if (root==NULL) 
        return; 
    if (root->data != '$') 
        codes[root->data]=str; 
    storeCodes(root->left, str + "0"); 
    storeCodes(root->right, str + "1"); 
} 
  
priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap; 

void HuffmanCodes(int size) 
{ 
    struct MinHeapNode *left, *right, *top; 
    for (map<char, int>::iterator v=freq.begin(); v!=freq.end(); v++) 
        minHeap.push(new MinHeapNode(v->first, v->second)); 
    while (minHeap.size() != 1) 
    { 
        left = minHeap.top(); 
        minHeap.pop(); 
        right = minHeap.top(); 
        minHeap.pop(); 
        top = new MinHeapNode('$', left->freq + right->freq); 
        top->left = left; 
        top->right = right; 
        minHeap.push(top); 
    } 
    storeCodes(minHeap.top(), ""); 
} 

void calcFreq(string str, int n) 
{ 
    for (int i=0; i<str.size(); i++) 
        freq[str[i]]++; 
} 

string decode_file(struct MinHeapNode* root, string s) 
{ 
    string ans = ""; 
    struct MinHeapNode* curr = root; 
    for (int i=0;i<s.size();i++) 
    { 
        if (s[i] == '0') 
           curr = curr->left; 
        else
           curr = curr->right; 
  
        if (curr->left==NULL and curr->right==NULL) 
        { 
            ans += curr->data; 
            curr = root; 
        } 
    } 
    return ans+'\0'; 
} 
  
int main() 
{ 
    string str = "Yogender"; 
    string encodedString, decodedString; 
    calcFreq(str, str.length()); 
    HuffmanCodes(str.length()); 
    cout << "Character With there Frequencies:\n"; 
    for (auto v=codes.begin(); v!=codes.end(); v++) 
        cout << v->first <<' ' << v->second << endl; 
  
    for (auto i: str) 
        encodedString+=codes[i]; 
  
    cout << "\nEncoded Huffman data:\n" << encodedString << endl; 
  
    decodedString = decode_file(minHeap.top(), encodedString); 
    cout << "\nDecoded Huffman Data:\n" << decodedString << endl; 
    return 0; 
}

Input and Output:

Character With there Frequencies:
Y 100
d 011
e 00
g 111
n 110
o 101
r 010

Encoded Huffman data:
1001011110011001100010

Decoded Huffman Data:
Yogender

Conclusion

This tutorial shows how to perform Huffman Decoding in C++. Done using heap and Huffman tree. Concepts demonstrated in this tutorial are the usage of heap, Huffman coding and Coding and Decoding.

Also Checkout:

How to Demonstrate Huffman Coding in C++

Heap in C++

Leave a Reply

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