skip to content

Why does a Huffman code spend a full bit per symbol when one next hop carries 95% of the traffic?

level: seniorimportance: should knowfreq 50%

answer

  1. whole bits only, never a fraction
  2. one bit is the floor per symbol
  3. worst when one symbol dominates
  4. entropy near zero, code still one bit
  5. block symbols to share the rounding

basics

~20 s

Because a symbol code emits whole bits, and the shortest possible code word is one bit. A two-symbol alphabet therefore costs exactly 1 bit per symbol while the source's Shannon entropy is about 0.29 bits, wasting roughly 0.71 bits every time.

solid answer

~50 s

Huffman assigns an **integer number of bits** to each symbol, and no code word can be shorter than one bit. With two next hops at 0.95 and 0.05, the tree has one merge and both leaves sit at depth 1, so the expected length is exactly **1.0 bit per symbol** against a Shannon entropy of about **0.29 bits** — more than three times the floor. The waste is largest precisely when one symbol holds most of the mass, because that symbol *should* cost a fraction of a bit and cannot. The Huffman-side remedy is to enlarge the alphabet: code fixed-size blocks of symbols as single units, so the rounding overhead is shared. Coding pairs here drops the cost to about 0.574 bits per symbol. The overhead shrinks with block size but the alphabet grows exponentially with it.

go deeper

for a junior

Hold on to the shape of the problem: a code that emits whole bits cannot spend less than one bit on a symbol, so a source that is almost always the same value still costs a bit each time.

for a middle

Explain the integer-length constraint and compute both numbers for a skewed two-symbol source — one bit per symbol against an entropy near 0.29 bits — and say why no rearrangement of the tree helps.

for a senior

Recognise the pattern in a real payload: a field with one dominant value is where a symbol code leaves the most on the table. Propose blocking, quantify the improvement, and state the exponential table cost you are accepting.

for a principal

Decide whether the residual overhead is worth chasing at all: measure it against message size, table distribution cost and the operational weight of a bigger alphabet before trading a simple coder for a more complex one.

## Where the waste comes from A symbol code makes one indivisible decision per symbol: which bit string to emit. That string has a whole number of bits, and the shortest useful one is a single bit. Nothing in the construction can spend, say, 0.07 bits on a symbol that occurs 95% of the time — that is not a thing a symbol code can emit. So the per-symbol cost of any symbol code is bounded below by 1, no matter how predictable the source is. That bound bites hardest on skewed sources. Take a router logging which of two next hops a packet took, with shares 0.95 and 0.05: - The Huffman tree has a single merge, both leaves at depth 1, so both code words are one bit: expected length **1.000 bit per symbol**. - The Shannon entropy of the source is `0.95 x log2(1/0.95) + 0.05 x log2(1/0.05)`, which is about `0.070 + 0.216 = 0.286` bits — call it **0.29 bits per symbol**. - The code therefore spends about **3.5 times** what the source's content is worth, wasting roughly 0.71 bits on every symbol. Push the skew further and it gets worse in relative terms: as the dominant probability approaches one, the entropy approaches zero while the code's cost stays pinned at one bit. In the degenerate case of a one-symbol alphabet the source carries no information at all, and the code still cannot emit less than a bit per symbol without leaving the symbol-code model entirely. ## Where the waste does not come from It is worth being precise about what is *not* wrong here, because candidates often misdiagnose it: - **The tree is not suboptimal.** Huffman is optimal among codes that assign an integer number of bits per symbol. No rearrangement beats 1.0 bit for a two-symbol alphabet. - **The frequencies are not stale.** The code was built from exactly this distribution. - **It is not a tie-breaking artefact.** With two symbols there is only one tree shape. The gap is structural, not a defect: it is the price of the integer-length constraint. Huffman's expected length lands on the entropy **exactly when every probability is a power of one half**, because only then is every ideal code length already a whole number. Every other distribution pays some rounding, and that rounding is worst when a single symbol carries most of the mass. ## The Huffman-side remedy: enlarge the alphabet The overhead is *per coding decision*, so make each decision cover more source symbols. Treat every **pair** of consecutive next hops as one symbol of a four-symbol alphabet. Assuming independence, the pair probabilities are 0.9025, 0.0475, 0.0475 and 0.0025, and Huffman over them gives code lengths 1, 2, 3, 3: | Pair probability | Code length | Contribution | |---|---|---| | 0.9025 | 1 | 0.9025 | | 0.0475 | 2 | 0.0950 | | 0.0475 | 3 | 0.1425 | | 0.0025 | 3 | 0.0075 | That totals **1.1475 bits per pair**, which is about **0.574 bits per source symbol** — down from 1.0, and much closer to the 0.29-bit floor. The pattern generalises: coding blocks of `k` symbols spreads one rounding overhead across `k` symbols, so the per-symbol waste falls roughly in proportion to `1/k`. The cost of that remedy is what makes it a judgement call rather than a free win: - The alphabet size grows **exponentially in the block size**, so the table, the build cost and the memory grow with it. - Larger blocks mean a larger table to ship or agree, which eats into the saving on short messages. - Blocking assumes you can estimate the block probabilities well; with limited data, the estimates for rare blocks are noisy. ## What to say in an interview Diagnose it as the integer-length constraint, quantify it with the two numbers (1.0 versus 0.29 bits), name blocking as the in-family fix with its exponential table cost, and say plainly that a coder which is not restricted to whole bits per symbol is the other way out. That is the honest boundary of what a symbol code can do.

  • For which distributions does a Huffman code's expected length hit the entropy exactly?
    Exactly those where every probability is a power of one half — 1/2, 1/4, 1/8 and so on. Then each symbol's ideal length is already a whole number of bits, so the integer constraint costs nothing and the code's expected length equals the entropy. Any other distribution forces at least one symbol to a rounded length and pays for it.
  • Does blocking symbols together change what the coder can see about the source?
    Yes, and that is a second benefit. A per-symbol code is blind to correlation between neighbours; blocking pairs makes the pair itself the unit, so a source where one next hop tends to follow itself shows up as a skew in the pair frequencies and gets coded accordingly. The cost is that the alphabet, and hence the table, grows exponentially with block size.
  • Why does capping the maximum code length cost so little in practice?
    Because long code words are assigned to the rarest symbols, so their contribution to the expected length is tiny. Flattening the smallest frequencies slightly before building bounds the tree depth, which lets a decoder use fixed-width lookup tables, and typically costs a small fraction of a percent in compression.

saying these in an interview costs you the question

  • Blames the tree for being built badly
  • Thinks a better merge order would beat one bit per symbol
  • Claims the code always lands on the entropy
  • Assumes the waste shrinks as the skew grows
  • Cannot name enlarging the alphabet as the in-family fix
  • Thinks a symbol code can emit part of a bit