Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 37 ยท Huffman and Arithmetic Coding

Comparing Source Coders

Benchmark fixed-length, Shannon, Huffman, block Huffman and arithmetic coding against entropy on different sources, and learn how to choose a coder and where context modelling beats them all.

You now know five ways to turn symbols into bits. This lesson puts them side by side, measures how far each is from the entropy on several kinds of source, and gives a decision guide. It also shows the limit of all of them: memoryless coders cannot exploit context, which is where real compressors get most of their gain.

The contestants

Coder Bits per symbol Needs Weakness
Fixed length ceil(log2 n) nothing ignores probabilities
Shannon ceil(-log2 p) each probabilities up to +1 bit
Huffman optimal whole bits probabilities (or lengths) at least 1 bit per symbol
Block Huffman amortized over blocks probabilities exponential table
Arithmetic -log2 p, +2 bits per message probability model slower, patent history

Benchmark on four sources

We measure the average code length per symbol for sources chosen to expose each coder's behavior: uniform (nothing to gain), dyadic (Huffman perfect), skewed (Huffman wasteful) and a typical text-like distribution. Arithmetic coding is reported as its ideal length, which is the entropy, plus a 2-bit constant that vanishes per symbol.

Python Average code length per symbol

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the rows:

  • Uniform: every coder ties at log2 8 = 3; there is nothing to compress.
  • Dyadic: Shannon and Huffman both equal the entropy, 1.875.
  • Skewed binary: the entropy is about 0.194, but Huffman cannot go below 1 bit: five times worse. Arithmetic coding (or blocks) closes this gap.
  • Text-like: Huffman sits a few hundredths of a bit above entropy, while a fixed 3-bit code wastes about half a bit per symbol.

Where each coder is the right choice

  • Huffman when speed and simplicity matter and probabilities are not extreme: final stage of DEFLATE, JPEG, PNG.
  • Arithmetic / range coding when probabilities are skewed or adaptive: image and video codecs (CABAC), LZMA, bzip3.
  • ANS (tANS, rANS) when you want arithmetic-level compression at Huffman-like speed: Zstandard, Apple LZFSE, JPEG XL, AV1.
  • Fixed length when you need random access to any element.

Context beats better coding

All of the above assume independent symbols. Real data is not. A coder that uses the previous symbol, a first-order context model, pays the conditional entropy H(X_n | X_(n-1)), which is never larger than H(X) and often much smaller.

Python Order-0 versus order-1 entropy of text

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first-order figure is much lower. (A caution: with a short sample, the order-1 table has seen each context only a handful of times, so it partly memorizes the text; the estimate is optimistic. With large corpora the effect is real but smaller.) Compressors that model longer contexts (PPM, CM, LZMA) go further still.

A practical shoot-out against zlib

zlib (DEFLATE) combines an LZ77 dictionary stage with Huffman coding. Let us compare the ideal order-0 cost with zlib's output on a text.

Python Order-0 entropy bound versus zlib

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

zlib is far below the order-0 bound because the text repeats: LZ77 replaces repeats with short back-references, something no memoryless coder can do. On text without repetition the picture reverses and zlib lands near the entropy.

Rule of thumb for building a compressor: model first, code second. Better probabilities (context, mixing, adaptivity) save far more than switching between Huffman and arithmetic coding.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. For which kind of source does Huffman coding waste the most compared with the entropy?

    Its 1-bit-per-symbol floor is far above a tiny entropy.
  2. 2. Which coder is typically used when speed and simplicity matter most?

    Huffman decoding is a table lookup, which is why it remains in DEFLATE, JPEG and PNG.
  3. 3. Why can an order-1 context model beat the order-0 entropy?

    Conditioning reduces entropy on average, and dependent sources gain the difference.
  4. 4. What do ANS coders offer?

    Asymmetric numeral systems are used in Zstandard and modern image/video codecs.

Summary

  • Fixed, Shannon, Huffman, block Huffman and arithmetic coding differ by how close they get to the entropy and what they cost.
  • Huffman is near-optimal for moderate skew but wasteful when one symbol dominates; arithmetic coding and ANS fix that.
  • All memoryless coders are bounded by the order-0 entropy; context models and dictionary methods go beyond it.
  • Rule of thumb: improve the model before changing the coder.

Next: Mutual Information and Discrete Channels