Offensive Security Researcher & Quantum Cryptography Analyst

Huffman Coding Compression Algorithm: Working, Explanation, and Data Compression

Abdul Wahab Junaid
Huffman coding compression algorithm and working of this algorithm

I consider Huffman coding one of the cleanest examples of how a simple idea, applied carefully, can produce an optimal result. It is a lossless data compression algorithm that assigns shorter binary codes to more frequently occurring symbols and longer codes to less frequent ones, reducing the overall size of encoded data compared to using fixed-length codes for every symbol. I find it remarkable that this algorithm, invented as a student class assignment, remains a foundational building block inside many modern compression formats.

History and Background

I trace Huffman coding to 1952, when David A. Huffman, then a graduate student at MIT, developed it while working on a term paper for a class taught by Robert Fano. The assignment was to find the most efficient method of representing symbols using binary codes, and Huffman’s professor, along with Claude Shannon, had already developed a similar but suboptimal technique known as Shannon-Fano coding. Rather than take the final exam for the course, Huffman was given the option to solve this open problem, and he devised a bottom-up approach using a greedy algorithm that proved to be provably optimal, unlike the Shannon-Fano method that came before it. His paper, “A Method for the Construction of Minimum-Redundancy Codes,” was published in 1952, and the technique has been a staple of information theory and computer science ever since.

Problem Statement

Huffman coding addresses the problem of representing a set of symbols (such as characters in a text file) using binary codes in a way that minimizes the total number of bits needed, given that some symbols occur more frequently than others. If I used a fixed-length code, like ASCII’s 8 bits per character, I would waste bits on common characters and could not take advantage of the fact that some symbols appear far more often than others in typical data. The problem is to find a variable-length prefix code, where no code is a prefix of any other code (ensuring unambiguous decoding), that minimizes the expected number of bits needed to encode a message given the known frequency of each symbol.

Core Concepts

Terms I use throughout my explanation:

How It Works

I break Huffman coding into the following steps:

  1. I count the frequency of each distinct symbol in the input data.
  2. I create a leaf node for each symbol, storing its frequency, and insert all these nodes into a min-priority queue ordered by frequency.
  3. While more than one node remains in the queue, I remove the two nodes with the smallest frequencies, create a new internal node whose frequency is the sum of the two, set the two removed nodes as its left and right children, and insert this new node back into the queue.
  4. I repeat step 3 until only one node remains in the queue; this node is the root of the completed Huffman tree.
  5. I traverse the tree from the root to each leaf, assigning a 0 for each left branch and a 1 for each right branch (or vice versa), building the binary code for each symbol.
  6. I encode the original data by replacing each symbol with its corresponding binary code, and I decode by walking the tree bit by bit from the root, outputting a symbol each time I reach a leaf and returning to the root.

Working Principle

I find the core insight of Huffman coding to be that combining the two least frequent nodes at each step, and pushing the result back into consideration, naturally builds a tree where frequently occurring symbols end up closer to the root (and thus get shorter codes), while rare symbols get pushed deeper into the tree (and get longer codes). This greedy strategy works because of a key property: in the optimal encoding tree, the two least frequent symbols must be siblings at the deepest level of the tree, since swapping them with any other pair of symbols at a shallower level could only increase or maintain the total encoded length, never decrease it. Because this property holds at every step of tree construction, the greedy approach of always merging the two smallest nodes provably leads to a globally optimal prefix code.

Mathematical Foundation

The expected length of the encoded message, given a code assignment where symbol $i$ has probability $p_i$ and code length $\ell_i$, is:

$$L = \sum_{i} p_i \ell_i$$

Huffman coding produces a code that minimizes $L$ among all prefix codes, but it is worth noting this optimal $L$ is generally not quite as low as the theoretical entropy limit given by Shannon’s source coding theorem:

$$H = -\sum_{i} p_i \log_2 p_i$$

The relationship between the two is bounded as:

$$H \leq L < H + 1$$

meaning Huffman coding’s expected code length is always within one bit of the theoretical minimum entropy, and it achieves the entropy exactly when all symbol probabilities happen to be exact negative powers of two (like $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}$, and so on).

Diagrams

flowchart TD
    A[Count symbol frequencies] --> B[Create leaf node for each symbol]
    B --> C[Insert all nodes into min-priority queue]
    C --> D{More than one node in queue?}
    D -->|Yes| E[Remove two smallest-frequency nodes]
    E --> F[Create new internal node with combined frequency]
    F --> G[Insert new node back into queue]
    G --> D
    D -->|No| H[Remaining node is the Huffman tree root]
    H --> I[Traverse tree to assign binary codes]

Pseudocode

