Huffman Coding

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.

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

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$.

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.