Huffman Coding in Python: How Compression Actually Compresses

A plain text file spends eight bits on the letter e and eight bits on the letter q, even though English uses e about a hundred times more often. That is the waste Huffman coding removes. It hands every symbol a bit pattern whose length depends on how often the symbol appears — one bit for the workhorses, ten or twelve for the oddities — and the result is provably the best you can do with whole numbers of bits.

"Provably the best" is a strong claim and Huffman earns it. Among all codes that give each symbol a whole number of bits and can be decoded without separators between symbols, none produces a shorter output than Huffman's on the same frequency table. The construction that achieves this is a loop with two heap pops and one heap push in it.

It is also still running on your machine right now. Huffman codes are the entropy stage of DEFLATE, so they are inside nearly every .zip archive, nearly every Content-Encoding: gzip response and nearly every PNG image — nearly, because DEFLATE can also emit uncompressed blocks and ZIP permits other methods entirely. They are inside baseline JPEG and inside MP3 too. This post builds a working coder on abracadabra, decodes a bit string by hand, measures the real compression ratio including the table you have to ship alongside the bits, and is honest about where modern codecs have moved past it.

The idea

Why variable-length codes need a rule

Start with the boring option. abracadabra uses five distinct characters, so you could number them 0 to 4 and spend three bits on each: 11 characters, 33 bits. Decoding is trivial — chop the stream into three-bit pieces.

Now try to do better. a appears five times out of eleven, so give it a short code and the rare c and d long ones. The moment code lengths differ, decoding stops being obvious. Assign E the code 0, T the code 1 and A the code 01, and the received bits 01 mean either E then T, or a single A. No amount of cleverness in the decoder fixes that; the information is genuinely not there.

The rule that saves you is prefix-free: no symbol's code may be a prefix of another symbol's code. 01 is broken because 0 is a prefix of it. With that rule, decoding becomes a single left-to-right scan with no lookahead. Read bits until what you hold matches some code, and that match is forced — a longer code that started the same way would have your bits as a prefix, which the rule forbids.

Codes are paths down a binary tree

There is a neat way to guarantee prefix-freeness by construction rather than by checking. Build a binary tree. Label every left edge 0 and every right edge 1. Put the symbols only at the leaves. A symbol's code is the sequence of edge labels from the root down to its leaf.

Prefix-freeness now comes for free. Code X is a prefix of code Y exactly when the path to X is the start of the path to Y — which would mean X sits on the way to Y, and therefore is not a leaf. Symbols live at leaves, so it cannot happen.

Decoding is now a walk. Put a finger on the root. For each bit, step left on 0 and right on 1. When the finger lands on a leaf, emit that symbol and jump back to the root. Here is the bit string 0101101110 decoded against the tree above, one line per symbol:

bits     path from the root                       lands on   emit
0        left                                     leaf       E
1 0      right, left                              leaf       T
1 1 0    right, right, left                       leaf       A
1 1 1    right, right, right                      leaf       O
0        left                                     leaf       E

Ten bits in, ETAOE out. The decoder never looked ahead, never backtracked and never needed a separator or a length field. That is the entire payoff of the prefix-free property.

Which tree, though?

Any tree with the symbols at the leaves gives a valid code. The one you want is the cheapest. The total number of bits for a message is

cost(tree) = sum over symbols of (frequency of symbol) x (depth of its leaf)

because a symbol at depth d costs d bits every time it appears. Minimising that means pushing frequent symbols towards the root and rare ones towards the bottom.

Huffman's rule for building that tree is one sentence: take the two lowest-weight nodes, join them under a new parent whose weight is their sum, and put the parent back in the pool. Repeat until one node is left. Start with one leaf node per symbol, weighted by its frequency. Each merge removes two nodes and adds one, so n symbols take exactly n - 1 merges.

The reason this greedy rule is correct is easier to see with a second way of writing the same cost. Every merge you perform adds one edge above everything already inside the two nodes you merged, so it adds one bit to every occurrence of every symbol underneath. That means each merged node's weight gets billed exactly once:

cost(tree) = sum of the weights of all the internal nodes

Cheap merges early, expensive merges late — and that is what "always merge the two lightest" does.

Watching it work

