# FM-index: two matches, but where are they?
A constructed, executable explanation of backward search and locate sampling.
The code and constructed observations in this directory are CC0-1.0.
Paper PDFs are linked, not redistributed.

## Reproduce
Use Python 3.10 or newer, with no third-party dependencies:
```sh
python3 -B model.py
python3 -B -m unittest test_model.py
python3 -B -O -m unittest test_model.py
```
The first command recomputes and compares the complete stored JSON, including
the model's SHA-256. `--write` explicitly regenerates that evidence.
Download [model.py](model.py), [test_model.py](test_model.py),
[observations.json](observations.json) into one directory.

## Exact Example
The indexed text is `banana$`, where `$` is a unique smallest terminator.
The suffix array is `[6,5,3,1,0,4,2]`; the BWT is `annb$aa`.
Positions and row numbers are zero-based. Rank excludes its endpoint.
Starting with all rows `[0,7)`, process `ana` right to left:

| Prepended symbol | Matching row interval | Rows |
| --- | --- | --- |
| a | [1,4) | 3 |
| n | [5,7) | 2 |
| a | [2,4) | 2 |

The final interval counts two matches. Its endpoints are row numbers, not
text positions. Locating those rows yields positions 3 and 1.

For stride 4, each policy below stores two positions. Text-position sampling
stores rows whose suffix positions are divisible by 4. Row sampling instead
stores every fourth row of the sorted suffix array.

| Policy | Stored row:position pairs | Maximum LF steps over all 7 rows |
| --- | --- | --- |
| Text positions | 4:0, 5:4 | 3 |
| Sorted rows | 0:6, 4:0 | 5 |

From row 1, row sampling walks `1 -> 5 -> 2 -> 6 -> 3 -> 4`.
The sample at row 4 contains position 0; five steps recover position 5.
Text-position sampling reaches row 5 in one step and recovers 4 + 1 = 5.
This is an exact counterexample to applying the `stride - 1` bound to
arbitrarily regularly spaced *rows*. Both strategies return correct positions.

## Method and Limits
The model materializes sorted suffixes for construction and uses scanning rank.
Search, inverse transform and sampled locate do not read that suffix array.
An independent direct-text oracle checks every nonempty pattern of length 1-4
over `abc` against all 255 texts of length 0-7 over `ab`: 30,600 comparisons,
including overlaps and absent symbols. Rotation sorting checks BWT construction;
every row is located under both policies at strides 1, 2, 3, 4 and 8.
Empty queries are rejected and the terminator is reserved: model choices,
not universal library requirements. Sample positions are trusted; this is
not a parser for untrusted index files.

No compressed-space, throughput or I/O measurements are made. The finite
checks provide regression evidence, not a general proof or paper replication.

## Sources
- [Burrows and Wheeler, SRC Report 124 (1994)](https://www.cs.jhu.edu/~langmea/resources/burrows_wheeler.pdf), sections 1-2 and 4.2.
- [Ferragina and Manzini, FOCS 2000 author draft](https://people.unipmn.it/manzini/papers/focs00draft.pdf), sections 2-3.
- [Ferragina and Manzini, Indexing Compressed Text, JACM 52(4), 552-581 (2005)](https://people.unipmn.it/manzini/papers/jacm05a.pdf), sections 3.1 and 3.3.
- [Navarro, Wavelet Trees for All (2014)](https://users.dcc.uchile.cl/~gnavarro/ps/jda13.pdf), section 5.1.
- [Source manifest](sources.json): access date, downloaded hashes and scope.

Corpus: [FM-index](https://hesela.dev/terms/fm-index/) and
[Burrows-Wheeler transform](https://hesela.dev/terms/burrows-wheeler-transform/).
