# Move-to-front: ranks, bytes and restart state

An MTF rank is a position in a changing alphabet, not a compressed byte count.
This original fixed-alphabet demonstration uses zero-based ranks and no eviction.
It is not a bzip2 encoder, benchmark or reproduction of a historical experiment.

## Worked example

Starting alphabet: abc. Input: cabbaa. Ranks: 2, 1, 2, 0, 1, 0.
After the first three ranks the alphabet is bac.
Continuing with that state decodes the remaining ranks as baa.
Restarting from abc instead decodes them as abb; all ranks remain in range.
An in-range check alone cannot establish the original output.

For abbbba, the final rank of a is 1: four accesses have occurred since its
last use, but only one distinct other symbol appeared. First occurrences also
depend on initial alphabet order.

With all 256 byte values in the alphabet, one byte per rank uses exactly as many
payload bytes as the input. Even 32 identical bytes still occupy 32 bytes under
this representation. A subsequent coder may exploit the zeros; its format and
metadata determine actual stored size. The JSON is an observation report, not
a proposed compact representation.

## Reproduce

Python 3.9+ standard library, no downloads or packages:

```sh
python3 -B model.py
python3 -B -m unittest -v test_model
python3 -B -O -m unittest -v test_model
```

results.json is generated by model.py --write. Verification regenerates the
examples in memory and compares exact bytes. Six test methods cover 19,680
short sequence/initial-permutation cases, all 519 split positions of a
518-byte fixture, state mismatch, invalid input and byte accounting.
The independent rank oracle counts distinct identities, rather than reusing
the encoder's list-update operation.

## Source distinctions

[Bentley et al., CACM 1986](https://www.cs.cmu.edu/~sleator/papers/adaptive-data-compression.pdf)
describes a word-list scheme with unseen-word transmission. This example
instead uses a known alphabet as in
[Burrows and Wheeler, SRC 124, section 3](https://www.cs.jhu.edu/~langmea/resources/burrows_wheeler.pdf).

The [bzip2 1.0.8 source](https://sourceware.org/pub/bzip2/bzip2-1.0.8.tar.gz)
adds used-alphabet mapping, zero-run tokens, shifted nonzero ranks, an end marker
and entropy coding. This demonstration omits that format.

Files: model.py, test_model.py and results.json. License: CC0-1.0 for these
Hesela-authored files. Linked papers and implementation retain their own licenses.
