# Huffman Compression

Building an optimal prefix-free code by repeatedly merging the two least frequent symbols, giving short codes to common symbols.

**Rests on:** Data Compression

*Mathematical Foundations · Information Theory*


## Why learn this

You send emails with attachments, stream videos, or save documents every day. All those files take up space on hard drives and require time to travel over networks. This technique explains exactly how software shrinks a large file—like a photo or a text document—so it becomes smaller, without losing any single word or pixel. It matters because it is the reason your email attachments arrive quickly and why you can store thousands of hours of music on a small device. You will see this mechanism every time you zip a folder or receive a compacted web page.


## The intuition

Imagine you have to send a message made of only four letters: A, B, C, and D. In a standard computer system, each letter is stored as a fixed number of bits (like binary digits). For example, A is 00, B is 01, C is 10, and D is 11. This means every letter takes exactly 2 bits to store. That is simple, but it is wasteful if some letters appear much more often than others.

Suppose you have a long text where A appears 50% of the time, B 25% of the time, C 12.5% of the time, and D 12.5% of the time. You are using 2 bits for every letter, but you could do better by giving shorter codes to frequent symbols and longer codes to rare ones. 

If we give A the code '0' (1 bit), B the code '10' (2 bits), C the code '110' (3 bits), and D the code '111' (3 bits), the average number of bits per letter drops significantly.

But there is a catch. You must be careful about how you assign these codes. If you use '0' for A and '01' for B, then when you see the sequence '01', you cannot tell if it represents A followed by B (0 then 01) or just B alone (01). To prevent this confusion, we need a special rule: no code can be the beginning of another code. This ensures that every sequence of bits has only one possible interpretation. Huffman coding builds exactly such a code, step-by-step, to ensure it is as efficient as possible.


## An analogy

Think of a librarian organizing books who wants to make it fastest for patrons to reach the most popular titles. She knows how many people check out each book. She starts by taking the two least checked-out books and tying them together with a single string, creating a new 'bundle' that has the combined popularity of those two books. Then she looks at all the remaining individual books and bundles again, picks the two least popular items (whether they are single books or bundles), ties them together, and creates a larger bundle. She keeps doing this until there is just one giant bundle containing every book. The structure she builds looks like an upside-down tree. The most popular books end up closest to the trunk of the tree (short path from the top), while the least popular books are far out on the branches (long path). This works beautifully for organizing access, but the analogy breaks down in one way: in a library, you can just look at the spine to find a book. In this coding method, the instructions must be unambiguous—like saying 'turn left' versus 'turn left, then right.' If 'turn left' is a complete instruction, you cannot also use it as the start of another instruction, or people would never know when to stop following directions.

This analogy is limited because a librarian can see all the books at once, while this coding method builds the structure purely by comparing frequencies without seeing the entire text beforehand.


## Definition

Huffman coding is a method for shrinking data without losing any information by creating variable-length codes where no code is the start of another, assigning shorter codes to more frequent symbols by repeatedly merging the two least frequent items into new groups.


## How it connects

This concept sits beside Shannon entropy, which calculates the theoretical minimum number of bits needed to represent each symbol in a message based on their probability. It also relates to the greedy algorithm strategy, where you make the best local choice at each step (merging the smallest frequencies) to build up to the overall solution.


## The mathematics

Huffman coding is a procedure from a branch of mathematics called information theory. Information theory asks: 'how can we measure information, and how can we transmit it efficiently?' The specific operation we need is not a dot product or a derivative; it's just counting and comparing. We count how many times each symbol appears in our message. Then we repeatedly take the two symbols with the smallest counts and combine them into a new 'node' whose count is the sum of the two. We keep doing this until we have combined everything into a single tree. This is called a 'greedy' algorithm because at each step we make the choice that seems best right now (merging the two smallest), and this simple rule turns out to give the best possible code overall.

The Huffman algorithm can be described as: while there is more than one node, take the two nodes with the smallest frequencies f1 and f2, replace them with a new node whose frequency is f1 + f2, and make the two old nodes its children. The resulting tree defines the prefix-free code. The 'weight' of a code is its length; the optimality is guaranteed by the fact that this greedy choice at each step leads to the minimum total weighted path length.


## A worked example

```
We have a message with these symbols and frequencies: A: 5, B: 9, C: 12, D: 13, E: 16, F: 45.

Step 1: Step 1: Merge A (5) and B (9) → new node AB (14).   # The two smallest counts are 5 and 9.
Step 2: Step 2: Frequencies now: AB (14), C (12), D (13), E (16), F (45). Merge C (12) and D (13) → CD (25).   # The two smallest are now 12 and 13.
Step 3: Step 3: Frequencies now: AB (14), CD (25), E (16), F (45). Merge AB (14) and E (16) → ABE (30).   # The two smallest are 14 and 16.
Step 4: Step 4: Frequencies now: CD (25), ABE (30), F (45). Merge CD (25) and ABE (30) → CDABE (55).   # The two smallest are 25 and 30.
Step 5: Step 5: Frequencies now: CDABE (55) and F (45). Merge them → root (100).   # Only two nodes left.

Result: We have built a binary tree. Now assign codes: starting from the root, each left branch is '0' and each right branch is '1'. The code for each symbol is the path from the root to that symbol. For example, F (45) might be '0', and the other symbols get longer codes. The average code length is now much shorter than if we used a fixed 3-bit code (which would need 3 bits for 6 symbols).
```