function HUFFMAN_BUILD_TREE(symbols_with_frequencies):
    queue = min_priority_queue()
    for (symbol, freq) in symbols_with_frequencies:
        queue.insert(LeafNode(symbol, freq))

    while queue.size() > 1:
        left = queue.extract_min()
        right = queue.extract_min()
        merged = InternalNode(
            frequency = left.frequency + right.frequency,
            left_child = left,
            right_child = right
        )
        queue.insert(merged)

    return queue.extract_min()  // this is the root

function HUFFMAN_ASSIGN_CODES(node, current_code, code_table):
    if node is a leaf:
        code_table[node.symbol] = current_code
        return
    HUFFMAN_ASSIGN_CODES(node.left_child, current_code + "0", code_table)
    HUFFMAN_ASSIGN_CODES(node.right_child, current_code + "1", code_table)

function HUFFMAN_ENCODE(data, code_table):
    encoded = ""
    for symbol in data:
        encoded = encoded + code_table[symbol]
    return encoded

function HUFFMAN_DECODE(encoded_bits, tree_root):
    decoded = ""
    current = tree_root
    for bit in encoded_bits:
        if bit == "0":
            current = current.left_child
        else:
            current = current.right_child
        if current is a leaf:
            decoded = decoded + current.symbol
            current = tree_root
    return decoded

Step-by-Step Example

I will walk through encoding the string "ABRACADABRA".

  1. I count frequencies: A: 5, B: 2, R: 2, C: 1, D: 1.
  2. I create leaf nodes for each symbol and insert them into a min-priority queue: [C:1, D:1, B:2, R:2, A:5].
  3. I remove the two smallest, C:1 and D:1, and merge them into a new node CD:2. Queue becomes [B:2, R:2, CD:2, A:5].
  4. I remove the two smallest, B:2 and R:2 (order among equal frequencies can vary), and merge into BR:4. Queue becomes [CD:2, BR:4, A:5].
  5. I remove CD:2 and BR:4, merging into CDBR:6. Queue becomes [A:5, CDBR:6].
  6. I remove A:5 and CDBR:6, merging into the root Root:11. Queue now has just one node, so I stop.
  7. I traverse the tree: A gets a short code since it is a direct child of the root, for example 0; B and R end up as 100 and 101; C and D end up as 110 and 111 (exact codes depend on tie-breaking order, but the pattern of shorter codes for more frequent symbols holds).
  8. Encoding "ABRACADABRA" with these codes produces a bit string considerably shorter than the 88 bits (11 characters times 8 bits) that fixed-length ASCII encoding would require.

Time Complexity

Building the frequency table takes $O(n)$ time, where $n$ is the length of the input data. Building the Huffman tree itself takes $O(k \log k)$ time, where $k$ is the number of distinct symbols, since each of the $k – 1$ merge operations involves two extract-min operations and one insert operation on a priority queue, each costing $O(\log k)$. Assigning codes by traversing the tree takes $O(k)$ time. Encoding the actual data takes $O(n)$ time, since I look up each symbol’s precomputed code. In total, Huffman coding runs in $O(n + k \log k)$ time, which for typical text data where $k$ (the alphabet size) is much smaller than $n$ (the data length), behaves essentially linearly in the size of the input.

Space Complexity

I need $O(k)$ space to store the frequency table and the priority queue, where $k$ is the number of distinct symbols, and $O(k)$ space for the resulting Huffman tree, since a tree with $k$ leaves has at most $2k – 1$ total nodes. The code table also requires $O(k)$ space, though the total number of bits across all codes can vary depending on the frequency distribution. The encoded output itself requires space proportional to the compressed size of the data, which by design is smaller than or equal to the original fixed-length encoding.

Correctness Analysis

I can justify Huffman coding’s optimality through an exchange argument, a classic technique in greedy algorithm proofs. I first show that in any optimal prefix code tree, the two least frequent symbols can always be placed as siblings at the maximum depth without increasing the total encoded length, since if they were not siblings at the deepest level, I could always swap them with whichever symbols are there without making the encoding worse. I then use an inductive argument: if I combine the two least frequent symbols into a single “merged” symbol with combined frequency, and I can show that an optimal code for the reduced problem (with one fewer symbol) extends to an optimal code for the original problem by splitting that merged symbol back into its two children, then by induction, building the tree bottom-up by always merging the two smallest nodes at each step produces a globally optimal solution. Huffman’s original 1952 paper contains the formal version of this argument.

Advantages

Disadvantages

Applications

I see Huffman coding used as a component inside many widely used compression formats and standards: the DEFLATE algorithm (used in ZIP files, gzip, and PNG images) uses Huffman coding as its final entropy-coding stage after LZ77-style dictionary compression; JPEG image compression uses Huffman coding to compress the quantized frequency coefficients; MP3 and other multimedia codecs use Huffman-like entropy coding stages; and many custom file formats and network protocols use it as a general-purpose, simple, and effective final compression step.

