Zstandard ships two entropy coders in one format and routes different parts of every frame to each. RFC 8878 states the split plainly: "Huffman is used to compress literals, while FSE is used for all other symbols (Literals_Length_Code, Match_Length_Code, and offset codes) and to compress Huffman headers." That sentence encodes a sharp tradeoff. Huffman is fast but cannot charge less than one bit per symbol; FSE (Finite State Entropy) charges fractional prices but decodes through a serial dependency chain. zstd refuses to pick a winner — and the reasons why are a compact tour of entropy coding.
The 1-bit floor
An entropy coder's job is to spend -log2(p) bits on a symbol of probability p. A symbol that appears 90% of the time should cost about 0.15 bits — a number Yann Collet uses in his original FSE announcement. Huffman coding can't do that. It builds a prefix code, and a prefix codeword is a whole number of bits, at minimum one. As the FiniteStateEntropy repository puts it: "By design, Huffman can't break the '1 bit per symbol' limit."
On balanced distributions nobody notices, because rounding each symbol's cost to a whole bit loses almost nothing. On skewed ones the floor is brutal. Collet's announcement post benchmarks a proba90 test file (one symbol dominating at ~90%): FSE reaches a compression ratio of 15.21 where zlib manages 7.175 — Huffman-style coding leaves more than half the achievable compression on the table, because it keeps paying 1 bit for a symbol worth 0.15.
The classical escape is arithmetic coding, which gets arbitrarily close to the Shannon limit. Collet's post lists why it never displaced Huffman in fast codecs: it needs multiplications and divisions with strictly defined rounding, patents on implementation details discouraged adoption for years, and even on modern CPUs arithmetic decoders run slower than Huffman ones.
A single integer that carries fractional bits
The way out came from Jarek Duda's asymmetric numeral systems (ANS), whose paper title is the whole pitch: "entropy coding combining speed of Huffman coding with compression rate of arithmetic coding." Where an arithmetic coder tracks a range — two numbers — ANS tracks a single natural number as its state. FSE is Collet's table-driven variant of ANS (the "tANS" flavor), engineered so the hot loop "only requires additions, masks, and shifts."
The entire FSE decoder, from Collet's follow-up post on decoding:
outputSymbol(decodeTable[state].symbol);
int nbBits = decodeTable[state].nbBits;
state = decodeTable[state].newStateBaseline
+ getSomeBits(bitStream, nbBits);In RFC 8878 terms: the decode table has 2^Accuracy_Log entries, each holding a Symbol, a Num_Bits, and a Baseline. The decoder reads Accuracy_Log bits to get its initial state, emits that state's symbol, then reads Num_Bits more bits and adds them to Baseline to land on the next state. One quirk: the encoder writes bits forward, but the decoder reads the stream in reverse — the two visit the state sequence in opposite orders.
No tree walking, no range maintenance, no divisions. The magic is entirely in how the table is built.
Where the fractional bit lives
Collet's decoding post works the example that makes tANS click. The standalone library defaults to a 12-bit state — 4096 table slots. A symbol with normalized frequency 4 out of 4096 appears once per 1024 symbols, so it should cost 10 bits, and it does: each of its 4 states reads exactly 10 bits. Huffman could do that too, because 1/1024 is a power of two.
Now give the symbol frequency 5. Its ideal cost is -log2(5/4096) = 9.68 bits — not a whole number, and exactly where Huffman gives up. FSE assigns the symbol 5 of the 4096 table slots and partitions the full state space among those 5 occurrences into power-of-two sub-ranges: two ranges of 512 states (9 bits each) and three of 1024 states (10 bits each), summing to 4096. When the decoder lands on one of this symbol's states, it reads 9 or 10 bits depending on which sub-range that state forwards into.
Price it naively, assuming every state is equally likely:
(2 × 9 × 512 + 3 × 10 × 1024) / 4096 = 9.75 bits average — against the 9.68-bit ideal.
The real figure is better than 9.75, because states are not equally likely: low states occur more often than high ones, and the low states are the ones reached after reading fewer bits. Duda's analysis shows the construction converges toward the Shannon limit.
The intuition worth keeping: the state is the fractional bit buffer. After emitting a symbol worth 9.68 bits, the decoder sometimes reads 9 bits and sometimes 10 — and the leftover 0.32 or 0.68 of a bit isn't discarded, it's stored in which state you ended up in, to be spent on the next symbol. Huffman falls out as the degenerate case: when every probability is an exact power of two, every state of a given symbol reads the same nbBits, and the state carries no information between symbols.
Why zstd still ships Huffman
If FSE strictly dominated, zstd would be FSE-only. The benchmark table in the FiniteStateEntropy repository (Core i7-5600U, GCC 4.8.4, 32 KB blocks) shows why it isn't:
| File | Codec | Ratio | Compression | Decompression |
|---|---|---|---|---|
| Proba80 | Huff0 | 6.38 | 600 MB/s | 1350 MB/s |
| Proba80 | FSE | 8.84 | 325 MB/s | 440 MB/s |
| Proba02 | Huff0 | 1.13 | 525 MB/s | 555 MB/s |
| Proba02 | FSE | 1.13 | 325 MB/s | 445 MB/s |
Two regimes. On the heavily skewed Proba80, FSE's ratio is 39% better — the 1-bit floor is costing Huffman dearly. On the near-uniform Proba02, the ratios are identical to two decimal places, and Huff0 decompresses Proba80 at three times FSE's speed. The README credits Huff0's speed to exploiting out-of-order execution across multiple ALUs; FSE's loop, by contrast, is a serial chain — you cannot compute the next table index until you've read the bits the current entry told you to read.
zstd's routing follows the table. Literals — the bytes LZ matching couldn't eliminate — are a 256-symbol alphabet that is rarely extreme in skew, so the whole-bit penalty is small and the 3x-faster decoder wins; the spec even caps Huffman code length at 11 bits (Number_of_Bits = Max_Number_of_Bits + 1 - Weight), keeping the decode tables small. Sequence codes — literal lengths, match lengths, offsets — are tiny alphabets where individual codes can dominate the distribution, exactly where the floor binds, so they get FSE. And the tables stay minuscule: the predefined modes use an accuracy log of 6 (64 states) for the length codes and 5 (32 states) for offsets, with spec maximums of 9, 9, and 8.
The best detail is recursive: the Huffman table itself travels compressed. When the weights header byte is below 128, the Huffman code's weight list is FSE-compressed (maximum accuracy log 6); otherwise the weights are stored raw as 4-bit fields. The fast coder's configuration rides in on the precise one.
The tradeoff in one line
The 1-bit floor binds exactly when a symbol's ideal cost drops below one bit — probability above 50% — and gets worse the further you push. Below that, Huffman sits within rounding error of Shannon and decodes in parallel-friendly whole bits. FSE buys back the fractional bits with a table lookup per symbol and a serial state chain. zstd's answer to "which coder is better" is the only honest one: it depends on the alphabet, so route each alphabet to the coder that fits it.