Take the string abracadabra. Count the characters first:

Eleven characters, five distinct symbols. Fixed-width would cost 33 bits and ASCII costs 88.

Two of those frequencies tie at 2 and two tie at 1, so before any merging you have to decide what "the two lowest" means when several nodes are equal. Pick a tie-break and stick to it, or two runs of your own code can produce two different (equally good) trees. The rule used here: nodes enter the pool in alphabetical order and carry a strictly increasing counter, and ties are broken by the lower counter. So the initial pool, in the order it will be drained, is c=1, d=1, b=2, r=2, a=5.

Four merges, since there are five symbols:

Merge 1. The two lightest are c=1 and d=1. Join them under a node of weight 2. The pool is now b=2, r=2, (cd)=2, a=5 — the new node sorts last among the twos because it received the newest counter.

Merge 2. The two lightest are b=2 and r=2. Join them under a node of weight 4. Pool: (cd)=2, (br)=4, a=5.

Merge 3. The two lightest are (cd)=2 and (br)=4. Join them under a node of weight 6. Pool: a=5, (cdbr)=6.

Merge 4. Only two nodes are left, so they merge into the root, weight 11 — which is the length of the string, as it must be, because every character is counted exactly once somewhere below the root.

Now read the tree. Left edges are 0, right edges are 1:

Total: 23 bits, against 33 for fixed width and 88 for ASCII. Check it against the other cost formula — the internal nodes weigh 2, 4, 6 and 11, and 2 + 4 + 6 + 11 = 23. The two ways of counting agree, as they must.

Encoding abracadabra is now a table lookup per character:

a   b    r    a   c    a   d    a   b    r    a
0   110  111  0   100  0   101  0   110  111  0

which runs together as 01101110100010101101110. Feed that back into the decoding walk and you get abracadabra — the first 0 lands immediately on the a leaf, then 110 steps right, right, left to b, and so on.

Why greedy is right here

Greedy algorithms are usually wrong, so the argument matters. It has two halves.

First, there is an optimal tree in which the two rarest symbols are siblings at the deepest level. Take any optimal tree. No internal node in it has only one child, because deleting such a node would shorten a code and cut the cost. So the deepest leaf has a sibling, and that sibling must be a leaf at the same depth — anything hanging below it would be deeper still. Call those two slots p and q, and swap the rarest symbol into p and the second-rarest into q. Each swap moves a lower frequency to a greater-or-equal depth and a higher frequency to a lesser-or-equal depth, so the total cost cannot go up. The tree was optimal, so the swapped tree is optimal too, and in it the two rarest symbols are siblings at the bottom.

Second, merging them leaves a smaller version of the same problem. Replace those two siblings with a single symbol whose frequency is their sum. Any tree for the smaller alphabet turns into a tree for the original by splitting that leaf in two, and the cost goes up by exactly the merged weight either way. So an optimal tree for the smaller problem gives an optimal tree for the bigger one.

Put them together and induct on the number of symbols: the first merge is safe, and what remains is the same problem one symbol shorter. That is a textbook exchange argument, and it is what separates Huffman from the greedy rules that merely look sensible.

The code

Counting first. collections.Counter is the standard-library tool for this and there is no reason to write your own tally loop.

from __future__ import annotations

from collections import Counter

TEXT = "abracadabra"
counts = Counter(TEXT)

for symbol, weight in sorted(counts.items()):
    print(f"{symbol}  {weight}")

print(f"{len(TEXT)} characters, {len(counts)} distinct symbols")
print(f"three bits each (fixed width): {3 * len(TEXT)} bits")
print(f"eight bits each (ASCII):       {8 * len(TEXT)} bits")

a  5
b  2
c  1
d  1
r  2
11 characters, 5 distinct symbols
three bits each (fixed width): 33 bits
eight bits each (ASCII):       88 bits

Now the tree. The pool of nodes waiting to be merged needs one operation — "give me the lightest" — repeated 2(n - 1) times, which is exactly what a min-heap is for. Python's is heapq, and it works on a plain list.

import heapq
from dataclasses import dataclass
from typing import Optional


