huffman_coding_code.cpp

#include <iostream>
#include <string>
using namespace std;

const int MAX_CHARS = 256;
const int MAX_CODE  = 256;

struct Node {
    char   ch;
    int    freq;
    int    left;
    int    right;
    bool   isLeaf;
};

struct MinHeap {
    int  data[MAX_CHARS * 2];
    int  size;

    void init() { size = 0; }

    void swapAt(int i, int j) {
        int tmp  = data[i];
        data[i]  = data[j];
        data[j]  = tmp;
    }

    void heapifyUp(int i, Node pool[]) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (pool[data[parent]].freq > pool[data[i]].freq) {
                swapAt(parent, i);
                i = parent;
            } else {
                break;
            }
        }
    }

    void heapifyDown(int i, Node pool[]) {
        while (true) {
            int left  = 2 * i + 1;
            int right = 2 * i + 2;
            int smallest = i;

            if (left < size &&
                pool[data[left]].freq < pool[data[smallest]].freq)
                smallest = left;

            if (right < size &&
                pool[data[right]].freq < pool[data[smallest]].freq)
                smallest = right;

            if (smallest != i) {
                swapAt(i, smallest);
                i = smallest;
            } else {
                break;
            }
        }
    }

    void insert(int nodeIdx, Node pool[]) {
        data[size] = nodeIdx;
        size++;
        heapifyUp(size - 1, pool);
    }

    int extractMin(Node pool[]) {
        int minIdx = data[0];
        size--;
        data[0] = data[size];
        heapifyDown(0, pool);
        return minIdx;
    }
};

int buildHuffmanTree(Node pool[], int &poolSize,
                     char chars[], int freqs[], int n) {
    MinHeap heap;
    heap.init();

    for (int i = 0; i < n; i++) {
        pool[i].ch     = chars[i];
        pool[i].freq   = freqs[i];
        pool[i].left   = -1;
        pool[i].right  = -1;
        pool[i].isLeaf = true;
        heap.insert(i, pool);
    }
    poolSize = n;

    while (heap.size > 1) {
        int leftIdx  = heap.extractMin(pool);
        int rightIdx = heap.extractMin(pool);

        int newIdx = poolSize;
        poolSize++;

        pool[newIdx].ch     = '\0';
        pool[newIdx].freq   = pool[leftIdx].freq + pool[rightIdx].freq;
        pool[newIdx].left   = leftIdx;
        pool[newIdx].right  = rightIdx;
        pool[newIdx].isLeaf = false;

        heap.insert(newIdx, pool);
    }

    return heap.extractMin(pool);
}

void generateCodes(Node pool[], int nodeIdx,
                   int code[], int depth,
                   int  codeTable[][MAX_CODE],
                   int  codeLengths[]) {
    if (nodeIdx == -1) return;

    if (pool[nodeIdx].isLeaf) {
        unsigned char c = pool[nodeIdx].ch;
        codeLengths[c] = depth;
        for (int i = 0; i < depth; i++) {
            codeTable[c][i] = code[i];
        }
        if (depth == 0) {
            codeTable[c][0] = 0;
            codeLengths[c]  = 1;
        }
        return;
    }

    code[depth] = 0;
    generateCodes(pool, pool[nodeIdx].left,
                  code, depth + 1,
                  codeTable, codeLengths);

    code[depth] = 1;
    generateCodes(pool, pool[nodeIdx].right,
                  code, depth + 1,
                  codeTable, codeLengths);
}

void encodeString(const string &text,
                  int codeTable[][MAX_CODE],
                  int codeLengths[]) {
    cout << "\nEncoded bitstream:\n  ";
    for (int i = 0; i < (int)text.size(); i++) {
        unsigned char c = text[i];
        for (int b = 0; b < codeLengths[c]; b++) {
            cout << codeTable[c][b];
        }
        cout << " ";
    }
    cout << "\n";
}

