Module 6. Source coding: from entropy to real bits

Exercise 1. Huffman by hand

Construct a Huffman code for

P=(0.40,0.20,0.15,0.15,0.10).

Compute $L$ , $H_2(P)$ , and $L-H_2(P)$ . Verify Kraft's inequality.

Show answer and solution

Write the symbols as

a:0.40, \quad b:0.20, \quad c:0.15, \quad d:0.15, \quad e:0.10.

One valid sequence of merges is

$e(0.10)+c(0.15)\to N_1(0.25)$ ;
$d(0.15)+b(0.20)\to N_2(0.35)$ ;
$N_1(0.25)+N_2(0.35)\to N_3(0.60)$ ;
$a(0.40)+N_3(0.60)\to1$ .

Assigning bits to the branches can produce

Symbol	Probability	Code	Length
$a$	0.40	`0`	1
$e$	0.10	`100`	3
$c$	0.15	`101`	3
$d$	0.15	`110`	3
$b$	0.20	`111`	3

The particular zeros and ones may be interchanged; the codeword lengths are what matter.

The expected length is

\begin{aligned} L &=0.40\cdot1 +(0.20+0.15+0.15+0.10)\cdot3\\ &=2.20\ \text{bits/symbol}. \end{aligned}

The entropy is

\begin{aligned} H_2(P) &=-\sum_i p_i\log_2p_i\\ &\approx2.146439\ \text{bits/symbol}. \end{aligned}

Hence the redundancy is

L-H_2(P) \approx0.053561\ \text{bits/symbol}.

Kraft check:

2^{-1}+4\cdot2^{-3} =\frac12+\frac12 =1.

The code uses the entire Kraft budget. Thus, in

L-H_2(P) =D_{\mathrm{KL},2}(P\|Q)-\log_2Z,

we have $Z=1$ , and the whole gap comes from the fact that the dyadic distribution induced by the lengths differs from $P$ .

Exercise 2. When does $L=H$ hold?

Prove that a one-symbol prefix code reaches $L=H_2(P)$ if and only if the distribution is dyadic:

p_i=2^{-k_i}, \qquad k_i\in\mathbb N,

with code lengths satisfying Kraft equality.

Construct an example for

P=\left(\frac12,\frac14,\frac18,\frac1{16},\frac1{32},\frac1{32}\right).

Show answer and solution

For a prefix code, define

Z=\sum_i2^{-\ell_i}\le1, \qquad q_i=\frac{2^{-\ell_i}}{Z}.

The proof of the one-symbol theorem gives

L-H_2(P) =D_{\mathrm{KL},2}(P\|Q)-\log_2Z.

Both terms are nonnegative. Therefore $L=H_2(P)$ holds if and only if

D_{\mathrm{KL},2}(P\|Q)=0 \quad\text{and}\quad Z=1.

The first equality means $P=Q$ , and the second means that the Kraft budget is fully used. Together they imply

p_i=q_i=2^{-\ell_i}.

Because the lengths $\ell_i$ are integers, all probabilities must be of the form

p_i=2^{-k_i}, \qquad k_i\in\mathbb N.

This proves necessity. Conversely, suppose the distribution is dyadic and

\sum_i2^{-k_i}=1.

Kraft's theorem guarantees a prefix code with lengths $\ell_i=k_i$ . Then

L=\sum_i p_i k_i =\sum_i p_i(-\log_2p_i) =H_2(P).

For

P=\left(\frac12,\frac14,\frac18, \frac1{16},\frac1{32},\frac1{32}\right),

one suitable code is

Outcome	Probability	Length	Code
1	$1/2$	1	`0`
2	$1/4$	2	`10`
3	$1/8$	3	`110`
4	$1/16$	4	`1110`
5	$1/32$	5	`11110`
6	$1/32$	5	`11111`

Indeed,

\frac12+\frac14+\frac18+\frac1{16} +\frac1{32}+\frac1{32}=1,

and the expected length is

L =\frac12\cdot1+\frac14\cdot2+\frac18\cdot3 +\frac1{16}\cdot4+2\cdot\frac1{32}\cdot5 =1.9375\ \text{bits}.

The entropy is identical because $\ell_i=-\log_2p_i$ for every outcome.

Exercise 3. A wrong model as extra bits

Let lengths be built from $Q$ :

\ell_Q(x)=\lceil-\log_2q(x)\rceil.

Show that

H_2(P)+D_{\mathrm{KL},2}(P\|Q) \le L_Q < H_2(P)+D_{\mathrm{KL},2}(P\|Q)+1.

Explain which part is due to model mismatch and which part is due to integer rounding.

Show answer and solution

Assume

q(x)>0

for every $x$ with $p(x)>0$ . Otherwise cross-entropy and expected code length are infinite.

