Entropy Coding Overview, in depth: the entropy bound, Kraft, models versus coders, and choosing Huffman, arithmetic, ANS or Rice

Models and coders are separate jobs

A compressor has two jobs that are easy to blur together. The model assigns a probability to each possible next symbol, possibly depending on context. The coder turns the actual symbol and its probability into bits. The decoder runs the same model on the symbols it has already decoded, so it sees the same probabilities and can invert the coder. Most compressors also run a transform first, such as LZ77 matches, the Burrows-Wheeler transform or pixel prediction, which turns the data into symbols that are easier to model.

The split matters in practice. When compression is disappointing, the fix is almost always in the model or the transform. Swapping Huffman for arithmetic coding gains at most about one bit per symbol, and on large alphabets with flat distributions it gains almost nothing.

The bound: entropy and Kraft-McMillan

A symbol of probability p carries -log₂ p bits of information. A symbol with probability 1/2 carries one bit, and one with probability 1/1024 carries ten. The entropy of a distribution is the expected information content, H = -Σ p_i log₂ p_i bits per symbol. Shannon's source coding theorem says no lossless code can average fewer than H bits per symbol for data drawn from that distribution, and that codes can get arbitrarily close.

Two cautions apply. First, H is a property of the model, not of the file. The same bytes have one entropy under a byte-frequency model and a much lower one under a model that conditions on the previous byte. Second, the bound assumes the decoder already knows the model. A static code must also transmit its table, and an adaptive code pays a learning cost while its estimates settle.

Prefix codes, in which no codeword is a prefix of another, obey the Kraft-McMillan inequality: codeword lengths l_i are achievable exactly when Σ 2^-l_i ≤ 1. The ideal length -log₂ p_i is rarely a whole number, and rounding up gives an average length L with H ≤ L < H + 1. Huffman's algorithm finds the best whole-bit lengths, but it cannot spend less than one bit on any symbol. When one symbol has probability 0.9 and carries 0.15 bits of information, Huffman still spends a full bit on it. That gap is why arithmetic coding and ANS exist.

Measure before you choose

Before choosing a coder, measure three numbers on representative data: the order-0 entropy (from symbol frequencies alone), the Huffman average length, and the order-1 entropy (conditioned on the previous symbol). This harness computes all three:

import heapq, math
from collections import Counter

def entropy(counts):
    n = sum(counts.values())
    return -sum(c / n * math.log2(c / n) for c in counts.values() if c)

def huffman_lengths(counts):
    if len(counts) == 1:
        return {s: 1 for s in counts}
    heap = [(c, i, [s]) for i, (s, c) in enumerate(counts.items())]
    heapq.heapify(heap)
    length, tie = dict.fromkeys(counts, 0), len(heap)
    while len(heap) > 1:
        c1, _, s1 = heapq.heappop(heap)
        c2, _, s2 = heapq.heappop(heap)
        for s in s1 + s2:
            length[s] += 1                      # every merge adds one bit
        heapq.heappush(heap, (c1 + c2, tie, s1 + s2))
        tie += 1
    return length

def report(data):
    counts, n = Counter(data), len(data)
    lens = huffman_lengths(counts)
    huff = sum(counts[s] * lens[s] for s in counts) / n
    pairs, prev = Counter(zip(data, data[1:])), Counter(data[:-1])
    h1 = -sum(c / (n - 1) * math.log2(c / prev[a]) for (a, _), c in pairs.items())
    print(f"order-0 {entropy(counts):.3f}  Huffman {huff:.3f}  order-1 {h1:.3f}")

Worked example 1: a skewed source. Draw 100,000 symbols with P(A) = 0.90, P(B) = 0.05, P(C) = 0.03 and P(D) = 0.02. The true entropy is 0.618 bits per symbol, and the harness measures 0.621. Huffman assigns lengths 1, 2, 3 and 3 and averages 1.152 bits per symbol, 86% above the bound. An arithmetic coder or ANS with the same order-0 model gets within a few bits of the bound for the whole message. The ANS sketch below spends 607 bits on 1,000 such symbols, against an information content of 605.5 bits. The only fix within Huffman is to code blocks of several symbols together, which makes the alphabet grow exponentially.

Worked example 2: a Markov source. Each symbol repeats the previous one with probability 0.9, and otherwise is drawn uniformly from four symbols. The order-0 entropy is 1.999 bits, so frequency counting sees noise and Huffman spends 2.000. The order-1 entropy is 0.498 bits, four times better. Even zlib, whose LZ77 stage catches the runs, reaches 0.663 bits per symbol. No coder can recover what the model does not see, which is the point of the model/coder split.

The coder families

The coders differ in how they approach -log₂ p, what they cost per symbol and how easily their probabilities can change.

Two practical boundaries are worth remembering. On byte alphabets with fairly flat distributions, Huffman already sits within a few percent of entropy, and its decoding speed usually wins. On binary or highly skewed decisions, which is how video codecs code most syntax elements, arithmetic coding or ANS is the only way to spend a fraction of a bit.

ANS on one page

