# Byte-pair substitution: payload and stored bytes

Byte-pair encoding can shorten a payload while enlarging its stored representation.
This original teaching model separates byte substitutions, table storage and framing.
It does not implement Gage's historical bitstream, fast pair-count maintenance or
block-selection policy. No throughput or real-corpus compression claim is made.

## Reproduce

Requires Python 3.10 or newer and the standard library, with no network or packages.

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

The first command recomputes all eight constructed cases and checks exact equality
with results.json. Use model.py --write only when intentionally regenerating it.
The tests exhaust all 5,461 inputs of lengths 0 through 6 over four byte values,
compare two decoding implementations, and check both representation policies.

## Declared policy

- Count every adjacent pair, including overlapping occurrences.
- Choose the greatest count, then the lexicographically smallest byte pair.
- Stop if the greatest count is below two or no unused byte remains.
- Allocate the smallest byte unused by the original input or any prior rule.
- Replace disjoint occurrences left to right and recount after each pass.
- Keep every assigned code reserved, even if it disappears from the payload.
- Process one block, bounded at 1 MiB. The naive rescanning algorithm is for
  small examples, not production compression.

For aaaa the pair aa has three adjacent occurrences but only two non-overlapping
substitutions. The all-byte-values case cannot allocate a code in this one-block
model. Gage's 1994 implementation instead divides input into blocks while
preserving spare byte values; the example is not a limitation of every BPE codec.

## Exact teaching format

All integers are unsigned and big-endian. A header has four magic bytes BPE1,
a two-byte rule count, a four-byte decoded length and a four-byte payload length:
14 bytes total. Each ordered rule stores three bytes: replacement, left, right.
The final payload uses one byte per literal or replacement code. There is no
checksum, entropy coder, index, padding, filesystem metadata or replication.

| Constructed input | Input bytes | Rules | Header bytes | Rule bytes | Payload bytes | Stored bytes |
| --- | ---: | ---: | ---: | ---: | ---: | ---: |
| ab repeated 4 times | 8 | 2 | 14 | 6 | 2 | 22 |
| ab repeated 128 times | 256 | 7 | 14 | 21 | 2 | 37 |
| every byte value twice | 512 | 0 | 14 | 0 | 512 | 526 |

These are measured lengths of this explicitly defined representation. They are
not estimates for Gage's table encoding, a production format, or typical files.
Full traces and wire bytes are in results.json.

The parser rejects repeated rule codes, forward/self references, malformed
lengths, trailing data and expansions beyond the caller's bounded output quota.
It checks expanded length before allocating output. Structural checks do not
authenticate content: replacing the first rule's b by c in the short example
still passes all length checks and decodes to acacacac.

With the correct pair table, any payload-code boundary can be expanded independently.
Finding the compressed code containing a specified original-byte offset requires
mapping the expansion lengths or maintaining an index. These coordinates differ.

## Choose a stored representation, not only a shorter payload

The default compressor keeps its original stopping rule so the earlier examples
remain reproducible. An optional `compress(data, smallest_prefix=True)` selects
the smallest full representation among all visited merge prefixes, including
zero substitutions. Equal stored sizes prefer fewer rules. It does not claim an
optimal grammar or test alternative pair choices, block splits or wire formats.

| Input | All passes: rules / payload / stored bytes | Smallest prefix: rules / payload / stored bytes |
| --- | ---: | ---: |
| ab repeated 4 times | 2 / 2 / 22 | 1 / 4 / 21 |
| ab repeated 128 times | 7 / 2 / 37 | 6 / 4 / 36 |

For the 256-byte example, complete sizes after zero through seven passes are
270, 145, 84, 55, 42, 37, 36 and 37 bytes. The last pass saves two payload bytes
but adds a three-byte rule. Keeping four payload bytes therefore stores one byte
less than keeping two. The selected stream still decodes to the same 256 bytes.

In this fixed teaching format, a pass with k disjoint replacements changes stored
size by 3 - k bytes. The adjacent-pair count is not that k when matches overlap.
For twelve a bytes, the first two passes both yield 23 stored bytes; the selector
keeps one rule instead of two. For data with no profitable prefix, even the
zero-rule representation still pays the 14-byte header: this is not a guarantee
of shrinking every file. Gage's encoded pair table has a different marginal cost.

The JSON includes every prefix size and the chosen wire bytes. These exact
constructed checks concern representation size, not compression throughput.

## Primary sources and scope

- Philip Gage, [A New Algorithm for Data Compression](https://jacobfilipp.com/DrDobbs/articles/CUJ/1994/9402/gage/gage.htm),
  C Users Journal, February 1994, archived original article. Mechanism, byte budget,
  block adaptation and table cost. The original listing's threshold, hash-table
  tie order and allocation policy differ from this model.
- Philip Gage, [Random Access Data Compression](https://jacobfilipp.com/DrDobbs/articles/CUJ/1997/9709/gage/gage.htm),
  September 1997. Access from compressed payload positions with a loaded table;
  not a general original-offset index or integrity guarantee.
- Larsson and Moffat, [Offline Dictionary-Based Compression](https://avadeaux.net/larsson.dogma.net/dcc99.pdf),
  DCC 1999, sections 2.2-2.3. Re-Pair uses an extended alphabet and separate
  dictionary/sequence encoding, not a fixed supply of unused bytes.
- Sennrich, Haddow and Birch, [Neural Machine Translation of Rare Words with Subword Units](https://aclanthology.org/P16-1162/),
  ACL 2016, section 3.2, DOI 10.18653/v1/P16-1162. A character-sequence adaptation
  trained on word frequencies, not the original byte-bounded storage format.

Accessed 2026-11-18. Only original Hesela code and generated examples are included;
third-party prose, listings, datasets and figures are not redistributed.