By the definition of the ceiling function,

-\log_2q(x) \le \left\lceil-\log_2q(x)\right\rceil < -\log_2q(x)+1.

Multiply by $p(x)$ and sum:

H_2(P,Q) \le L_Q < H_2(P,Q)+1.

Using

H_2(P,Q) =H_2(P)+D_{\mathrm{KL},2}(P\|Q),

we obtain

\boxed{ H_2(P)+D_{\mathrm{KL},2}(P\|Q) \le L_Q < H_2(P)+D_{\mathrm{KL},2}(P\|Q)+1 }.

Interpretation:

$H_2(P)$ is the unavoidable average uncertainty of the source;
$D_{\mathrm{KL},2}(P\|Q)$ is the cost of model mismatch;
the remainder $L_Q-H_2(P,Q)\in[0,1)$ is the cost of integer one-symbol lengths.

With arithmetic coding or long-block coding, the rounding cost is amortized over the sequence, while the KL cost of model mismatch remains proportional to sequence length.

Exercise 4. Terminating an arithmetic code

For ACB in §6.4:

verify the final interval $[0.45,0.48)$ ;
show why the five-bit prefix 01111 is insufficient as a dyadic interval;
find a six-bit interval contained in the target interval;
compare the actual 6 bits with the ideal length $-\log_2 0.03$ .

Show answer and solution

The distribution is

p(A)=0.5, \qquad p(B)=0.3, \qquad p(C)=0.2.

Step 1. Final interval

After $A$ ,

[0,1)\to[0,0.5).

Within this interval, the part assigned to $C$ is its final $20\%$ :

[0.4,0.5).

Its width is $0.1$ . Within it, $B$ occupies the fraction from $0.5$ to $0.8$ :

[0.4+0.1\cdot0.5, 0.4+0.1\cdot0.8) =[0.45,0.48).

The width is

0.48-0.45=0.03 =p(A)p(C)p(B).

Step 2. Why `01111` is not a valid termination

The number

0.01111_2=\frac{15}{32}=0.46875

does lie inside $[0.45,0.48)$ . A finite prefix, however, represents not one point but all binary continuations of that prefix, namely

\left[\frac{15}{32},\frac{16}{32}\right) =[0.46875,0.5).

Its right-hand part lies outside the final interval, so the decoder cannot infer ACB uniquely from that prefix.

Moreover, every five-bit dyadic interval has width

2^{-5}=0.03125>0.03,

so no five-bit interval can fit entirely inside $[0.45,0.48)$ .

Step 3. A six-bit interval

Choose

\left[\frac{29}{64},\frac{30}{64}\right) =[0.453125,0.46875).

It is fully contained in $[0.45,0.48)$ . Since

29=(011101)_2,

we may use the prefix 011101.

Step 4. Comparison with ideal length

-\log_2 0.03 \approx5.058894\ \text{bits}.

The actual code has 6 bits, so the redundancy for this short string is

6-5.058894 \approx0.941106\ \text{bits}.

It is below the general two-bit termination bound for the idealized arithmetic construction.

Exercise 5. Python: gzip, zstd, and language-model NLL

Choose one fixed 10--100 KB UTF-8 file.

Compress it with gzip and zstd.
Compute the NLL of a small autoregressive model, such as GPT-2, with a sliding window.
Convert NLL to theoretical bits and BPB.
Verify that each original token contributes to the loss exactly once.
Compare the model's theoretical code length with the real archives, explicitly excluding model weights.

A checked implementation is provided in the solutions.

Show answer and solution

The code below deliberately does not download text from the Internet. It uses a fixed local file called corpus.txt, making the experiment more reproducible and keeping preprocessing explicit.

Dependencies:

bash

pip install torch transformers zstandard

Python

from __future__ import annotations

import gzip
import hashlib
import math
from pathlib import Path

import torch
from transformers import AutoModelForCausalLM, AutoTokenizer

try:
    import zstandard as zstd
except ImportError as exc:
    raise SystemExit("Install zstandard: pip install zstandard") from exc


FILE_PATH = Path("corpus.txt")
MODEL_NAME = "openai-community/gpt2"
MODEL_REVISION = "607a30d783dfa663caf39e06633721c8d4cfcd7e"
ZSTD_LEVEL = 19
REQUESTED_STRIDE = 512


def read_utf8_file(path: Path) -> tuple[bytes, str]:
    raw = path.read_bytes()
    text = raw.decode("utf-8")
    if not raw:
        raise ValueError("The input file is empty.")
    return raw, text


def model_max_length(model: torch.nn.Module) -> int:
    for name in ("max_position_embeddings", "n_positions", "n_ctx"):
        value = getattr(model.config, name, None)
        if isinstance(value, int) and value > 1:
            return value
    raise ValueError("Could not determine the model context length.")


