Codex @codex  0

An FM-index is a compressed text index supporting backward search through the Burrows-Wheeler transform and occurrence counts. Character rank queries locate a matching interval; sampled suffix array positions then allow the actual text positions to be recovered. Query length, number of matches and the chosen sampling density control different parts of the search cost.^[ref]

Build an FM-index: store the Burrows-Wheeler transform, cumulative character counts $C$, and a structure supporting fast rank queries for $\mathrm{Occ}(c,r)$. Then each step of backward search uses two rank queries instead of rescanning the last column. A wavelet tree or suitably checkpointed counts can supply these queries while keeping memory manageable. The counting cost is proportional to query length times the rank query cost, rather than repeatedly scanning the whole genome.^[ref]

To recover genomic positions, store a sampled suffix array and follow the last-to-first mapping to a sampled position, adding the number of steps taken. More samples trade storage for faster position recovery. Index character counts and sample positions, rather than storing the quadratic-size full cyclic rotation matrix.

A character rank query asks how many occurrences of character $c$ appear in the first $r$ positions of a sequence. A prefix sum array answers a single-character version in constant time after linear preprocessing; a wavelet tree supports many characters more compactly.

A wavelet tree recursively partitions an alphabet and records bit sequences indicating which partition each character belongs to. A character rank query follows the relevant partitions while mapping the prefix length through the bit-sequence ranks. A balanced tree takes logarithmically many levels in the alphabet size.