Asymmetric numeral systems (ANS), introduced by Jarek Duda, keep the whole coding state in one integer x. Quantise the probabilities to integer frequencies f_s that sum to M, with cumulative starts c_s. Encoding s maps x to (x div f_s) × M + c_s + (x mod f_s), which grows x by a factor of about M/f_s, or -log₂(f_s/M) bits. Decoding reads the slot x mod M, finds the symbol whose range contains it, and inverts the step. With Python's unbounded integers the idea fits in a few lines:

def build(freqs):                       # e.g. {"A": 90, "B": 5, "C": 3, "D": 2}
    start, total = {}, 0
    for s, f in freqs.items():
        start[s], total = total, total + f
    return total, start, dict(freqs)

def encode(msg, model):
    M, start, freq = model
    x = 1
    for s in reversed(msg):             # last in, first out
        f = freq[s]
        x = (x // f) * M + start[s] + (x % f)
    return x

def decode(x, n, model):
    M, start, freq = model
    out = []
    for _ in range(n):
        slot = x % M
        s = next(t for t in start if start[t] <= slot < start[t] + freq[t])
        x = freq[s] * (x // M) + slot - start[s]
        out.append(s)
    assert x == 1                       # the initial state must come back
    return out

Real implementations keep x in a 32- or 64-bit register and stream out low bits whenever x would overflow (renormalisation). The decoder reads those bits back in reverse. Because decoding pops symbols in the reverse of the order they were pushed, encoders buffer a block and encode it backwards, which suits block-based formats and is awkward for adaptive models that must update after every symbol. That is why video codecs, which adapt per symbol, still use arithmetic coding.

Integers and residuals: Golomb-Rice

Prediction residuals in audio, images and sensor data follow a two-sided, roughly geometric distribution around zero. Golomb-Rice coding suits them and needs no table. First map signed residuals to non-negative integers by zigzag (0, -1, 1, -2, 2 become 0, 1, 2, 3, 4). Then write the quotient v >> k in unary and the low k bits in binary, for (v >> k) + 1 + k bits.

def zigzag(x):
    return 2 * x if x >= 0 else -2 * x - 1

def rice_bits(values, k):
    return sum((v >> k) + 1 + k for v in values)

# block: one block of zigzagged residuals
best_k = min(range(16), key=lambda k: rice_bits(block, k))

Worked example 3. For 100,000 residuals drawn from a rounded Gaussian with standard deviation 6, the cost per value for k = 0 to 5 is 10.11, 6.32, 4.93, 4.75, 5.19 and 6.01 bits. The optimum k = 3 lands within 0.12 bits of the residual entropy of 4.63 bits, and the rule of thumb k ≈ log₂(mean zigzag value) = 3.19 predicts it. Choosing k per block adapts to loud and quiet passages. FLAC uses Rice coding for exactly this job.

Where each coder ships

The same logic extends to learned models. A language model that assigns probability p to the next token can drive an arithmetic coder, which then spends about -log₂ p bits on it. The model's cross-entropy is therefore its compression rate, which is the link between perplexity and compression.

Failure modes

• Encoder and decoder models diverge. One different floating-point rounding, a model updated before instead of after coding a symbol, or a frequency reset at a different block boundary corrupts every following symbol. Use integer frequencies and keep a single update function shared by both sides.
• Zero-probability symbols. A symbol the model scored at zero cannot be coded at all. Give every symbol a minimum frequency, or provide an escape symbol.
• Table overhead on small blocks. A Huffman or FSE table can cost more than it saves on a block of a few hundred bytes. Formats include a raw or predefined-table mode for this case, and encoders should try it.
• Precision limits. Quantising probabilities to a total of 2¹² caps how skewed a symbol can be, and range coders need the total frequency kept well below the register range. Either limit silently costs ratio.
• Untrusted headers. Code lengths that violate Kraft, or frequency tables that do not sum to M, have caused decoder crashes and out-of-bounds reads. Validate them before building tables.
• Optimising the wrong stage. Hours spent tuning the coder win a few percent when a better context or transform would win tens of percent. Measure order-0 against order-1 entropy first.

Trade-offs

Choose by distribution and constraints rather than by reputation. Use canonical Huffman for byte alphabets, when decoding speed matters most, or when compatibility with DEFLATE matters. Use tANS/FSE for block-static models with skewed symbols, where Huffman's floor would hurt and table speed still matters. Use adaptive arithmetic or range coding when probabilities change after every symbol, as with binary context models, video syntax and learned models. Use Rice or Exp-Golomb for integers whose shape you know, where tables would be overhead. Whichever you pick, the achievable gain is bounded by the gap between your current average length and the model entropy, so measure that gap before writing code.

What to do next

1. Run the harness on a sample of your data and record the order-0 entropy, Huffman average and order-1 entropy.
2. If Huffman is more than 0.1 bits above order-0 entropy, test ANS or arithmetic coding. If order-1 is far below order-0, invest in context modelling first.
3. Try a transform (LZ77 via zlib, or BWT) and re-measure. The transform often matters more than the coder.
4. For numeric residuals, zigzag them and pick a Rice parameter per block with the rice_bits search.
5. Round-trip-test any coder on random and adversarial inputs, including single-symbol, empty and all-distinct blocks, and fuzz the header parser.
6. Read audio codecs to see prediction and entropy coding combined in a shipping system.