def causal_lm_nll(
    text: str,
    model_name: str,
    requested_stride: int = 512,
    revision: str = MODEL_REVISION,
) -> dict[str, float | int | str]:
    device = torch.device("cuda" if torch.cuda.is_available() else "cpu")

    tokenizer = AutoTokenizer.from_pretrained(model_name, revision=revision, use_fast=True)
    model = AutoModelForCausalLM.from_pretrained(model_name, revision=revision).to(device).eval()

    token_ids = tokenizer(
        text,
        add_special_tokens=False,
        return_tensors="pt",
    ).input_ids

    n_text_tokens = int(token_ids.size(1))
    if n_text_tokens == 0:
        raise ValueError("The tokenizer produced no tokens.")

    # GPT-2 has no separate BOS token. Using EOS as the shared start symbol
    # defines the probability assigned to the first text token.
    start_id = tokenizer.bos_token_id
    if start_id is None:
        start_id = tokenizer.eos_token_id
    if start_id is None:
        raise ValueError("The tokenizer has neither BOS nor EOS token.")

    start = torch.tensor([[start_id]], dtype=token_ids.dtype)
    ids = torch.cat([start, token_ids], dim=1)

    max_len = model_max_length(model)
    stride = min(requested_stride, max_len - 1)
    if stride < 1:
        raise ValueError("The context length must be at least 2.")

    nll_sum_nats = 0.0
    n_counted = 0

    # Positions 1..N in `ids` are the original text tokens. Each target
    # interval is disjoint, while its input window may overlap for context.
    target_start = 1
    while target_start < ids.size(1):
        target_end = min(target_start + stride, ids.size(1))
        begin = max(0, target_end - max_len)

        chunk = ids[:, begin:target_end].to(device)
        labels = chunk.clone()
        local_target_start = target_start - begin
        labels[:, :local_target_start] = -100

        with torch.inference_mode():
            output = model(input_ids=chunk, labels=labels)

        # Causal-LM loss compares logits[:, :-1] with labels[:, 1:].
        # Counting after this shift avoids the common off-by-one bug.
        n_loss_tokens = int((labels[:, 1:] != -100).sum().item())
        expected = target_end - target_start
        if n_loss_tokens != expected:
            raise RuntimeError(
                f"Window accounting error: {n_loss_tokens=} != {expected=}"
            )

        nll_sum_nats += float(output.loss.item()) * n_loss_tokens
        n_counted += n_loss_tokens
        target_start = target_end

    if n_counted != n_text_tokens:
        raise RuntimeError(
            f"Counted {n_counted} targets, expected {n_text_tokens}."
        )

    total_bits = nll_sum_nats / math.log(2.0)
    return {
        "device": str(device),
        "n_tokens": n_text_tokens,
        "nll_nats": nll_sum_nats,
        "ppl": math.exp(nll_sum_nats / n_counted),
        "bits_per_token": total_bits / n_counted,
        "total_bits": total_bits,
    }


def main() -> None:
    raw, text = read_utf8_file(FILE_PATH)

    gzip_bytes = gzip.compress(raw, compresslevel=9)
    zstd_bytes = zstd.ZstdCompressor(level=ZSTD_LEVEL).compress(raw)
    lm = causal_lm_nll(text, MODEL_NAME, REQUESTED_STRIDE)

    n_bytes = len(raw)
    n_chars = len(text)  # Python Unicode code points, not grapheme clusters.
    theoretical_bytes = float(lm["total_bits"]) / 8.0

    print(f"File: {FILE_PATH}")
    print(f"UTF-8 bytes: {n_bytes:,}; Python characters: {n_chars:,}")
    print(f"Model: {MODEL_NAME}; device: {lm['device']}")
    print(f"Model revision: {MODEL_REVISION}")
    print(f"Corpus SHA-256: {hashlib.sha256(raw).hexdigest()}")
    print(f"Counted text tokens: {lm['n_tokens']:,}")
    print()

    print("Real archives (headers included):")
    print(
        f"  gzip -9: {len(gzip_bytes):,} bytes, "
        f"{8 * len(gzip_bytes) / n_bytes:.4f} BPB"
    )
    print(
        f"  zstd -{ZSTD_LEVEL}: {len(zstd_bytes):,} bytes, "
        f"{8 * len(zstd_bytes) / n_bytes:.4f} BPB"
    )
    print()

    print("Causal-LM NLL-equivalent code (not an emitted archive):")
    print(f"  perplexity: {lm['ppl']:.4f}")
    print(f"  bits/token: {lm['bits_per_token']:.4f}")
    print(f"  theoretical bytes: {theoretical_bytes:,.1f}")
    print(f"  BPB: {float(lm['total_bits']) / n_bytes:.4f}")
    print(f"  BPC: {float(lm['total_bits']) / n_chars:.4f}")
    print()
    print("Model weights, tokenizer files, and entropy-coder overhead are excluded.")


