The fastest way to search a string may be to enter through the back door.

That sounds like a trick until you see the data structure. The FM-index keeps a compressed view of a text, then answers an exact-match query by reading the pattern from right to left. Each character tightens an interval in a sorted list of suffixes. When the interval is empty, the pattern is absent. When the interval survives, the suffix-array rows inside it are the match positions.

The query does not scan the text.

It asks the index:

which suffixes could still begin with the pattern I have reconstructed so far?

Every Suffix Is a Future

Take a text ending with a unique sentinel:

banana$

Sort all suffixes:

$        6
a$       5
ana$     3
anana$   1
banana$  0
na$      4
nana$    2

The suffix array is just the position column:

[6, 5, 3, 1, 0, 4, 2]

Manber and Myers introduced suffix arrays as a compact alternative to suffix trees for online string search: a sorted list of suffixes plus auxiliary information can answer fixed-text, many-query substring questions while using substantially less space in practice than suffix trees.1

The suffix array is a map of every future of the string. If you know the rows whose suffixes start with ana, their positions are the matches.

So far, this is an index, not a compression story.

The compression story begins with a column.

The Character Before the Future

For each sorted suffix row, write the character that appears immediately before that suffix in the original cyclic text. For banana$, the last column is:

annb$aa

That string is the Burrows-Wheeler transform. Burrows and Wheeler described it as a reversible transformation that does not itself compress the data, but reorders it so that simple compressors can exploit local clustering.2 The reordering is the point: characters with similar following contexts tend to stand near each other.

The surprising part is that the same transformed string can also be used for search.

The FM-index combines:

  • the BWT last column L;
  • a small table C[c], the number of characters in the text smaller than c;
  • an occurrence counter Occ(c, i), the number of c characters in L[0:i);
  • a sampled suffix array if positions are needed.

Then exact search uses this recurrence:

left'  = C[c] + Occ(c, left)
right' = C[c] + Occ(c, right)

The interval [left, right) contains suffix-array rows matching the suffix of the query processed so far. To prepend a new character c, use counts in the last column to jump to the new interval. This is called backward search.

The text is present, but hidden behind ranks.

Search by Shrinking a Crowd

The lab below builds a suffix array, BWT string, C table, and sampled occurrence checkpoints for a tiny corpus. It verifies three things internally: the BWT round-trips back to the original text, FM-index matches agree with a naive scan, and sparse occurrence checkpoints trade less storage for more local counting.

The default toy genome is:

GATTACAGATTACAAGTCGATGATTACA$

Searching for GATTACA returns three positions: 0, 7, and 21. With checkpoint stride 4, the lab stores 45 occurrence-counter cells instead of the 150 cells a full Occ table would use. The query still works; it just scans short gaps between checkpoints.

A C G T Sentinel

The implementation is intentionally small. It builds suffix arrays by sorting suffixes, not by using an industrial construction algorithm. The search logic is the FM-index part: BWT ranks narrow the suffix-array interval from right to left.

For the default genome, the lab builds BWT ACCTTTCAGGGGAAATCTA$ATTTGAAAA, finds GATTACA at positions 0, 7, and 21, and scans 15 cells between occurrence checkpoints while using 45 sampled counter cells instead of 150 full Occ cells. I swept 64 sample/pattern/stride cases; every FM-index result matched a naive scan and every BWT round-trip returned the original text.

Try banana with pattern ana. The final interval has two suffix-array rows, which map to positions 1 and 3. Try mississippi with issi; the same interval logic finds positions 1 and 4. Try a pattern that is absent. The interval collapses to empty before the whole query has been consumed.

Now change Occ checkpoint stride. At stride 1, every occurrence count is stored, so queries do no local counting. At stride 8, the index stores fewer checkpoint cells and scans farther from the nearest checkpoint. The match positions do not change. The cost accounting changes.

That is the FM-index bargain in miniature: store enough rank information to search without scanning the text, but sample it enough to keep space low.

Compression Smuggled In an Index

Ferragina and Manzini called their structure “opportunistic” because its space falls with the empirical compressibility of the text while still supporting full-text search.3 The insight was not merely “compress the file, then search it.” It was to combine the Burrows-Wheeler transform with suffix-array structure so that compression and indexing share machinery.

The word opportunistic is unusually apt.

If a text is repetitive, the BWT tends to create runs. Runs are friendly to compression. Those same runs also make rank structures compact. The index takes advantage of redundancy without needing to know in advance where the redundancy will be.

This is why BWT-based indexing became so important in genomics. A human genome is large, but it is not random. Short-read aligners need to ask a brutal number of substring questions against a fixed reference. Bowtie used Burrows-Wheeler indexing to align more than 25 million 35-base-pair reads per CPU hour with a reported human-genome memory footprint of about 1.3 GB.4 BWA similarly used backward search with the BWT to align short reads while allowing mismatches and gaps.5

The production tools add the hard parts this toy ignores: inexact matching, quality scores, seeding, paired reads, ambiguity codes, sampled suffix-array recovery, engineering around cache behavior, and many biological edge cases. But the quiet central move is already visible in the lab:

rank in the last column tells you where to jump in the first column

Backward Because the State Is an Interval

Backward search feels odd only if you imagine the text as the thing being read. The FM-index is not reading the text. It is maintaining an interval of sorted suffixes.

After processing the last character of the pattern, the interval contains all suffixes beginning with that character. After processing the previous character, the interval contains all suffixes beginning with those two characters. Each step prepends one character to the already-matched suffix.

The recurrence works because the first column of the sorted rotation matrix is just the sorted characters, while the last column tells us what character precedes each row’s suffix in the original text. Occ preserves the relative rank of equal characters. If this is the third A in the last column, it maps to the third A in the first column.

That rank preservation is the little hinge.

Once you see it, the BWT stops being just a compression transform. It becomes a coordinate system for moving through suffix-array rows.

Representation Chooses the Question

There is a pattern here that shows up all over systems:

the useful representation is the one that makes the next question cheap

A suffix array makes substring search cheap by sorting all suffixes. The BWT makes compression cheap by grouping similar contexts. The FM-index notices that those are not separate tricks. They are two views of the same sorted object.

That is what makes the structure feel elegant. It does not bolt an index onto a compressed blob. It finds search inside the compression.

The search starts at the end because the index remembers what came before.

  1. Udi Manber and Gene Myers, “Suffix Arrays: A New Method for On-Line String Searches”, SIAM Journal on Computing, 1993. ↩

  2. M. Burrows and D. J. Wheeler, “A Block-sorting Lossless Data Compression Algorithm”, SRC Research Report 124, 1994. ↩

  3. Paolo Ferragina and Giovanni Manzini, “Opportunistic Data Structures with Applications”, FOCS, 2000. See also the authors’ abstract page. ↩

  4. Ben Langmead, Cole Trapnell, Mihai Pop, and Steven L. Salzberg, “Ultrafast and memory-efficient alignment of short DNA sequences to the human genome”, Genome Biology, 2009. ↩

  5. Heng Li and Richard Durbin, “Fast and accurate short read alignment with Burrows-Wheeler transform”, Bioinformatics, 2009. ↩