Huffman Coding and Decoding Algorithm in C++

Huffman’s Coding algorithms is used for compression of data so that it doesn’t lose any information. Each symbol is converted into a binary code. In order to decompress the data and see the initial symbols, we need the frequencies of elements and the compressed data.

Huffman Coding uses prefix rules which assures that there is no ambiguity in the decoding process. The prefix rule states that no code is a prefix of another code.

This algorithm includes two parts: Building the Huffman Tree from the input characters; and Traversing the tree to assign codes to symbols.

// Huffman Coding and Decoding algorithm

#include <bits/stdc++.h>

using namespace std;

map<char, string> codesMap;
map<char, int> frequencyMap;

struct MinHeapNode
{
    char data;
    int frequency;
    MinHeapNode *left;
    MinHeapNode *right;

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

struct compare
{
    bool operator()(MinHeapNode* left, MinHeapNode* right)
    {
        return (left->frequency > right->frequency);
    }
};

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

void storeCodes(struct MinHeapNode* root, string inputString)
{
    if (root == NULL)
    {
        return;
    }

    if (root->data != '$')
    {
        codesMap[root->data] = inputString;
    }

    storeCodes(root->left, inputString + "0");
    storeCodes(root->right, inputString + "1");
}

priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;

void HuffmanCodes(int size)
{
    struct MinHeapNode *left, *right, *top;
    for (map<char, int>::iterator v = frequencyMap.begin(); v != frequencyMap.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->frequency + right->frequency);
        top->left = left;
        top->right = right;
        minHeap.push(top);
    }
    storeCodes(minHeap.top(), "");

    cout << "Characters and their Codes:\n";
    printCodes(minHeap.top(), "");
}

void calculateFrequency(string inputString)
{
    for (int i = 0; i < inputString.size(); i++)
    {
        frequencyMap[inputString[i]]++;
    }
}

string decodeString(struct MinHeapNode* root, string inputString)
{
    string answer = "";
    struct MinHeapNode* current = root;
    for (int i = 0; i < inputString.size(); i++)
    {
        if (inputString[i] == '0')
        {
            current = current->left;
        }
        else
        {
            current = current->right;
        }

        if (current->left == NULL && current->right == NULL)
        {
            answer += current->data;
            current = root;
        }
    }
    return answer + '\0';
}

string encodeHuffman(string inputString)
{
    string encodedString;
    calculateFrequency(inputString);
    HuffmanCodes(inputString.length());

    for (auto i: inputString)
    {
        encodedString += codesMap[i];
    }
    return encodedString;
}

int main()
{
    string inputString = "All falls into place";
    string encodedString;
    string decodedString;

    encodedString = encodeHuffman(inputString);
    cout << "\nEncoded String:\n" << encodedString << endl;

    decodedString = decodeString(minHeap.top(), encodedString);
    cout << "\nDecoded String:\n" << decodedString << endl;
    return 0;
}

Characters and their Codes: s: 0000 p: 0001 c: 0010 e: 0011 A: 0100 f: 0101 o: 0110 n: 0111 l: 10 : 110 a: 1110 i: 11110 t: 11111 Encoded String: 010010101100101111010100000110111100111111110110110000110111000100011 Decoded String: All falls into place