---
title: 'Huffman Coding'
source: 'https://academia.sh/en/courses/algorithms/huffman-coding'
course: Algorithms
language: en
updated: '2026-08-17T18:07:46+00:00'
license: 'CC BY-SA 4.0'
---

# Huffman Coding

Variable-length prefix-free codes, greedy tree construction, the optimality argument, the entropy bound, and the method's limits.

The final question of text algorithms differs from search: storing the same
information in **less space**.

Fixed-length coding assigns an equal number of bits to every symbol; the character
encodings in the How Computers Work course followed this scheme. Symbols, however, do
not occur with equal frequency. Giving a short code to a frequent symbol and a long code
to a rare one lowers the total length.

## Prefix-Free Codes

Variable length creates an ambiguity: if `A → 0` and `B → 01` are assigned, the sequence
`001` can be read as the start of either `AB` or `AA…`.

The solution is a **prefix-free code**: no symbol's code may be the prefix of another
symbol's code. Such a code decodes unambiguously — as soon as the bits read so far match
a code, that symbol is settled.

Prefix-free codes correspond exactly to binary trees: symbols sit at the leaves, and a
code is the sequence of bits (left 0, right 1) on the path from the root to a leaf. The
condition of stopping at a leaf is exactly the prefix-free condition.

A symbol's code length is the depth of its leaf. The goal is to minimize the weighted
sum of depths:

$$
\text{cost} = \sum_{i} f_i \cdot d_i
$$

Here $f_i$ is the symbol's frequency and $d_i$ is the depth of its leaf.

## Greedy Construction

The Huffman method builds the tree **from the leaves toward the root**: the two rarest
symbols are merged and treated as a single node, and the process continues until a
single node remains.

The intuition is this: the two rarest symbols deserve the deepest leaves; merging them
is the step that increases the cost the least.

```python
import heapq
from collections import Counter


def huffman_codes(frequencies: dict[str, int]) -> dict[str, str]:
    """Symbol → binary code mapping."""
    if len(frequencies) == 1:                    # special case: a single symbol
        return {next(iter(frequencies)): "0"}

    counter = 0
    heap: list[tuple[int, int, dict[str, str]]] = []
    for symbol, f in sorted(frequencies.items()):   # fixed order: the heap is unstable on ties
        heapq.heappush(heap, (f, counter, {symbol: ""}))
        counter += 1

    while len(heap) > 1:
        f1, _, left = heapq.heappop(heap)          # the two rarest nodes
        f2, _, right = heapq.heappop(heap)
        merged = {s: "0" + k for s, k in left.items()}
        merged.update({s: "1" + k for s, k in right.items()})
        heapq.heappush(heap, (f1 + f2, counter, merged))
        counter += 1

    return heap[0][2]


text = "ABRACADABRA"
frequencies = dict(Counter(text))
print(dict(sorted(frequencies.items())))
# {'A': 5, 'B': 2, 'C': 1, 'D': 1, 'R': 2}

code = huffman_codes(frequencies)
print(dict(sorted(code.items())))
# {'A': '0', 'B': '110', 'C': '100', 'D': '101', 'R': '111'}
```

The most frequent symbol, `A`, is coded with one bit; the rarest, `C` and `D`, with
three. No code is the prefix of another.

The third field placed in the heap (`counter`) makes the ordering deterministic on
ties. Without it, the code could vary from run to run on equal frequencies; because the
party decoding the compressed data must build the same tree, this would be an
unwanted ambiguity.

## Gain and Decoding

```python
import math


def encode(text: str, code: dict[str, str]) -> str:
    return "".join(code[character] for character in text)


def decode(bits: str, code: dict[str, str]) -> str:
    reverse = {v: k for k, v in code.items()}
    result: list[str] = []
    buffer = ""
    for bit in bits:
        buffer += bit
        if buffer in reverse:              # prefix-free, so the first match is certain
            result.append(reverse[buffer])
            buffer = ""
    return "".join(result)


bits = encode(text, code)
fixed_length = len(text) * math.ceil(math.log2(len(frequencies)))

print(len(bits), fixed_length)     # 23 33
print(decode(bits, code) == text)  # True
```

Five distinct symbols require three bits at fixed length: 33 bits. The Huffman code
stores the same text in 23 bits — roughly a third less.

