# BWT runs and one located match

This reproducible teaching example accompanies [r-index](https://hesela.dev/terms/r-index/)
and [prefix-free parsing](https://hesela.dev/terms/prefix-free-parsing/).
It is constructed finite evidence, not a production index or a benchmark.

## Same histogram, different run count

| Input (before terminator) | BWT (including terminator) | Maximal runs |
| --- | --- | ---: |
| abab abab, with the space removed | bbbb$aaaa | 3 |
| babbaaba | abbabab$a | 8 |

Both inputs contain four a and four b symbols. Their ordinary zero-order
symbol distributions are identical; their transformed run counts are not.
Thus a character-frequency summary alone does not determine this parameter.
The example does not convert these counts into bytes or promise compression.

## One match is not all matches

The model reuses the existing [exact FM model](../fm-index/README.md).
It stores suffix-array values at both ends of each BWT run. During backward
search, it maintains a row and its text position inside the nonempty interval.
If the preceding character matches, LF navigation preserves this witness.
Otherwise, the matching run has an endpoint inside the previous interval;
the corresponding sample supplies a new witness.

The source for that invariant is Gagie, Navarro and Prezza,
[Optimal-Time Text Indexing in BWT-runs Bounded Space](https://users.dcc.uchile.cl/~gnavarro/ps/soda18.pdf),
SODA 2018, Lemma 3.1. The separate mechanism for enumerating every match
is intentionally absent. This program establishes neither the paper's
asymptotic resource bounds nor a new result.

## Reproduce

Download this directory's model.py, test_model.py and observations.json,
plus the sibling fm-index/model.py, retaining that directory structure.
Use Python 3.10 or newer; no third-party Python dependencies are required.

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

The exhaustive check covers all 511 binary strings of length 0 through 8.
Each is queried with all 62 binary patterns of lengths 1 through 5 and
one absent-symbol query, for 32,193 queries. Direct substring scanning
checks counts and returned witnesses; the full suffix array independently
checks every successful transition. These are not random samples and no
confidence interval or population estimate is implied.

## Scope and units

The input is lowercase ASCII, at most 256 symbols, with a reserved trailing
dollar terminator. Run intervals and query intervals are zero-based and
half-open. Samples store text offsets, not sorted-row numbers.
The constructor materializes suffixes; rank and boundary selection use scans.
The query does not consult the full suffix array after samples are created,
but the model still retains it for validation. No O(r)-space claim applies
to this Python implementation.

Index size, builder peak memory, and supported query operations are separate
measurements. The PFP entry explains why a count-only index size cannot
stand in for locate-capable construction costs.

Code and original synthetic data in this directory: CC0-1.0.
Linked papers retain their own rights and are not redistributed.
