Entropy Coding Explained: Huffman vs Arithmetic vs ANS

TL;DR >- Entropy coding is the final, lossless stage of a codec: it packs already-quantized symbols into the fewest bits their probabilities allow.- Huffman is fast but spends whole bits per symbol, so it loses efficiency whenever probabilities are not powers of one-half.- Arithmetic coding reaches the entropy limit but needs a per-symbol multiply and renormalize, which is slow (Duda, arXiv:1311.2540, 2013).- Asymmetric numeral systems (ANS) decode about 50% faster than Huffman on a 256-symbol alphabet while matching arithmetic coding's ratio, using a single natural-number state (Duda, arXiv:1311.2540, 2013).- That combination is why Zstandard (2016) and JPEG XL both replaced arithmetic coding with ANS variants (Meta Engineering, 2016).

Most explainers treat entropy coding as a footnote to the "interesting" parts of a codec, the transforms and the prediction. That is backwards. Entropy coding is where the actual bits get written, and a decade-old idea has quietly rewritten this stage across the whole industry without most engineers noticing the swap.

Between roughly 2015 and today, Zstandard, Apple's LZFSE, and JPEG XL all shipped a family of coders that did not exist in a practical form before 2009. This post explains what entropy coding does, why Huffman and arithmetic coding each fall short, and the triple-sourced reason ANS displaced both. For the broader arc, see our complete guide to image compression. Here we settle the final stage.

What entropy coding actually does

Entropy coding is the lossless back end that converts a stream of symbols into the shortest bitstream their statistics permit. It runs after the lossy steps, quantization, prediction, transform, are done. By that point the encoder has decided what to store; entropy coding decides how compactly to write it. Nothing here is thrown away.

The target it chases is Shannon entropy: the theoretical minimum average bits per symbol given the symbols' probabilities. A symbol that appears 90% of the time carries little information and deserves a fraction of a bit; a rare symbol deserves many. Every entropy coder is an approximation strategy for that ideal, and they differ in how close they get and how fast they run.

This is why entropy coding sits inside almost every format you touch. JPEG, PNG, Zstandard, gzip, H.264, and JPEG XL all end in an entropy stage, even though their earlier stages look nothing alike. The transform decides which numbers to keep. The entropy coder decides the byte count.

Citation capsule: Entropy coding is a codec's lossless final stage, packing quantized symbols toward the Shannon minimum. It runs after the lossy transform and prediction steps. Zstandard, gzip, JPEG, and JPEG XL all end in an entropy coder, differing only in which algorithm, Huffman, arithmetic, or ANS, writes the bits (Meta Engineering, 2016).

Why is Huffman coding not good enough?

Huffman is fast and simple, but it assigns a whole number of bits to every symbol, so it can only hit the entropy limit when every probability is exactly a power of one-half. Real image and text data almost never cooperate. When a symbol "wants" 2.4 bits, Huffman must round to 3, and that rounding waste accumulates across millions of symbols.

Consider a symbol that occurs 90% of the time. Its ideal cost is about 0.15 bits. Huffman cannot spend less than one full bit on it, so it overspends by roughly a factor of six on the most common symbol in the stream. On skewed distributions, which describe most quantized DCT coefficients, that gap is exactly where bytes leak.

Huffman survives anyway because it is genuinely quick and its tables are trivial to build, which is why baseline JPEG and gzip both use it. But its ceiling is structural. No amount of engineering removes the whole-bit rounding, because that rounding is the algorithm. To beat it you need a coder that can spend fractional bits per symbol.

Why is arithmetic coding slow?

Arithmetic coding solves Huffman's rounding by encoding an entire message as a single fractional number, so it can spend 0.15 bits on a symbol when the math calls for it. That reaches the entropy limit closely. The cost is speed: classic arithmetic coding needs a multiply and a renormalization step for every symbol, which is expensive in a tight decode loop (Duda, arXiv:1311.2540, 2013).

The technique is real and it works. JPEG's own standard, ITU-T T.81, defines two entropy coders, Huffman and an arithmetic QM-coder, and the arithmetic option produces roughly 5 to 10% smaller files (an approximate figure) (ITU-T T.81). JPEG 2000 leans on an MQ arithmetic coder inside its EBCOT engine, coding each bit-plane in three passes (ScienceDirect). H.264's CABAC delivers about 9 to 14% average bitrate savings over the simpler CAVLC at roughly 1.5x decode complexity (Marpe, Schwarz, Wiegand, IEEE TCSVT, 2003).

Notice the pattern. Every arithmetic deployment buys ratio and pays complexity. That trade was acceptable for professional video and JPEG 2000's niche, but for high-throughput general compression the per-symbol arithmetic was a real bottleneck. That bottleneck is the opening ANS walked through.

