The FM-Index

In 2000, Paolo Ferragina and Giovanni Manzini published a deceptively simple idea: take a string, apply the Burrows-Wheeler Transform (BWT), and you simultaneously compress the text and build a searchable index over it. The resulting structure — the FM-index — lets you count every occurrence of a pattern of length $m$ in O(m) time, regardless of how large the underlying text is.

That might sound routine. It is not. Before the FM-index, searching a large text typically meant either keeping the full text in memory (expensive) or decompressing it before searching (slow). The FM-index does neither. It answers queries directly on the compressed representation.

The breakthrough landed at exactly the right moment: the Human Genome Project had just deposited three billion base pairs of DNA into public databases, and researchers desperately needed a way to align short sequencing reads against that reference without loading the entire thing into RAM. Tools like BWA and Bowtie — both built on the FM-index — became the workhorses of an entire generation of genomics. Today every short-read aligner you are likely to encounter uses a variant of this structure.

The core idea rests on two components working together: the BWT, which rearranges the characters of the text so that repeated substrings cluster together (making the text highly compressible), and backward search, which exploits that rearrangement to count pattern occurrences by scanning the pattern from right to left, maintaining a shrinking interval in a sorted array of suffixes.

The demo below builds a small FM-index over the text banana$ and lets you search for any pattern. Each step of backward search narrows a range $[lo, hi)$ in the suffix array — when the range is empty, the pattern is absent; when it closes, the count is $hi - lo$.

<p class="hint">
  {{hint}}
</p>
<div class="controls">
  <input id="pattern" type="text" value="ana" maxlength="12" placeholder="{{placeholder_pattern}}" autocomplete="off" spellcheck="false" />
  <button id="search-btn" type="button">{{btn_search}}</button>
  <button id="reset-btn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="steps-area"></div>
<div id="result-area"></div>
<div class="tables-wrap">
  <div>
    <p class="table-label">{{label_sa_bwt}}</p>
    <table id="sa-table">
      <thead><tr><th>i</th><th>SA[i]</th><th>Suffix</th><th>BWT[i]</th></tr></thead>
      <tbody></tbody>
    </table>
  </div>
  <div>
    <p class="table-label">{{label_f_col}}</p>
    <table id="f-table">
      <thead><tr><th>char</th><th>C[char]</th></tr></thead>
      <tbody></tbody>
    </table>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; gap: .5rem; align-items: center; flex-wrap: wrap; margin-bottom: .8rem; }
input { font: 15px ui-monospace, monospace; padding: .4rem .6rem; border: 1px solid #adb1b8;
        border-radius: 6px; width: 140px; outline: none; }
input:focus { border-color: #1d3557; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
#steps-area { display: flex; flex-direction: column; gap: .35rem; margin-bottom: .5rem; min-height: 1rem; }
.step { font: 13px ui-monospace, monospace; background: #f0f4f8; border-left: 3px solid #1d3557;
        padding: .3rem .6rem; border-radius: 0 5px 5px 0; }
.step.done { border-color: #0a7d33; background: #edf7f0; }
#result-area { font: 700 14px system-ui, sans-serif; min-height: 1.4rem;
               margin-bottom: .8rem; }
.ok { color: #0a7d33; }
.bad { color: #c92f3c; }
.tables-wrap { display: flex; gap: 1.4rem; flex-wrap: wrap; }
.table-label { font-size: .8rem; font-weight: 700; color: #555; margin: 0 0 .25rem; text-transform: uppercase; letter-spacing: .04em; }
table { border-collapse: collapse; font: 13px ui-monospace, monospace; }
th, td { border: 1px solid #cdd9e3; padding: .2rem .55rem; text-align: center; }
th { background: #e8eef3; font-weight: 700; }
.hi-row td { background: #fff3c4; }

// Code not found

Notice that every step does one lookup in a small table (the rank/Occ table). No matter how long the text grows, searching for a pattern of length $m$ still takes exactly $m$ steps. That is the O(m) guarantee — and it holds even though the index stores the text in compressed form.

Compare that with naive search, which must scan every character, or even a suffix array without the BWT, which needs O(m log n) binary search steps. The FM-index eliminates the log-n factor entirely.

The FM-index has proven, tight complexity bounds — this is not an open problem.

Ferragina and Manzini (2000) established all the key results in their original paper:

• Count query: given a pattern of length $m$, count all its occurrences in O(m) time. Each backward-search step does two rank queries on the BWT; with the Occ table sampled at regular intervals, each rank query is O(1).
• Locate query: report the positions of all $occ$ occurrences in O(m + occ · log n) time using a sampled suffix array.
• Space: the index occupies O(n H_k) bits, where $H_k$ is the $k$-th order empirical entropy of the text. For highly repetitive texts like genomes, $H_k$ is very small — the index can be far smaller than the raw text.
• No decompression needed: queries run directly on the compressed structure, unlike gzip-then-search.

The BWT itself is computed in O(n) time using suffix-array construction algorithms (e.g., SA-IS). Index construction is therefore linear.

This places the FM-index in the rare class of data structures that are simultaneously optimal in both time and space. The O(m) search bound cannot be beaten by a comparison-based index (you must read all $m$ characters of the pattern at least once). The space bound matches the information-theoretic lower bound for compressible texts.

Related problems that are not solved: efficiently supporting approximate matching with many mismatches at the same O(m) cost, and maintaining the FM-index under insertions and deletions without rebuilding it. Both remain active research areas. See also pattern matching for the classical string-search landscape.

The FM-index is not an academic toy. It is the production engine behind several of the most widely used tools in biology and information retrieval:

• Short-read alignment: BWA (Li & Durbin, 2009) and Bowtie (Langmead et al., 2009) both index the human reference genome with an FM-index. A sequencing run producing hundreds of millions of 150-base reads is aligned in minutes on a laptop. Without the FM-index that job required a cluster.
• Long-read alignment: Minimap2 uses a sketch-then-extend approach but still relies on compressed suffix structures for its seed lookup.
• Full-text search: the BWT step alone (without the full FM machinery) powers bzip2 compression. Search engines that must index terabytes of text use FM-index variants because they avoid storing the raw text at all.
• Pangenome indexing: as genomics moves from one reference genome to graphs of thousands of haplotypes, tools like GBWT extend the FM-index to handle variation graphs — the same backward-search principle, generalized.
• Database substring search: columnar databases increasingly use BWT-based indexes for pattern queries over large string columns.

The broader lesson: whenever you compress data, you normally sacrifice the ability to query it. The FM-index is one of the few known ways to have both at once.

The FM-index is one of those rare results where theory and practice converge completely. The bounds are proven tight — O(m) to count, O(n H_k) bits to store — and the tools that implement those bounds have processed more DNA than any other software in history.

The key insight is almost philosophical: the Burrows-Wheeler Transform does not destroy information. It rearranges it in a way that makes repeated substrings cluster together, which compresses the text, and simultaneously makes backward search possible. Compression and indexing turn out to be two sides of the same coin.

If you have worked through this article, you now understand the engine that runs every time a bioinformatician aligns a sequencing read, every time bzip2 shrinks a file, and every time a modern search engine avoids storing its corpus twice. The pattern matching article goes deeper into the classical string-search landscape from which the FM-index emerged.