int countFrequencies(const string &text,
                     char chars[], int freqs[]) {
    int freq[MAX_CHARS] = {0};

    for (int i = 0; i < (int)text.size(); i++) {
        freq[(unsigned char)text[i]]++;
    }

    int n = 0;
    for (int i = 0; i < MAX_CHARS; i++) {
        if (freq[i] > 0) {
            chars[n] = (char)i;
            freqs[n] = freq[i];
            n++;
        }
    }
    return n;
}

void printFrequencyTable(char chars[], int freqs[], int n) {
    cout << "\n------------------------------------------\n";
    cout << "  Char   Frequency\n";
    cout << "------------------------------------------\n";
    for (int i = 0; i < n; i++) {
        if (chars[i] == ' ')
            cout << "  ' '   " << freqs[i] << "\n";
        else
            cout << "   " << chars[i] << "     " << freqs[i] << "\n";
    }
    cout << "------------------------------------------\n";
}

void printCodeTable(char chars[], int n,
                    int codeTable[][MAX_CODE],
                    int codeLengths[]) {
    int totalBitsFixed    = 0;
    int totalBitsHuffman  = 0;

    cout << "\n------------------------------------------\n";
    cout << "  Char   Code\n";
    cout << "------------------------------------------\n";
    for (int i = 0; i < n; i++) {
        unsigned char c = chars[i];
        if (c == ' ')
            cout << "  ' '   ";
        else
            cout << "   " << (char)c << "     ";

        for (int b = 0; b < codeLengths[c]; b++) {
            cout << codeTable[c][b];
        }
        cout << "  (length " << codeLengths[c] << ")\n";
    }
    cout << "------------------------------------------\n";
}

void printCompressionStats(const string &text,
                           char chars[], int freqs[], int n,
                           int codeLengths[]) {
    int totalBitsFixed   = (int)text.size() * 8;
    int totalBitsHuffman = 0;
    for (int i = 0; i < n; i++) {
        unsigned char c = chars[i];
        totalBitsHuffman += freqs[i] * codeLengths[c];
    }

    cout << "\n------------------------------------------\n";
    cout << "  Compression Statistics\n";
    cout << "------------------------------------------\n";
    cout << "  Original size  (8-bit ASCII): "
         << totalBitsFixed   << " bits\n";
    cout << "  Compressed size (Huffman)   : "
         << totalBitsHuffman << " bits\n";

    if (totalBitsFixed > 0) {
        float ratio = 100.0f - (totalBitsHuffman * 100.0f / totalBitsFixed);
        cout << "  Space saved                 : "
             << ratio << "%\n";
    }
    cout << "------------------------------------------\n";
}

int main() {
    cout << "======================================\n";
    cout << "    Huffman Coding  -  Greedy\n";
    cout << "======================================\n\n";

    string text;
    cout << "Enter the text to encode:\n  ";
    getline(cin, text);

    if (text.empty()) {
        cout << "No text entered. Exiting.\n";
        return 0;
    }

    char chars[MAX_CHARS];
    int  freqs[MAX_CHARS];
    int  n = countFrequencies(text, chars, freqs);

    cout << "\nFrequency table:";
    printFrequencyTable(chars, freqs, n);

    Node pool[MAX_CHARS * 2];
    int  poolSize = 0;
    int  root = buildHuffmanTree(pool, poolSize, chars, freqs, n);

    int codeTable[MAX_CHARS][MAX_CODE] = {};
    int codeLengths[MAX_CHARS]         = {};
    int tempCode[MAX_CODE]             = {};
    generateCodes(pool, root, tempCode, 0, codeTable, codeLengths);

    cout << "\nHuffman code table:";
    printCodeTable(chars, n, codeTable, codeLengths);

    encodeString(text, codeTable, codeLengths);

    printCompressionStats(text, chars, freqs, n, codeLengths);

    cout << "\n======================================\n";
    cout << "  Complexity: O(n log n)  [heap ops]\n";
    cout << "======================================\n";

    return 0;
}