Compression foundations: count bits under an explicit model

Lossless compression must give each possible input a distinguishable representation. A useful compressor spends fewer bits on likely inputs and accepts that some others expand. The bit I/O module turns those representations into bytes; first learn to calculate what they cost.

From counts to an average

Suppose a source emits A, B, C, D with counts 8, 4, 2, 2 in a 16-symbol sample. Normalize by 16: p=(1/2,1/4,1/8,1/8). The ideal information costs -log2(p) are 1, 2, 3, 3 bits. Their weighted sum is:

H = (8*1 + 4*2 + 2*3 + 2*3) / 16 = 28/16 = 1.75 bits/symbol

A prefix code A=0, B=10, C=110, D=111 attains exactly that average. Fixed two-bit codes cost 32 bits for these counts; this code costs 28 payload bits. That is only four bits saved before headers, termination, and byte padding. A one-byte table header already reverses the win for this sample.

Entropy is an expectation under a probability model, not a promise that every file shrinks to that size. A histogram also discards order: AAAABBBB and ABABABAB have the same byte counts but different runs. A model that conditions on prior bytes can exploit relationships absent from a single-symbol model.

Prefix space is a budget

No complete codeword may begin another. A word of length l reserves fraction 2^-l of the binary tree's eventual leaves. The previous code spends:

1/2 + 1/4 + 1/8 + 1/8 = 1

For lengths [1,1,2], the sum is 1.25: impossible. Two one-bit words already occupy both first-level branches. Lengths [2,2,2] spend 3/4 and leave one branch unused; incomplete trees are valid. Kraft's inequality tests feasibility of lengths; it does not prove an arbitrary assignment is prefix-free. The assignment 0,00 fails even though lengths [1,2] have sum 3/4.

For a nondegenerate source and an optimal binary prefix code, H <= L < H+1. A deterministic single-symbol source has H=0; this pack deliberately assigns its symbol one bit to simplify framing, an exception to the strict upper bound under that convention. Huffman optimizes weighted lengths, not headers or a whole file's representation.

Model mismatch has a measurable cost

Imagine the true probabilities for X,Y are p=(3/4,1/4), but a fractional-bit coder predicts q=(1/4,3/4). Its ideal average is:

H(p,q) = -(3/4)*log2(1/4) -(1/4)*log2(3/4)
       ≈ 1.604 bits/symbol
H(p)   ≈ 0.811 bits/symbol
extra ≈ 0.792 bits/symbol

This cross-entropy calculation isolates model quality from integer code lengths and framing. Predicting probability zero for a possible symbol is worse: there is no code interval to emit. A practical model needs nonzero support or an escape mechanism.

The entropy exercise takes nonnegative counts, ignores zero-count entries, and returns zero for an empty total. Use floating division before log2; integer division would turn probabilities below one into zero. Sum expected cost as sum(p[i]*length[i]), not as an unweighted average of lengths.

Choose tokens by actual cost

A dictionary match covering three bytes may cost 17 bits while three literals cost 15. The match is longer than one literal, but it is not cheaper than all bytes it replaces. This pack's LZ77 exercise deliberately requires greedy longest matching for determinism; a format optimizer could instead compare complete parse costs. Keep the algorithm's contract separate from an optimal-compression claim.

For n-bit inputs there are 2^n possibilities but only 2^n-1 shorter binary strings, including the empty string. Distinct inputs cannot all receive shorter encodings. That counting argument explains expansion without any claim about implementation quality.

Reconstruct it

1. A source has counts [6,3,3] and lengths [1,2,2]. Compute payload cost and average.
2. Can lengths [1,2,2,3] form a prefix code?
3. If a 40-bit header enables savings of two bits per symbol, when does total cost first improve, before byte rounding?

Model answers

1. 6+6+6=18 bits, or 1.5 bits/symbol. The probabilities are 1/2,1/4,1/4, so the code reaches H.
2. No: 1/2+1/4+1/4+1/8=1.125.
3. At 21 symbols: 20 ties and 21 saves two bits. Byte padding can move the actual file-size threshold.

See Shannon's original paper for the source-coding framework. The examples above are calculations for this pack, with their model and framing assumptions stated explicitly.