## From scratch, in Python

```python
class Node:
    def __init__(self, symbol, freq):
        self.symbol = symbol
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq


def build_huffman_tree(frequencies):
    # frequencies is a dict like {'A': 5, 'B': 9, ...}
    nodes = []
    for symbol, freq in frequencies.items():
        nodes.append(Node(symbol, freq))

    while len(nodes) > 1:
        # sort by frequency (we'll use a proper priority queue in practice)
        nodes.sort(key=lambda x: x.freq)
        left = nodes.pop(0)  # smallest
        right = nodes.pop(0) # second smallest
        parent = Node(None, left.freq + right.freq)
        parent.left = left
        parent.right = right
        nodes.append(parent)

    return nodes[0]  # root of the tree


def generate_codes(node, prefix="", codebook=None):
    if codebook is None:
        codebook = {}
    if node.symbol is not None:
        codebook[node.symbol] = prefix
    else:
        generate_codes(node.left, prefix + "0", codebook)
        generate_codes(node.right, prefix + "1", codebook)
    return codebook

# Example usage
frequencies = {'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45}
root = build_huffman_tree(frequencies)
codes = generate_codes(root)
print(codes)  # {'F': '0', 'A': '100', 'B': '101', 'C': '110', 'D': '111'} (example, order may vary)
```


## What the code does

This code defines a `Node` class to represent a node in the Huffman tree. Each node has a `symbol` (if it's a leaf), a `freq`, and left/right children. The `__lt__` method lets us compare nodes by frequency. The `build_huffman_tree` function takes a dictionary of symbol-to-frequency pairs, creates a leaf node for each, and then repeatedly merges the two nodes with the smallest frequencies, creating a new parent node. This parent node has no symbol (None) but its frequency is the sum of its children. The `generate_codes` function recursively walks the tree: if it's a leaf, it records the code (the path of 0s and 1s); otherwise, it recurses on the left (adding '0') and right (adding '1'). Finally, we print the codebook. Note: we used a simple list and sorting for clarity, but a real implementation would use a priority queue for efficiency.


## Common misconceptions

**Huffman coding is lossy** — I thought Huffman coding throws away some of the data to make it smaller, like JPEG does.

Huffman coding is a lossless technique. You can perfectly reconstruct the original data from the compressed stream, symbol by symbol. The compression comes from using shorter codes for common symbols, not from discarding information. In fact: Huffman coding is lossless. The decoded output is exactly the same as the input.

**The codes must be fixed length** — I thought every symbol must have a code of the same length, like in ASCII.

Fixed-length codes are simpler but inefficient when symbol frequencies vary. Huffman allows variable-length codes, where common symbols have short codes and rare symbols have long codes. In fact: Huffman codes are variable-length, with the length inversely proportional to the frequency.

**The codes can be any bit pattern** — I can just assign any shorter code to the frequent symbols, like 'A' = 0, 'B' = 1, 'C' = 01.

If codes are not prefix-free, you cannot uniquely decode the stream. For example, if 'C' is '01' and 'A' is '0', then the stream '01' could be 'C' or 'A' followed by something else. Huffman ensures no code is a prefix of another, so decoding is unambiguous. In fact: Every code is a prefix-free code, guaranteeing unique decodability.

**It's only useful for text** — Huffman works only on letters, not on arbitrary binary data.

Huffman works on any set of symbols: bytes, characters, or even words. You just count the frequencies of whatever your symbols are and build the tree accordingly. In fact: Huffman is general-purpose and can compress any sequence of symbols, be it ASCII characters, bytes, or larger chunks.


## In short

Huffman coding is a greedy, lossless compression algorithm that builds a prefix-free code by repeatedly merging the two least frequent symbols. It gives shorter codes to more common symbols, leading to a shorter overall message. The algorithm is provably optimal for symbol-wise coding, meaning no other prefix-free code can achieve a shorter average length. This concept is foundational to information theory, and its close connection to entropy is why it's the first thing you should understand before diving into concepts like cross-entropy loss.


## Where this is used

Huffman coding is used in many real-world compression tools. The most famous example is in the DEFLATE algorithm, which is used in gzip, PNG images, and ZIP files. In these, Huffman coding is applied to the output of a previous step (like LZ77) to compress the data further. It's also used in fax machines and in MP3 audio encoding. In the context of AI and machine learning, Huffman coding is not typically at the core of neural network training, but it is used in some large language model (LLM) serving systems to compress token vocabularies before they are sent over a network. For example, when a model runs on a phone (small model), the vocabulary file (a list of all tokens) could be compressed with Huffman coding to reduce download size. Similarly, in retrieval-augmented generation (RAG) pipelines, large document collections are often stored compressed, and Huffman coding is a standard lossless method. In summary, while not central to the math of deep learning, Huffman coding is a ubiquitous utility in the systems that support AI, from file formats to communication protocols.


---

Read this on the web: https://basavapurushottam.com/learn-ai/huffman-compression