Implementation in C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SYMBOLS 256

typedef struct Node {
    unsigned char symbol;
    int frequency;
    struct Node *left, *right;
} Node;

typedef struct {
    Node *nodes[MAX_SYMBOLS];
    int size;
} MinHeap;

Node *create_node(unsigned char symbol, int frequency, Node *left, Node *right) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->symbol = symbol;
    node->frequency = frequency;
    node->left = left;
    node->right = right;
    return node;
}

void heap_push(MinHeap *heap, Node *node) {
    int i = heap->size++;
    heap->nodes[i] = node;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap->nodes[parent]->frequency <= heap->nodes[i]->frequency) break;
        Node *tmp = heap->nodes[parent];
        heap->nodes[parent] = heap->nodes[i];
        heap->nodes[i] = tmp;
        i = parent;
    }
}

Node *heap_pop(MinHeap *heap) {
    Node *top = heap->nodes[0];
    heap->nodes[0] = heap->nodes[--heap->size];
    int i = 0;
    while (1) {
        int left = 2 * i + 1, right = 2 * i + 2, smallest = i;
        if (left < heap->size && heap->nodes[left]->frequency < heap->nodes[smallest]->frequency)
            smallest = left;
        if (right < heap->size && heap->nodes[right]->frequency < heap->nodes[smallest]->frequency)
            smallest = right;
        if (smallest == i) break;
        Node *tmp = heap->nodes[i];
        heap->nodes[i] = heap->nodes[smallest];
        heap->nodes[smallest] = tmp;
        i = smallest;
    }
    return top;
}

void assign_codes(Node *node, char *code, int depth, char codes[MAX_SYMBOLS][MAX_SYMBOLS]) {
    if (!node->left && !node->right) {
        code[depth] = '\0';
        strcpy(codes[node->symbol], code);
        return;
    }
    code[depth] = '0';
    assign_codes(node->left, code, depth + 1, codes);
    code[depth] = '1';
    assign_codes(node->right, code, depth + 1, codes);
}

int main() {
    const char *input = "ABRACADABRA";
    int freq[MAX_SYMBOLS] = {0};

    for (int i = 0; input[i]; i++) freq[(unsigned char)input[i]]++;

    MinHeap heap = {.size = 0};
    for (int i = 0; i < MAX_SYMBOLS; i++) {
        if (freq[i] > 0) {
            heap_push(&heap, create_node((unsigned char)i, freq[i], NULL, NULL));
        }
    }

    while (heap.size > 1) {
        Node *left = heap_pop(&heap);
        Node *right = heap_pop(&heap);
        Node *merged = create_node(0, left->frequency + right->frequency, left, right);
        heap_push(&heap, merged);
    }

    Node *root = heap_pop(&heap);

    char codes[MAX_SYMBOLS][MAX_SYMBOLS] = {{0}};
    char buffer[MAX_SYMBOLS];
    assign_codes(root, buffer, 0, codes);

    printf("Symbol : Frequency : Code\n");
    for (int i = 0; i < MAX_SYMBOLS; i++) {
        if (freq[i] > 0) {
            printf("  %c    :    %d      :  %s\n", i, freq[i], codes[i]);
        }
    }

    printf("\nEncoded: ");
    for (int i = 0; input[i]; i++) {
        printf("%s", codes[(unsigned char)input[i]]);
    }
    printf("\n");

    return 0;
}

Sample Input and Output

Running the program on the input "ABRACADABRA" produces a frequency table showing A occurring 5 times, B and R occurring 2 times each, and C and D occurring once each. The resulting codes assign the shortest code (one bit) to A, medium-length codes to B and R, and the longest codes to C and D. The final encoded bit string for the full 11-character input ends up shorter than the 88 bits required by fixed-length 8-bit ASCII encoding, typically around 23 to 27 bits depending on the exact tie-breaking order used when frequencies are equal, demonstrating meaningful compression on even this small example.

Optimization Techniques

I have found a few techniques useful when implementing or applying Huffman coding efficiently:

Common Mistakes

I often see mistakes where developers forget to store or transmit the Huffman tree (or an equivalent canonical code table) alongside the encoded data, making decoding impossible without it. Another common mistake is assuming Huffman coding always outperforms fixed-length encoding, when in fact for very small inputs or nearly uniform frequency distributions, the overhead of the tree can make the total output larger than a simple fixed-length encoding. I also see confusion between building the tree with ties broken inconsistently between encoding and decoding, which, if not handled deterministically, can lead to a mismatch between the tree used to encode and the tree used to decode.

Further Reading

Exit mobile version