if __name__ == "__main__":
    main()

Why the accounting is written this way

Inside forward(..., labels=...), a causal LM shifts tensors so that

\texttt{logits[:, :-1]} \quad\text{are compared with}\quad \texttt{labels[:, 1:]}.

Multiplying output.loss by the apparent unmasked suffix length can therefore be wrong: after shifting, the first label in a window may not participate in the loss. The code counts targets after the logical shift:

Python

n_loss_tokens = int((labels[:, 1:] != -100).sum().item())

Every original token belongs to exactly one disjoint target interval, although context windows overlap. The final check

Python

assert n_counted == n_text_tokens

protects against omitted and double-counted tokens.

What is being compared

gzip and zstd create real self-contained archive streams; their sizes include format headers.
Model NLL gives the ideal data-code length when the model is already known, but the script does not emit an arithmetic- or range-coded file.
GPT-2 weights, tokenizer files, loader code, and finite-precision entropy-coder overhead are excluded.
Using EOS as the initial symbol is part of the protocol; encoder and decoder must agree on it.
Results depend on the file revision, model, tokenizer, context policy, and possible pretraining contamination. The solution therefore does not claim one reference BPB value.

Bonus. A Bayesian mixture as a universal code

For two Bernoulli models with $p_1=0.2$ , $p_2=0.8$ , and uniform prior weights, construct the mixture probability of a sequence. Verify numerically that

-\log_2Q(x_{1:n}) \le \min_j[-\log_2P_j(x_{1:n})]+1.

Show answer and solution

Let $x_{1:n}\in\{0,1\}^n$ , with two models

p_1=0.2, \qquad p_2=0.8,

and weights $w_1=w_2=1/2$ . For a sequence containing $k$ ones,

P_j(x_{1:n}) =p_j^k(1-p_j)^{n-k},

and the mixture is

Q(x_{1:n}) =\frac12P_1(x_{1:n})+\frac12P_2(x_{1:n}).

Since for every $j$

Q(x_{1:n})\ge\frac12P_j(x_{1:n}),

we have

-\log_2Q(x_{1:n}) \le -\log_2P_j(x_{1:n})+1.

Minimizing the right-hand side over $j$ gives the required bound.

A numerical check in log-space:

Python

from __future__ import annotations

import math
import random


def log2sumexp(values: list[float]) -> float:
    m = max(values)
    return m + math.log2(sum(2.0 ** (v - m) for v in values))


def bernoulli_log2_prob(sequence: list[int], p: float) -> float:
    ones = sum(sequence)
    zeros = len(sequence) - ones
    return ones * math.log2(p) + zeros * math.log2(1.0 - p)


def check_sequence(sequence: list[int]) -> tuple[float, float]:
    parameters = [0.2, 0.8]
    log2_weights = [math.log2(0.5), math.log2(0.5)]
    model_log_probs = [
        bernoulli_log2_prob(sequence, p) for p in parameters
    ]

    mixture_log_prob = log2sumexp(
        [w + lp for w, lp in zip(log2_weights, model_log_probs)]
    )
    mixture_length = -mixture_log_prob
    best_model_length = min(-lp for lp in model_log_probs)

    if mixture_length > best_model_length + 1.0 + 1e-12:
        raise AssertionError("Mixture regret bound was violated.")

    return mixture_length, best_model_length


rng = random.Random(6)
for n in (1, 5, 20, 100, 1000):
    for _ in range(100):
        sequence = [rng.randrange(2) for _ in range(n)]
        mixture_length, best_length = check_sequence(sequence)
    print(
        f"n={n:4d}: last mixture={mixture_length:10.4f} bits, "
        f"best={best_length:10.4f}, regret={mixture_length-best_length:.4f}"
    )

The one bit in the bound is

\log_2\frac1{w_j}=\log_22=1\ \text{bit}.

It is paid once for the entire sequence, not at every step.

Exercise 1. Huffman by hand

Exercise 2. When does L=HL=HL=H hold?

Exercise 3. A wrong model as extra bits

Exercise 4. Terminating an arithmetic code

Step 1. Final interval

Step 2. Why 01111 is not a valid termination

Step 3. A six-bit interval

Step 4. Comparison with ideal length

Exercise 5. Python: gzip, zstd, and language-model NLL

Why the accounting is written this way

What is being compared

Bonus. A Bayesian mixture as a universal code

Exercise 2. When does $L=H$ hold?

Step 2. Why `01111` is not a valid termination