skip to content

What does a canonical Huffman code let an encoder ship to the decoder instead of the tree itself?

level: middleimportance: should knowfreq 42%

answer

  1. the bits alone are not self-describing
  2. many trees, one length vector
  3. ship lengths, not shape
  4. increment, then shift on length change
  5. first-code-per-length drives fast decode

basics

~20 s

Only one code length per symbol, in an agreed symbol order. A canonical code assigns the actual bit patterns from the lengths alone by a fixed rule, so both sides derive identical code words without any tree structure crossing the wire.

solid answer

~50 s

A decoder cannot infer the code from the compressed bits — the same bits mean different next hops under different tables — so the table has to reach it somehow. A **canonical Huffman code** exploits the fact that many trees share one length vector: it fixes a rule that turns lengths into code words, so the only thing that must travel is **one length per symbol** in an agreed order. The rule is: walk symbols in order of increasing length (ties broken by symbol order), start at code `0`, increment after each symbol, and shift left by the difference whenever the length increases. Lengths 2, 2, 2, 3, 3 give `00`, `01`, `10`, `110`, `111`. That is far cheaper than serialising tree shape, it makes the table order-independent of how ties were broken during the merge, and it enables table-driven decoding from a small array of first-codes per length.

code

pseudocode · 10 lines
pseudocode
sort symbols by (length[s], symbol_order[s]), skipping length == 0

code = 0
previous_length = length[first symbol in sorted order]

for each symbol s in sorted order:
    code = code << (length[s] - previous_length)
    codeword[s] = code, written in length[s] bits
    code = code + 1
    previous_length = length[s]

go deeper

for a junior

Remember that compressed bits are meaningless without the code table, and that the table either ships with the data or is agreed in advance by both sides.

for a middle

Explain that code words are free to change as long as the lengths stay fixed, and that a canonical rule exploits this so only a length per symbol has to travel. Be able to turn lengths 2, 2, 2, 3, 3 into concrete code words.

for a senior

Reason about the header cost against the payload saving, and know the silent failure: a wrong table usually parses and emits wrong symbols, so integrity belongs on the decoded payload and the table needs a version.

for a principal

Treat the table as a contract between independently deployed encoders and decoders: where it lives, how it is versioned, and who can change it decides whether a distribution change is a config rollout or a coordinated release.

## Why the table has to travel A Huffman-coded stream is a bare sequence of bits. The same bits decode to different symbols under different code tables, and a table built from one frequency distribution is meaningless against another. There is nothing self-describing in the stream: the decoder needs the mapping. Three arrangements cover almost every real use: 1. **A table agreed in advance**, built once from representative traffic and compiled into both sides. Nothing ships per message; the cost is that both sides must be changed together when the table changes. 2. **A table shipped in the message header**, built from that message's own frequencies. Self-contained and always matched to the data, but the header's bits come out of the saving. 3. **A table shipped per batch**, amortising one header over many messages that share a distribution. Whatever the arrangement, the representation of the table matters, because in case 2 and 3 you pay for it on every message or batch. ## What canonical means Many different tree shapes produce the **same multiset of code lengths**, and any assignment of code words consistent with those lengths that keeps the code prefix-free is just as good — the expected length depends only on the lengths. A **canonical Huffman code** takes that freedom away deliberately: it fixes one rule for turning a length vector into code words, so that encoder and decoder, given the same lengths, always produce the same bit patterns. The rule: - Sort symbols by `(length, symbol order)`. - Start with `code = 0` and `previous_length` equal to the first (shortest) length. - For each symbol: shift `code` left by `length - previous_length`, assign it, then add one and set `previous_length = length`. Because the shift happens *before* the assignment and the increment *after*, codes of a given length are consecutive integers, and moving to a longer length extends the previous value with zeros. That is what keeps the result prefix-free. ## A worked assignment Five next-hop identifiers with lengths 2, 2, 2, 3, 3: | Symbol | Length | Canonical code | |---|---|---| | N1 | 2 | `00` | | N2 | 2 | `01` | | N3 | 2 | `10` | | N4 | 3 | `110` | | N5 | 3 | `111` | No code word here is a prefix of another, and the expected length over shares 0.4/0.2/0.2/0.1/0.1 is the same 2.2 bits the merge tree gave. Nothing about the tree's shape had to be transmitted: **five small integers** carry the whole code. ## What this buys - **A much smaller table.** Serialising a tree means shipping structure — which node has which children — while a canonical table ships one small integer per symbol, and those integers are themselves highly compressible. - **Tie-break independence.** Two implementations that broke merge ties differently may build different trees, but if both are handed the same length vector they produce byte-identical codes. - **Fast decoding.** From the lengths you can precompute, per length, the first code word of that length and the index of the first symbol with it. Decoding then reads bits one at a time and compares against the first-code of the current length, turning a tree walk into arithmetic on a small array. - **Compact absent symbols.** A symbol that never occurs is given length zero and simply skipped by the assignment rule. ## The failure mode to know If the decoder's table disagrees with the encoder's — a stale compiled-in table, a truncated header, symbols enumerated in a different order — the stream usually still **parses**. Prefix-free code words consume the bit stream happily and emit wrong symbols. There is no checksum in the code itself and no guarantee that it resynchronises, so corruption can be silent and open-ended. Systems that care therefore version the table explicitly and put an integrity check over the decoded payload rather than trusting the code structure to notice.

  • Why is a canonical table smaller than a serialised tree?
    A tree has to encode structure — for each internal node, what its children are — which costs bits proportional to the number of nodes and says nothing a decoder can predict. A canonical table needs only the depth of each leaf, one small bounded integer per symbol, in an order both sides already agree on. Those integers repeat heavily across symbols and compress further.
  • What does a decoder do with lengths to decode quickly?
    It precomputes, for each code length, the first canonical code word of that length and the index of the first symbol having it. Decoding accumulates bits into a value and, at each length, checks whether the value is below the next length's first code; if so, the symbol index is a subtraction plus an offset. That replaces a per-bit tree walk with a short loop over lengths.
  • Can a symbol with frequency zero be represented?
    Yes, by giving it length zero, which the assignment rule skips entirely so it receives no code word. That keeps the length vector a fixed-size array over the whole alphabet, which is simpler to transmit than a list of present symbols, and it means an encoder that later meets that symbol must rebuild and reship the table.

saying these in an interview costs you the question

  • Thinks the decoder can infer the table from the compressed bits
  • Believes the tree structure must be serialised
  • Says canonical codes compress better than ordinary ones
  • Assumes a mismatched table makes decoding fail loudly
  • Cannot say what the agreed symbol order is for