# Re-Pair: count the rules as well as the remaining sequence

A short root sequence is not the whole representation. This executable,
constructed example keeps the grammar-symbol ledger separate from a complete,
deliberately simple byte encoding. It is not a production codec or a reproduction
of published compression benchmarks.

## Exact examples

| Input | Input bytes | Binary rules | Root symbols | Grammar symbols | Encoded bytes |
| --- | ---: | ---: | ---: | ---: | ---: |
| empty | 0 | 0 | 0 | 0 | 12 |
| aaa | 3 | 0 | 3 | 3 | 18 |
| aaaa | 4 | 1 | 2 | 4 | 20 |
| abababab | 8 | 2 | 2 | 6 | 24 |
| abcdeabccde | 11 | 3 | 5 | 11 | 34 |
| ab repeated 1024 times | 2048 | 10 | 2 | 22 | 56 |
| all 256 byte values once | 256 | 0 | 256 | 256 | 524 |

These are deterministic outputs, not estimates. No confidence interval applies.
The encoded length includes the whole HGR1 representation described below,
but not filesystem blocks, a transport envelope or external replication.

## Method and format

For each candidate pair, count left-to-right non-overlapping occurrences.
Select the highest frequency, breaking ties by minimum numeric pair by default.
Replace all its disjoint occurrences and recompute. Stop below frequency two.
Original byte symbols are 0..255; successive binary rules are 256, 257, etc.

HGR1 is a teaching format, not a standard: four ASCII magic bytes, little-endian
uint32 rule count, little-endian uint32 root length, then each binary rule's
two uint16 symbols, then the root's uint16 symbols. Rule IDs are implicit in
order. References must target bytes or earlier rules. The fixed byte alphabet
needs no per-file dictionary. Exact length is 12 + 4r + 2c bytes.
There is no entropy coding, checksum, random-access index or raw fallback.

A replacement at f disjoint locations removes f root symbols and adds two
rule symbols: the grammar ledger changes by 2-f. At f=2 it does not shrink.
This says nothing about a variable-width code, header or allocation unit.

The decoder rejects wrong extents, unknown/forward references and expansions
above an explicit output budget. These checks are safety limits, not an
integrity guarantee: a changed valid representation can decode to changed data.

## Reproduce

Run in the directory containing these files, using Python 3.12 or later:

```sh
python3 -B model.py --check
python3 -B test_model.py
python3 -B -O test_model.py
```

The committed JSON includes exact rules, traces, encoded bytes and the model
SHA-256. Exhaustive enumeration covers every binary string of length 0..10:
2047 inputs under each of two tie policies. Separate tests compare pair counts
to a per-pair scan, use a different expansion strategy, check a golden wire
fixture and exercise malformed input. No random seed is needed.

The first enumerated size-changing tie witness is aaabaabaab. Minimum-ID
selection gives 9 grammar symbols and 30 encoded bytes; maximum-ID selection
gives 8 and 28. Both decode to the same ten bytes. This demonstrates dependence
on a specified tie rule, not a claim that one policy wins generally.

## Evidence and limits

[Larsson and Moffat (1999)](https://avadeaux.net/larsson.dogma.net/dcc99.pdf),
sections 2-4, supply the algorithm and the original separation of phrase
derivation from dictionary/message encoding.
[Furuya et al. (2020)](https://www.mdpi.com/1999-4893/13/4/103) analyze how
selection order changes grammar size. Their definition includes terminal
productions; their experimental table omits that common contribution.
Our model uses byte terminals directly and states its counting convention.
[Bille et al. (2016 preprint)](https://arxiv.org/pdf/1611.01479v1) specify
construction-space assumptions; this rescan model makes no asymptotic claim.

The input cap is 4096 bytes. There is no measured runtime, peak RAM, search
latency or comparison against gzip, Zstandard or the authors' implementations.
All inputs and teaching code are original to this package. Source PDFs are
linked, not redistributed. See sources.json for versions and private capture
hashes, and the [Re-Pair](https://hesela.dev/terms/re-pair/) and
[grammar compression](https://hesela.dev/terms/grammar-compression/) records.