@dataclass
class Node:
    """One node of the code tree. A leaf carries a symbol; an internal node
    carries None and exists only to hold two children together."""

    symbol: Optional[str]
    weight: int
    left: Optional["Node"] = None
    right: Optional["Node"] = None

    @property
    def is_leaf(self) -> bool:
        return self.left is None and self.right is None


def build_tree(counts: dict[str, int], trace: bool = False) -> Optional[Node]:
    """Merge the two lightest nodes until one node is left, and return it.

    The heap holds `(weight, tiebreak, node)`. The tiebreak counter is not
    decoration: it fixes the order of equal weights so the output is
    reproducible, and it guarantees heapq never has to compare two Nodes.
    """
    if not counts:
        return None

    tiebreak = 0
    heap: list[tuple[int, int, Node]] = []
    for symbol, weight in sorted(counts.items()):
        heap.append((weight, tiebreak, Node(symbol, weight)))
        tiebreak += 1
    heapq.heapify(heap)

    while len(heap) > 1:
        left_weight, _, left = heapq.heappop(heap)
        right_weight, _, right = heapq.heappop(heap)
        parent = Node(None, left_weight + right_weight, left, right)
        if trace:
            print(f"merge {name(left)} + {name(right)} -> {parent.weight}"
                  f"   pool: {pool(heap, parent, tiebreak)}")
        heapq.heappush(heap, (parent.weight, tiebreak, parent))
        tiebreak += 1

    return heap[0][2]


def name(node: Node) -> str:
    """A readable label: the symbol for a leaf, its leaves for a merged node."""
    if node.is_leaf:
        return f"{node.symbol}={node.weight}"
    return f"({''.join(symbols_of(node))})={node.weight}"


def symbols_of(node: Node) -> list[str]:
    if node.is_leaf:
        return [node.symbol]
    return symbols_of(node.left) + symbols_of(node.right)


def pool(heap: list[tuple[int, int, Node]], pending: Node, tiebreak: int) -> str:
    """The nodes still waiting to be merged, in the order the heap will pop."""
    waiting = sorted(heap + [(pending.weight, tiebreak, pending)],
                     key=lambda item: item[:2])
    return "  ".join(name(item[2]) for item in waiting)


root = build_tree(dict(counts), trace=True)
print(f"root weight: {root.weight}")

merge c=1 + d=1 -> 2   pool: b=2  r=2  (cd)=2  a=5
merge b=2 + r=2 -> 4   pool: (cd)=2  (br)=4  a=5
merge (cd)=2 + (br)=4 -> 6   pool: a=5  (cdbr)=6
merge a=5 + (cdbr)=6 -> 11   pool: (acdbr)=11
root weight: 11

Four merges, matching the hand trace line for line.

Turning the tree into a lookup table is one depth-first walk that carries the path so far:

def build_codes(root: Optional[Node]) -> dict[str, str]:
    """Map each symbol to its bit string. A left edge is 0, a right edge is 1."""
    if root is None:
        return {}
    if root.is_leaf:
        # A one-symbol alphabet has no edges at all, so the walk below would
        # hand it the empty code and nothing could ever be decoded.
        return {root.symbol: "0"}

    codes: dict[str, str] = {}

    def walk(node: Node, prefix: str) -> None:
        if node.is_leaf:
            codes[node.symbol] = prefix
            return
        walk(node.left, prefix + "0")
        walk(node.right, prefix + "1")

    walk(root, "")
    return codes


codes = build_codes(root)
total_bits = 0
for symbol, code in sorted(codes.items(), key=lambda pair: (len(pair[1]), pair[0])):
    cost = len(code) * counts[symbol]
    total_bits += cost
    print(f"{symbol}  {code:<4} x{counts[symbol]}  = {cost:>2} bits")
print(f"total: {total_bits} bits")

a  0    x5  =  5 bits
b  110  x2  =  6 bits
c  100  x1  =  3 bits
d  101  x1  =  3 bits
r  111  x2  =  6 bits
total: 23 bits

Encoding is a join over table lookups. Decoding is the finger-on-the-tree walk, written as a loop:

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