Family positions are illustrative; Zstd decodes the Silesia corpus near 550 MB/s versus zlib near 270 MB/s (Szorc, Meta, 2017).

Why arithmetic coding was skipped in baseline JPEG

Baseline JPEG uses Huffman even though the same standard defines a better arithmetic coder, and the reason is patents, not engineering. ITU-T T.81 specifies both a Huffman and an arithmetic (QM-coder) path, and the arithmetic option compresses roughly 5 to 10% smaller, but it was historically avoided because the QM-coder was patent-encumbered (ITU-T T.81).

This is one of the most consequential licensing decisions in media history. Baseline JPEG became the universal image format precisely because its Huffman path was unencumbered and every decoder could implement it freely. The arithmetic path sat in the same spec, offered free bytes, and almost nobody shipped it, because the surrounding patents made interoperability risky. Billions of JPEGs are 5 to 10% larger than they had to be, permanently, for legal reasons.

The lesson carried forward. When ANS arrived, its adoption story was shaped as much by its open, published origins as by its speed. Codec designers had learned that a compression method's legal status determines whether it can become universal, not just its ratio.

What is ANS, and how does the "single integer state" work?

ANS is an entropy coder that stores the entire compressed state as one natural number and updates it with cheap operations, reaching arithmetic-coding ratios at Huffman-like speed. Jarek Duda introduced it in 2009 and gave it a practical form in 2013, proving it is optimal for arbitrary symbol distributions (Duda, arXiv:0902.0271, 2009; Duda, arXiv:1311.2540, 2013).

Here is the mental model. Imagine the whole message so far compressed into a single large integer, call it the state. To encode the next symbol, you grow the state by an amount that depends on how probable that symbol is: a common symbol grows it a little, a rare symbol grows it a lot. Because the growth is proportional to information content, the final integer's size, in bits, lands near the Shannon minimum. Decoding runs the process in reverse: from the current integer you can read off the last symbol and shrink the state back. One number carries everything, and the updates are additions, table lookups, and bit shifts rather than per-symbol multiplies.

That is the whole trick. Arithmetic coding tracks a shrinking interval with two bounds and a multiply. ANS tracks a single growing integer with a table. Finite State Entropy, the tabled ANS in Zstandard, "provides the same performance as an arithmetic coder, but only requires additions, masks, and shifts" (Collet, Finite State Entropy, 2013). Same ratio, far cheaper arithmetic.

Citation capsule: ANS compresses an entire message into one natural-number state, growing it per symbol in proportion to information content so the final integer's bit length nears the Shannon limit. Its updates are additions, masks, and shifts rather than the per-symbol multiplies arithmetic coding needs (Duda, arXiv:1311.2540, 2013; Collet, 2013).

Why did ANS win? The triple-sourced answer

ANS won because it collapsed a decades-old trade-off: it hits near-arithmetic ratios at near-Huffman speed, so codec designers no longer had to choose. Three independent sources make the case. Duda's 2013 paper measured roughly 50% faster decoding than Huffman on a 256-symbol alphabet with compression close to arithmetic coding (Duda, arXiv:1311.2540, 2013). Collet showed the tabled variant matches arithmetic coding using only adds, masks, and shifts (Collet, 2013). And the adoption record confirms it in production: ANS now ships in Facebook's Zstandard, Apple's LZFSE, Google's JPEG XL, Draco, and Chrome, plus Dropbox and Microsoft (PMC8946946).

The production numbers back the theory. Zstandard, which pairs Huffman for literals with tANS for sequences, runs about 3 to 5x faster than zlib at equal ratio, or about 10 to 15% smaller at equal speed, decompressing the Silesia corpus near 550 MB/s versus zlib's roughly 270 MB/s, and at its maximum level 22 lands only about 2.3% larger than LZMA-9 (Szorc, Meta, 2017). Those are the numbers that end debates.

The overlooked part of the ANS story is that it did not win by being the best compressor. Arithmetic coding was already near-optimal on ratio. ANS won because it removed the reason to accept worse ratios for speed. For thirty years, general-purpose compression chose Huffman and swallowed the rounding waste because arithmetic was too slow. ANS did not raise the ceiling; it moved the fast option up to the ceiling, which is a more disruptive thing to do.

rANS, tANS, and range coding: getting the names right

The naming here is a common source of confusion, so pin it down: rANS and tANS are two variants of the same ANS family, while range coding is a separate, older arithmetic-coding technique that is not ANS at all. Mixing these up is the most frequent error in casual entropy-coding writing.

