# Tunstall coding: count the symbols behind each index

A two-bit index can represent one, two or three input symbols. Dividing total
bits by total symbols therefore answers a different question from averaging
the bits-per-symbol cost of each phrase.

## Exact worked example

Assume independent symbols with P(A)=3/4 and P(B)=1/4. Expand the most probable
leaf until four phrases fit the two-bit index budget. Alphabetical index
assignment here is illustrative, not a file-format convention.

| Index | Phrase | Probability | Symbols | Constructed count |
| --- | --- | --- | --- | --- |
| 00 | AAA | 27/64 | 3 | 27 |
| 01 | AAB | 9/64 | 3 | 9 |
| 10 | AB | 3/16 | 2 | 12 |
| 11 | B | 1/4 | 1 | 16 |

The mean phrase length is 37/16 symbols. For this memoryless model, the
long-stream payload rate is 2/(37/16)=32/37, about 0.865 bit per input symbol.
In contrast, averaging 2/L over phrases gives 17/16=1.0625 bits per symbol.
Neither calculation is a measured file size. The second weights phrase
occurrences, while the first accounts for all symbols they contain.

A deliberately constructed sequence containing the listed counts has 64 phrases,
148 binary source symbols and 128 index bits. Its aggregate ratio is 128/148.
With an illustrative 32-bit metadata charge it would occupy 160 bits, exceeding
a one-bit-per-symbol representation of those 148 symbols. This charge is an
assumption, not a measured codebook size.

## The end of a file still matters

Input AA stops at an internal node: it has no complete phrase index. The program
returns an explicit unencoded tail. Padding A or AA to AAA would give index 00
in either case; exact reconstruction needs a termination rule such as a separately
preserved original length. No such on-disk format is implemented here.

The mapping also matters: 00 and 01 both decode successfully but give different
strings. Fixed index boundaries do not authenticate the data. Decoding an
aligned index is possible with the dictionary, but locating an arbitrary
uncompressed symbol offset also needs accumulated phrase lengths or an index.

For a three-symbol alphabet, every expansion adds two leaves. A three-bit
budget in the included example yields seven phrases, leaving one index unused.
The decoder rejects that unused index.

## Reproduce

Python standard library only. The code uses exact rational arithmetic.

```sh
python3 -B model.py --check
python3 -B -m unittest discover -s . -p test_model.py
python3 -B -O -m unittest discover -s . -p test_model.py
```

[Model](model.py), [tests](test_model.py), [generated results](results.json).

The heap constructor is checked against a separate two-queue implementation
of Baer's binary selection algorithm. The latter avoids repeatedly searching
all leaves: only queue heads compete. This does not make arbitrary-precision
fraction arithmetic or materialized phrase strings constant-cost.
The tests also enumerate all short binary inputs through length ten and all
full binary trees with two, four or eight leaves for a small probability grid.

## Evidence and limits

The construction and expected-length identity follow Drmota, Reznik, Savari
and Szpankowski, [Precise Asymptotic Analysis of the Tunstall Code](https://www.cs.purdue.edu/homes/spa/papers/isit06-tunstall.pdf)
(ISIT 2006, sections I-II). Baer's
[2009 paper](https://arxiv.org/abs/0809.0949v3), sections I-II, explains the
two-queue construction; its P(A)=0.7 example is independently recalculated in
the tests. Arimura's [2010 abstract](https://doi.org/10.1587/transfun.E93.A.1904)
explicitly distinguishes the two average-rate definitions.

This is a worked calculation, not a compression benchmark or a new optimality
proof. The 3/4 example, stream counts and metadata charge are hypothetical.
Finite-file framing, dictionary serialization, model training, nonstationary
sources, errors and throughput are outside the model. No statistical confidence
interval applies to deterministic arithmetic.