def decode(bits: str, root: Optional[Node]) -> str:
    """Take one edge per bit. Landing on a leaf emits a symbol and restarts."""
    if root is None or not bits:
        return ""
    if root.is_leaf:
        return root.symbol * len(bits)

    out: list[str] = []
    node = root
    for bit in bits:
        node = node.left if bit == "0" else node.right
        if node.is_leaf:
            out.append(node.symbol)
            node = root

    if node is not root:
        raise ValueError("bit string ran out part-way down the tree")
    return "".join(out)


bits = encode(TEXT, codes)
print(bits)
print(f"{len(bits)} bits, against {8 * len(TEXT)} bits of ASCII")
print(decode(bits, root))
print(decode(bits, root) == TEXT)

01101110100010101101110
23 bits, against 88 bits of ASCII
abracadabra
True

How the code maps to the idea

The heap tuple is (weight, tiebreak, node) and every part earns its place. weight is the key the algorithm cares about. tiebreak increments on every push, so no two tuples are ever equal in their first two fields — which makes the output reproducible across runs and, less obviously, stops Python from ever reaching the third element during a comparison. Drop it and the first frequency tie crashes with a TypeError, because Node has no ordering.

heapq.heapify seeds the heap in O(n), not O(n log n), which is why the leaves are appended to a plain list first rather than pushed one at a time. It does not change the overall bound, but it is free.

The loop condition is len(heap) > 1, not a fixed range. Each pass pops two and pushes one, so the heap shrinks by exactly one and ends holding the root. It also handles a single-symbol alphabet for nothing: the body never runs and the lone leaf is returned.

build_codes carries the path in an argument, not a shared list. prefix + "0" gives each branch its own string, so there is nothing to undo on the way back up — a shared list you append to and forget to pop is the classic way to get this function subtly wrong. The single-symbol case still needs its own line, though: a tree of one leaf and no edges would hand aaaa the empty code and encode it to zero bits, so it gets the one-bit code 0 instead.

decode ends by checking that the finger came back to the root. A bit string that stops half-way down a branch is truncated or corrupt, and saying so beats silently dropping the last symbol.

The header you cannot skip

Here is the part that tutorials tend to leave out. The 23 bits above are meaningless on their own. The decoder needs the same tree the encoder used, and it has no way to derive it — the frequencies came from the original message, which is precisely what the decoder does not have. So a real Huffman file is header plus payload, and the header is not free.

You have two reasonable ways to write one. Storing raw frequencies means a symbol plus a count per entry, and the count needs four bytes to hold a large file's tally — five bytes an entry. Storing code lengths is much cheaper: given only "a is 1 bit, b is 3 bits, c is 3 bits, ..." you can rebuild a code with exactly those lengths by handing out bit patterns in a fixed order — shortest length first, symbols in order within a length. That is canonical Huffman, it is what DEFLATE does, and it costs two bytes an entry rather than five. The codes come out different from the ones the tree gave you, but the lengths are the same, so the payload is the same size.

The measurement below uses that cheaper header: a two-byte count of entries, then one byte of symbol and one byte of code length each.

import math


def measure(text: str) -> tuple[int, int, int, int]:
    """Return (distinct symbols, payload bits, header bits, stored bytes).

    The header is the honest part. Storing one byte of symbol and one byte of
    code length per entry, plus a two-byte entry count, is enough for the
    decoder to rebuild an identical canonical tree.
    """
    counts = dict(Counter(text))
    table = build_codes(build_tree(counts))
    payload = sum(len(table[symbol]) * count for symbol, count in counts.items())
    header = 16 + 16 * len(counts)
    return len(counts), payload, header, math.ceil((payload + header) / 8)


SAMPLE = (
    "Compression works because real data is lumpy. The letter e turns up in "
    "English text roughly a hundred times more often than the letter q, and yet "
    "a plain text file spends exactly eight bits on each of them. Huffman coding "
    "removes that waste by giving common symbols short codes and rare symbols "
    "long ones, and it does so optimally: no other code that spends a whole "
    "number of bits per symbol can beat it on the same frequency table."
)

print(f"{'input':<22}{'syms':>5}{'payload':>9}{'header':>8}{'stored':>8}{'ratio':>8}")
for label, text in [
    ("abracadabra", TEXT),
    ("sample paragraph", SAMPLE),
    ("sample x 4", SAMPLE * 4),
    ("sample x 40", SAMPLE * 40),
]:
    distinct, payload, header, stored = measure(text)
    ratio = stored / len(text)
    print(f"{label:<22}{distinct:>5}{payload:>9}{header:>8}{stored:>8}{ratio:>7.2f}x")