The distinction is concrete. tANS, the "table" variant, precomputes a state-transition table and drives everything with lookups; this is what Yann Collet's Finite State Entropy (FSE) implements, and it is the sequence coder inside Zstandard (Meta Engineering, 2016). rANS, the "range" variant, uses arithmetic on the state directly and is the ANS form JPEG XL uses in its entropy layer, where every stream is coded with either a prefix (Huffman) code or ANS, using 12-bit-precision histograms and a hybrid integer scheme of an entropy token plus 0 to 31 raw bits (libjxl overview).

Range coding, despite the shared word "range" with rANS, belongs to the arithmetic-coding lineage that predates ANS by decades. It tracks an interval, like arithmetic coding, not a single ANS state. So the clean summary is: rANS and tANS are siblings inside ANS; range coding is a cousin over in the arithmetic-coding family. Same-sounding names, different machinery.

Sources: ITU-T T.81; ScienceDirect; Marpe et al., IEEE TCSVT, 2003; Meta Engineering, 2016; libjxl overview; PMC8946946.

From Huffman (1952) to the ANS paper (2009) and its adoption in Zstandard (2016) and JPEG XL (Duda, arXiv, 2009 and 2013; Meta Engineering, 2016).

Does entropy coding matter for images specifically?

Yes, directly. In JPEG XL the entropy layer is not a bolt-on; every stream, DCT coefficients, prediction residuals, and metadata, is coded with either a prefix code or ANS, and the choice affects the final file size on every image (libjxl overview). For still images, the entropy stage is where the transform's savings become actual bytes.

The image case is where ANS's fractional-bit advantage pays off most cleanly. Quantized DCT and prediction coefficients are heavily skewed toward zero, exactly the distribution where Huffman's whole-bit rounding wastes the most and where ANS recovers the difference. JPEG XL's hybrid integer coding, an entropy token plus up to 31 raw bits, is a purpose-built way to handle that long tail of coefficient magnitudes efficiently (libjxl overview).

This connects to the rest of the pipeline. The prediction and transform stages, covered in intra-frame prediction explained and how JPEG compression works, decide which symbols exist. Entropy coding decides their price. For lossless workflows the stakes are even higher, because entropy coding is the only saving available, as we cover in lossless image compression formats. At Inverity, we treat the entropy coder choice as part of measuring true efficiency, because two files at the same visual quality can differ by double-digit percentages based purely on this last stage.

FAQ

Is ANS the same as range coding?

No. ANS and range coding are different families. ANS (including its rANS and tANS variants) tracks a single natural-number state updated by adds, shifts, and table lookups (Duda, arXiv:1311.2540, 2013). Range coding is an older arithmetic-coding technique that tracks a shrinking interval. The shared word "range" in rANS causes the confusion, but the machinery differs.

Why did baseline JPEG use Huffman instead of arithmetic coding?

Patents. ITU-T T.81 defines both a Huffman and an arithmetic QM-coder, and the arithmetic path compresses roughly 5 to 10% smaller, but it was avoided because the QM-coder was patent-encumbered (ITU-T T.81). The free Huffman path let every decoder interoperate, which is why baseline JPEG became universal and most JPEGs are slightly larger than the spec allowed.

What is the difference between rANS and tANS or FSE?

Both are ANS variants. tANS (the "table" form) precomputes a state-transition table; Yann Collet's Finite State Entropy is a tANS implementation, used for sequences in Zstandard (Meta Engineering, 2016). rANS (the "range" form) does arithmetic on the state directly and is the variant JPEG XL uses (libjxl overview).

Is ANS free to use?

ANS was published as open academic research by Jarek Duda in 2009 and 2013, and it now ships in Zstandard, LZFSE, JPEG XL, Draco, Chrome, and more, across Facebook, Apple, Google, Dropbox, and Microsoft (PMC8946946). A later patent application on an ANS variant drew industry pushback, which is worth checking for your specific use, but the core method was published openly.

Does ANS help lossy or only lossless compression?

Both, because entropy coding is the final stage of lossy and lossless codecs alike. In lossy formats like JPEG XL, ANS codes the quantized coefficients after the lossy transform (libjxl overview). In lossless tools like Zstandard, it codes the exact data. The gain is the same mechanism: fractional bits per symbol at high speed.

The stage that quietly changed

Entropy coding is the least glamorous part of a codec and one of the most improved in the last decade. Huffman gave us speed and whole-bit waste. Arithmetic coding gave us the entropy limit and a per-symbol multiply. For thirty years those were the only options, and general-purpose compression mostly chose speed and ate the waste.

ANS ended that compromise. A single integer state, updated with adds and table lookups, reaches arithmetic-coding ratios at Huffman-like speed, which is why Zstandard, LZFSE, and JPEG XL all adopted it within a few years of each other. If you are auditing where your bytes go, do not stop at the transform. The last stage, the one that actually writes the bits, may be the one leaving the most on the table. Read the next stage back in how lossy compression decides what to discard, and the picture is complete.