12.Huffman Coding

Huffman coding is a lossless data compression algorithm.

Consider the string ABRACADABRA.

image

Input characters are only present in the leaves. Internal nodes have a character value of ϕ (NULL). We can determine that our values for characters are:

A - 0
B - 111
C - 1100
D - 1101
R - 10

Our Huffman encoded string is:

A  B    R  A   C     A    D     A   B    R  A
0 111  10  0 1100    0  1101    0  111   10 0
or
01111001100011010111100

Huffman Decoding

void decode_huff(node *root, string s)
{

    string res = "";
    int n = s.length();
    int i = 0;
    while (i < n)
    {
        node *t = root;
        queue<node *> q;
        q.push(t);

        while (!q.empty())
        {
            t = q.front();
            q.pop();

            if (!t->left && !t->right)
            {
                res += t->data;
                break;
            }

            if (s[i] == '0')
            {
                q.push(t->left);
            }
            else if (s[i] == '1')
            {
                q.push(t->right);
            }
            
            i++;
        }
    }
    cout << res;
}