input                  syms  payload  header  stored   ratio
abracadabra               5       23      96      15   1.36x
sample paragraph         32     1843     528     297   0.69x
sample x 4               32     7372     528     988   0.57x
sample x 40              32    73720     528    9281   0.54x

Read the first row carefully: abracadabra compresses from 11 bytes to 15 bytes. Huffman made it bigger. The payload did shrink, from 88 bits to 23, but 96 bits of header swamped the saving. That is arithmetic, not a bug — header cost is proportional to alphabet size while the saving is proportional to message length, so a message loses when its alphabet is wide relative to its length. The ratio decides, not the length alone: eleven characters over five symbols stores as 15 bytes, but eleven characters over two symbols carries a six-byte header and stores as 8, a real win. DEFLATE knows this and offers a "stored" block type that copies bytes verbatim, used whenever compression would expand the data.

Repeat the same distribution down the table and the header amortises away: 0.69x, then 0.57x, then 0.54x, converging on the payload-only ratio of 1843 / (432 × 8) = 0.53.

The other number worth knowing is the floor. Shannon's source coding theorem says no code that assigns bits to symbols independently can beat the entropy of the distribution, and Huffman always lands within one bit per symbol of it — usually far closer.

def entropy_bits(text: str) -> float:
    """Shannon's lower bound: no per-symbol code can beat this on this text."""
    counts = Counter(text)
    return -sum(c * math.log2(c / len(text)) for c in counts.values())


for label, text in [("abracadabra", TEXT), ("sample paragraph", SAMPLE)]:
    _, payload, _, _ = measure(text)
    floor = entropy_bits(text)
    print(f"{label:<20} huffman {payload / len(text):.3f} bits/symbol, "
          f"entropy {floor / len(text):.3f}, overhead "
          f"{(payload - floor) / len(text):.3f}")

abracadabra          huffman 2.091 bits/symbol, entropy 2.040, overhead 0.051
sample paragraph     huffman 4.266 bits/symbol, entropy 4.224, overhead 0.042

Five hundredths of a bit per symbol off the theoretical floor. The gap exists because Huffman must round every code to a whole number of bits, and it is the one thing arithmetic coding fixes.

Complexity

Let n be the number of distinct symbols and m the length of the message. Keeping those two separate is essential — for English text n is a few dozen while m can be gigabytes.

Counting frequencies: O(m). One pass, one dictionary update per character.

Building the tree: O(n log n). Seeding costs O(n log n) as written, because the code sorts the symbols before it heapifies — that sort buys the alphabetical tie-break, not the heap, and heapify itself is O(n). The loop then runs exactly n - 1 times, because each pass consumes two nodes and produces one, taking the pool from n down to 1. Each pass does two heappop calls and one heappush, and every heap operation walks one root-to-leaf path of a heap holding at most n items, which is at most log₂ n steps. So the merging is 3(n - 1) heap operations at O(log n) each — that is the n and that is the log n. For 256 byte values, n - 1 is 255 merges and log₂ 256 is 8, so the whole tree build is around 6,000 elementary steps regardless of file size.

If the frequencies arrive already sorted you can drop the heap entirely and do it in O(n) with two FIFO queues: one holding the sorted leaves, one holding the merged nodes in the order they were created, which is automatically non-decreasing. The next-lightest node is always at the front of one of the two queues. That is a real technique, not a curiosity — it is why sorting-based Huffman implementations exist.

Building the code table: O(total code length). The walk visits each of the 2n - 1 nodes once, but the strings it builds cost the sum of all code lengths. That sum is n × (average depth), and the worst case is worse than it looks: frequencies that grow like the Fibonacci sequence produce a completely lopsided tree with a leaf at depth n - 1, giving O(n²) characters of code strings. In practice depth stays small, and there is a hard ceiling — to force a code of length d you need each level to be at least as heavy as the sum of the two below it, so total frequency must grow at least as fast as the Fibonacci numbers. A message of fewer than 4.8 billion symbols can never produce a code longer than 44 bits. DEFLATE tightens that to 15 bits by construction.