Decoding is a direct consequence of the prefix-free property: a decision is made the
moment the accumulated bit sequence matches a code, with no backtracking required.

## Optimality

Among methods that **assign a code per symbol**, the Huffman code gives the smallest
total length. The argument rests on two observations.

**First:** In an optimal tree, the two rarest symbols can be placed at the deepest
level, as siblings. If they are not, swapping them does not increase the cost — the
same exchange argument as in the minimum-spanning-tree lesson.

**Second:** Once two symbols are merged and counted as a single symbol, the optimal
solution of the smaller problem gives the optimal solution of the original problem.

Together, the two show that the greedy choice is safe at every step. Construction cost
is $O(k \log k)$ because of the priority queue, where $k$ is the number of distinct
symbols.

## The Entropy Bound

There is a limit to how much improvement is possible. With symbol probabilities $p_i$,
the **entropy**

$$
H = -\sum_i p_i \log_2 p_i
$$

is the lower bound on the average number of bits per symbol. The Huffman code operates
close to this bound: its average length lies between $H$ and $H + 1$.

```python
n = len(text)
H = -sum((f / n) * math.log2(f / n) for f in frequencies.values())

print(round(H, 3), round(len(bits) / n, 3))     # 2.04 2.091
```

The measured average, 2.091 bits, sits just above the theoretical lower bound of 2.04
bits. The gap comes from code lengths having to be integers; a symbol cannot be given
1.5 bits.

Crossing this bound is only possible by changing the assumption — much as the lower
bound on comparison-based sorting is crossed by using the structure of keys. Methods
that code symbols in groups rather than one at a time approach the fractional-bit cost;
methods that dictionary-encode repeated pieces drop the assumption of symbol
independence and exploit repetition in the text instead. The second is directly related
to the suffix structures from the previous lesson.

## Limits and Implementation Details

**A frequency table is required.** Encoding needs two passes: frequencies are counted
first, then encoding happens. The table is also stored so the decoder can rebuild the
tree; on short text this overhead can eat up the gain.

**Adaptive variants** update the table as the stream progresses and work in a single
pass; in exchange, the encoder and decoder must follow exactly the same update rule.

**Symbol independence is assumed.** The method does not use a symbol's relationship to
the one before it. In natural language this relationship is strong; for this reason
Huffman is generally used not on its own but after a stage that eliminates repetition
first.

**It is lossless.** Decoded data is identical, bit for bit, to the original. The lossy
methods used for images and audio belong to a different family and are outside this
course.

## Summary

- Prefix-free codes decode unambiguously and correspond exactly to binary trees; code
  length is the depth of the leaf.
- The Huffman method builds the tree from the leaves to the root by merging the two
  rarest nodes; its cost is $O(k \log k)$.
- Its optimality rests on an exchange argument showing the two rarest symbols can be
  made siblings.
- Average code length lies between entropy and entropy plus one; the gap comes from bit
  counts having to be integers.
- Storing the frequency table, the assumption of symbol independence, and the two-pass
  structure are the method's main limits.

## Course Wrap-Up

The Algorithms course began with a measure and ended with application. First, the cost
of a solution was defined: operation counting, asymptotic notation, complexity classes,
the algorithm-analysis method, and the time–space trade-off. The same measure was then
used across three areas — searching and sorting, graph algorithms, text algorithms.

A handful of recurring ideas turn the course into a single system:

- **Thinking in lower bounds.** Comparison-based search $\Omega(\log n)$,
  comparison-based sorting $\Omega(n \log n)$, entropy $H$: every problem has a floor
  that cannot be crossed, and that floor is crossed only by changing the assumption.
- **Proving a greedy choice.** Dijkstra, Prim, Kruskal, and Huffman share the same
  pattern: the choice is shown safe with an exchange argument.
- **Divide and conquer.** Merge sort, quicksort, binary search, and counting inverted
  pairs all arise from the same relation.
- **The preprocessing trade-off.** Binary search, the suffix array, the KMP table, and
  hash-based methods are different forms of the same calculation: pay once, gain many
  times.

The next course, **Operating System Concepts**, takes up the layer these algorithms run
on: processes, concurrency, memory management, and file systems. The analysis tools
built here will be used directly in topics such as scheduling algorithms, page
replacement, and deadlock detection.