Encoding: O(m + B), where B is the number of output bits. One table lookup per input character plus the cost of writing the bits.

Decoding: O(B). Exactly one tree step per bit — no searching, no backtracking. Real decoders speed this up with a lookup table that consumes several bits at once, trading memory for a shorter walk.

Space: O(n) for the tree, plus the code table, plus O(B) for the output. The tree has 2n - 1 nodes, since a binary tree with n leaves and no one-child nodes has n - 1 internal nodes. The code table is the part that is easy to under-count: it holds every code as a string, so it costs the same sum of code lengths that building it cost — O(n²) characters on the Fibonacci worst case above, not O(n). build_codes is also recursive, so it holds one stack frame per level, up to n - 1 of them, which is why a deep enough tree hits Python's recursion limit rather than merely running slowly.

The n log n here is cheap in absolute terms because n is bounded by your alphabet, not your data. Compressing a 1 GB file with a byte alphabet still builds the tree in 255 merges. The linear O(m) passes over the data are what actually dominate the clock.

When to use it, and when not to

Use it when you control a format and the symbol frequencies are genuinely skewed. Huffman decoding is fast, branch-light and easy to make correct, which is why it survives inside formats that need to decode at video frame rates.

Use it as the last stage of a pipeline, not as the whole pipeline. This is the important limitation. Huffman models only how often each symbol appears; it is blind to order. A file that is ab repeated a million times has two symbols at 50% each, so Huffman spends one bit on each and saves nothing over the fixed-width baseline — even though a human can describe that file in one sentence. Repetition is caught by a dictionary method like LZ77, which replaces repeats with back-references. DEFLATE is exactly that pairing: LZ77 first, Huffman second on whatever skew is left.

Do not reach for it when a general-purpose compressor will do. If you just want a file to be smaller, use zlib, gzip or lzma from the standard library — C implementations of complete formats that will beat a hand-rolled symbol coder on essentially any real input.

Do not use it on short messages. As the table above shows, an eleven-byte input with five distinct symbols comes back as fifteen bytes: the payload fell from 88 bits to 23, saving eight bytes, and the twelve-byte header more than swallowed them. If you must compress small records, share one pre-agreed table across all of them so the header is paid once — which is what HTTP/2's HPACK does with its static Huffman table.

Do not use it when you need the last few percent. A symbol with probability 0.9 deserves 0.15 bits; Huffman must spend a whole one. Arithmetic coding, range coding and the newer asymmetric numeral systems all encode at fractional bit cost and close that gap.

Where it shows up in the real world

DEFLATE (RFC 1951) is the big one, and it is everywhere: .zip archives, gzip, the zlib library, PNG's image data, and HTTP responses sent with Content-Encoding: gzip. Each DEFLATE block runs LZ77 and then Huffman-codes the resulting literals, match lengths and distances. A block either uses a fixed table baked into the spec or carries its own dynamic one — and that dynamic table is stored as canonical code lengths which are themselves Huffman-coded, a second layer of the same trick.

Baseline JPEG Huffman-codes the quantised DCT coefficients, with separate tables for the DC and AC coefficients of the luminance and chrominance channels. JPEG also defines an arithmetic-coding mode that compresses a few percent better, but patent worries in the 1990s meant almost nothing implemented it, and baseline Huffman became the version everyone actually ships.

MP3 (MPEG-1 Audio Layer III) picks from a set of predefined Huffman tables to code the quantised frequency-domain values in each granule. Brotli, the algorithm behind Content-Encoding: br, uses Huffman codes alongside a large built-in dictionary and context modelling.

Zstandard uses Huffman for literals but switches to Finite State Entropy, a tANS coder, for the sequence data — a deliberate split, because tANS handles skewed distributions at fractional bit cost while Huffman decodes literals faster.

Be accurate about the trend, though. The highest-compression modern codecs have largely moved past Huffman for their main entropy stage: H.264 and H.265 use CABAC, a context-adaptive binary arithmetic coder, and AV1 uses a multi-symbol arithmetic coder. Huffman persists where decode speed and simplicity matter more than the last few percent — which is still an enormous amount of the world's data.

Common mistakes

Pushing bare nodes into the heap. Without a tie-break value, the first frequency tie makes heapq compare two Node objects:

broken_heap = [(1, Node("c", 1))]
try:
    heapq.heappush(broken_heap, (1, Node("d", 1)))
except TypeError as error:
    print(f"TypeError: {error}")

TypeError: '<' not supported between instances of 'Node' and 'Node'

The fix is the counter in the middle of the tuple. @dataclass(order=True) looks like the shortcut and is not one: it compares fields in declaration order, so the first field it reaches is symbol — a string on a leaf, None on an internal node. Leaves and merged nodes tie all the time, and the moment they do you swap one crash for another:

@dataclass(order=True)
class OrderedNode:
    symbol: Optional[str]
    weight: int
    left: Optional["OrderedNode"] = None
    right: Optional["OrderedNode"] = None


leaf_b = OrderedNode("b", 2)
merged_cd = OrderedNode(None, 2, OrderedNode("c", 1), OrderedNode("d", 1))
try:
    heapq.heappush([(2, leaf_b)], (2, merged_cd))
except TypeError as error:
    print(f"TypeError: {error}")

TypeError: '<' not supported between instances of 'NoneType' and 'str'

That is the pool after merge 1 of abracadabra, where (cd)=2 meets b=2 — ordered nodes do not survive even the worked example. The counter sidesteps the question entirely: two tuples never tie on their first two fields, so the Node is never compared.

Forgetting to store the table. An encoder that returns only the bit string has produced something nobody can decode, including itself after a restart. Ship the header or agree the table in advance; there is no third option.

Non-deterministic tie-breaking. Iterating a dictionary you built in arbitrary order, or breaking ties by object identity, gives you a different-but-equally-optimal tree each run. Every such tree is fine on its own, but if any part of your system rebuilds the tree separately it will disagree with the encoder, and the output will decode to garbage.

Putting a symbol on an internal node. It is tempting when an alphabet feels small. It destroys the prefix-free property and makes decoding ambiguous — the whole reason for the tree.

Treating a bit string as bytes. 23 bits is not a whole number of bytes. You must pad the last byte and store how many padding bits you added, or the decoder will walk a few extra edges at the end and emit a phantom symbol. Do not lean on the if node is not root check in decode for this: it only fires when the padding happens to strand the walk part-way down a branch. Pad abracadabra's 23 bits with one 0 and the extra step lands cleanly on the a leaf, so the check passes and you get abracadabraa back with no complaint at all.

Compressing already-compressed data. Running Huffman over a JPEG or a ZIP gives you a nearly uniform byte distribution, near-maximal entropy, and an output slightly larger than the input thanks to the header.

Practice

1. Add byte packing: convert the bit string into a bytes object with the padding length recorded, and confirm the round trip still returns the original text.
2. Write a serialise_header and parse_header pair that stores the code lengths, then rebuild the code table from lengths alone using canonical ordering — shortest length first, alphabetical within a length.
3. Find the break-even point: for the sample paragraph's distribution, how many characters must a message have before the compressed form is smaller than the original?
4. Replace the recursive build_codes walk with an explicit stack, so it cannot hit Python's recursion limit on a pathologically deep tree.
5. Build the Fibonacci worst case — frequencies 1, 1, 2, 3, 5, 8, 13, ... for 20 symbols — and check that the longest code really is 19 bits.

Summary

Huffman coding is the clearest example in the whole greedy family of a local rule that provably reaches a global optimum, and the exchange argument that proves it is short enough to hold in your head. Build a min-heap of leaves, merge the two lightest n - 1 times, read the codes off the tree. Then remember the two things the theory does not tell you: the header has to travel with the bits, and symbol frequencies alone cannot see repetition, which is why every serious format wraps Huffman around something else.

Keep reading

• Heaps and Priority Queues — the structure doing all the work in the merge loop, built from scratch.
• Greedy Algorithms — the family Huffman belongs to, and how to prove a greedy rule before trusting it.
• Tries (Prefix Trees) — the other tree where the path spells the answer, used for autocomplete instead of compression.
• The Coin Change Problem — a greedy rule that looks just as reasonable and is wrong, with the DP that fixes it.
• Big O Notation — the counting arguments behind every bound quoted above.