Introduction to the FM-Index

Introduction

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.

Try Backward Search

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">
  The FM-index is built over <code id="text-display">bananalt;/code>.
      Type a pattern and press <b>Search</b> to run backward search step by step.
      Each step shrinks the interval <code>[lo, hi)</code> by one character.
</p>
<div class="controls">
  <input id="pattern" type="text" value="ana" maxlength="12" placeholder="pattern" autocomplete="off" spellcheck="false" />
  <button id="search-btn" type="button">Search</button>
  <button id="reset-btn" type="button" class="ghost">Reset</button>
</div>
<div id="steps-area"></div>
<div id="result-area"></div>
<div class="tables-wrap">
  <div>
    <p class="table-label">Suffix Array &amp; 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">F column (first chars)</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// FM-index demo: build an FM-index over TEXT = "banana$", then run
// backward search for any pattern. Each step shrinks [lo, hi) by one char.
// Time: O(m) — exactly m steps, each doing O(1) rank lookups.

const TEXT = 'banana

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.
;
const N = TEXT.length; // 7

// --- Build suffix array (simple O(n^2 log n) — fine for n=7) ---
const SA = Array.from({length: N}, (_, i) => i)
  .sort((a, b) => TEXT.slice(a) < TEXT.slice(b) ? -1 : 1);

// BWT[i] = TEXT[(SA[i] - 1 + N) % N]
const BWT = SA.map(s => TEXT[(s - 1 + N) % N]);

// C table: for each char c, C[c] = number of chars in TEXT that are < c
const ALPHA = [...new Set(TEXT)].sort();
const C = {};
for (const c of ALPHA) {
  C[c] = TEXT.split('').filter(x => x < c).length;
}

// Occ table: Occ[c][i] = number of occurrences of c in BWT[0..i-1]
// We store it as a 2D array for direct O(1) access (small text).
const OCC = {};
for (const c of ALPHA) {
  OCC[c] = new Array(N + 1).fill(0);
  for (let i = 0; i < N; i++) {
    OCC[c][i + 1] = OCC[c][i] + (BWT[i] === c ? 1 : 0);
  }
}

// rank(c, i) = number of c in BWT[0..i-1] = OCC[c][i]
function rank(c, i) { return (OCC[c] && i >= 0) ? OCC[c][Math.min(i, N)] : 0; }

// --- Backward search ---
// Returns array of step objects {char, lo_before, hi_before, lo_after, hi_after}
// plus final {count, lo, hi}
function backwardSearch(pattern) {
  let lo = 0, hi = N;
  const steps = [];
  for (let i = pattern.length - 1; i >= 0; i--) {
    const c = pattern[i];
    const lo_before = lo, hi_before = hi;
    if (!C.hasOwnProperty(c)) { lo = 0; hi = 0; steps.push({char: c, lo_before, hi_before, lo_after: 0, hi_after: 0}); break; }
    const lo_after = C[c] + rank(c, lo);
    const hi_after = C[c] + rank(c, hi);
    lo = lo_after; hi = hi_after;
    steps.push({char: c, lo_before, hi_before, lo_after, hi_after});
    if (lo >= hi) break;
  }
  return { steps, lo, hi, count: Math.max(0, hi - lo) };
}

// --- Render suffix-array table ---
function renderSATable(hiLo = -1, hiHi = -1) {
  const tbody = document.querySelector('#sa-table tbody');
  tbody.innerHTML = '';
  SA.forEach((sa, i) => {
    const tr = document.createElement('tr');
    if (i >= hiLo && i < hiHi) tr.className = 'hi-row';
    const suffix = TEXT.slice(sa);
    tr.innerHTML = `<td>${i}</td><td>${sa}</td><td>${suffix}</td><td>${BWT[i]}</td>`;
    tbody.appendChild(tr);
  });
}

// --- Render C table ---
function renderCTable() {
  const tbody = document.querySelector('#f-table tbody');
  tbody.innerHTML = '';
  for (const c of ALPHA) {
    const tr = document.createElement('tr');
    tr.innerHTML = `<td>${c === '

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.
 ? '&#36;' : c}</td><td>${C[c]}</td>`;
    tbody.appendChild(tr);
  }
}

function setResult(text, cls) {
  const el = document.getElementById('result-area');
  el.textContent = text; el.className = cls || '';
}

function clearSteps() {
  document.getElementById('steps-area').innerHTML = '';
}

function addStep(html, cls) {
  const div = document.createElement('div');
  div.className = 'step' + (cls ? ' ' + cls : '');
  div.innerHTML = html;
  document.getElementById('steps-area').appendChild(div);
}

document.getElementById('search-btn').addEventListener('click', () => {
  const pattern = document.getElementById('pattern').value.trim();
  clearSteps();
  setResult('');
  if (!pattern) { setResult('Enter a pattern above.', ''); renderSATable(); return; }
  const {steps, lo, hi, count} = backwardSearch(pattern);
  let cur_lo = N, cur_hi = 0; // just for display; we'll track per step
  // Replay to show steps
  let display_lo = 0, display_hi = N;
  steps.forEach((s, idx) => {
    const info = fmt('Step %v%: char=’%char%’  [%lo_before%, %hi_before%) → [%lo_after%, %hi_after%)', { v: idx + 1, char: s.char, lo_before: s.lo_before, hi_before: s.hi_before, lo_after: s.lo_after, hi_after: s.hi_after });
    addStep(info, s.lo_after >= s.hi_after ? 'done' : '');
    display_lo = s.lo_after; display_hi = s.hi_after;
  });
  renderSATable(lo, hi);
  if (count > 0) {
    setResult(fmt('✓ "%pattern%" occurs %count% time%v% (rows %lo%–%v2% highlighted).', { pattern: pattern, count: count, v: count > 1 ? 's' : '', lo: lo, v2: hi - 1 }), 'ok');
    console.log(fmt('FM-index: "%pattern%" found %count% time(s) at SA rows [%lo%,%hi%)', { pattern: pattern, count: count, lo: lo, hi: hi }));
  } else {
    setResult(fmt('✗ "%pattern%" not found in ""%TEXT%".', { pattern: pattern, TEXT: TEXT }), 'bad');
    console.log(fmt('FM-index: "%pattern%" not found.', { pattern: pattern }));
  }
});

document.getElementById('reset-btn').addEventListener('click', () => {
  document.getElementById('pattern').value = '';
  clearSteps();
  setResult('');
  renderSATable();
});

// Allow Enter key in input
document.getElementById('pattern').addEventListener('keydown', e => {
  if (e.key === 'Enter') document.getElementById('search-btn').click();
});

// Initial render
renderSATable();
renderCTable();

<p class="hint">
  The FM-index is built over <code id="text-display">bananalt;/code>.
      Type a pattern and press <b>Search</b> to run backward search step by step.
      Each step shrinks the interval <code>[lo, hi)</code> by one character.
</p>
<div class="controls">
  <input id="pattern" type="text" value="ana" maxlength="12" placeholder="pattern" autocomplete="off" spellcheck="false" />
  <button id="search-btn" type="button">Search</button>
  <button id="reset-btn" type="button" class="ghost">Reset</button>
</div>
<div id="steps-area"></div>
<div id="result-area"></div>
<div class="tables-wrap">
  <div>
    <p class="table-label">Suffix Array &amp; 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">F column (first chars)</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// FM-index demo: build an FM-index over TEXT = "banana$", then run
// backward search for any pattern. Each step shrinks [lo, hi) by one char.
// Time: O(m) — exactly m steps, each doing O(1) rank lookups.

const TEXT = 'banana

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.
;
const N = TEXT.length; // 7

// --- Build suffix array (simple O(n^2 log n) — fine for n=7) ---
const SA = Array.from({length: N}, (_, i) => i)
  .sort((a, b) => TEXT.slice(a) < TEXT.slice(b) ? -1 : 1);

// BWT[i] = TEXT[(SA[i] - 1 + N) % N]
const BWT = SA.map(s => TEXT[(s - 1 + N) % N]);

// C table: for each char c, C[c] = number of chars in TEXT that are < c
const ALPHA = [...new Set(TEXT)].sort();
const C = {};
for (const c of ALPHA) {
  C[c] = TEXT.split('').filter(x => x < c).length;
}

// Occ table: Occ[c][i] = number of occurrences of c in BWT[0..i-1]
// We store it as a 2D array for direct O(1) access (small text).
const OCC = {};
for (const c of ALPHA) {
  OCC[c] = new Array(N + 1).fill(0);
  for (let i = 0; i < N; i++) {
    OCC[c][i + 1] = OCC[c][i] + (BWT[i] === c ? 1 : 0);
  }
}

// rank(c, i) = number of c in BWT[0..i-1] = OCC[c][i]
function rank(c, i) { return (OCC[c] && i >= 0) ? OCC[c][Math.min(i, N)] : 0; }

// --- Backward search ---
// Returns array of step objects {char, lo_before, hi_before, lo_after, hi_after}
// plus final {count, lo, hi}
function backwardSearch(pattern) {
  let lo = 0, hi = N;
  const steps = [];
  for (let i = pattern.length - 1; i >= 0; i--) {
    const c = pattern[i];
    const lo_before = lo, hi_before = hi;
    if (!C.hasOwnProperty(c)) { lo = 0; hi = 0; steps.push({char: c, lo_before, hi_before, lo_after: 0, hi_after: 0}); break; }
    const lo_after = C[c] + rank(c, lo);
    const hi_after = C[c] + rank(c, hi);
    lo = lo_after; hi = hi_after;
    steps.push({char: c, lo_before, hi_before, lo_after, hi_after});
    if (lo >= hi) break;
  }
  return { steps, lo, hi, count: Math.max(0, hi - lo) };
}

// --- Render suffix-array table ---
function renderSATable(hiLo = -1, hiHi = -1) {
  const tbody = document.querySelector('#sa-table tbody');
  tbody.innerHTML = '';
  SA.forEach((sa, i) => {
    const tr = document.createElement('tr');
    if (i >= hiLo && i < hiHi) tr.className = 'hi-row';
    const suffix = TEXT.slice(sa);
    tr.innerHTML = `<td>${i}</td><td>${sa}</td><td>${suffix}</td><td>${BWT[i]}</td>`;
    tbody.appendChild(tr);
  });
}

// --- Render C table ---
function renderCTable() {
  const tbody = document.querySelector('#f-table tbody');
  tbody.innerHTML = '';
  for (const c of ALPHA) {
    const tr = document.createElement('tr');
    tr.innerHTML = `<td>${c === '

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.
 ? '&#36;' : c}</td><td>${C[c]}</td>`;
    tbody.appendChild(tr);
  }
}

function setResult(text, cls) {
  const el = document.getElementById('result-area');
  el.textContent = text; el.className = cls || '';
}

function clearSteps() {
  document.getElementById('steps-area').innerHTML = '';
}

function addStep(html, cls) {
  const div = document.createElement('div');
  div.className = 'step' + (cls ? ' ' + cls : '');
  div.innerHTML = html;
  document.getElementById('steps-area').appendChild(div);
}

document.getElementById('search-btn').addEventListener('click', () => {
  const pattern = document.getElementById('pattern').value.trim();
  clearSteps();
  setResult('');
  if (!pattern) { setResult('Enter a pattern above.', ''); renderSATable(); return; }
  const {steps, lo, hi, count} = backwardSearch(pattern);
  let cur_lo = N, cur_hi = 0; // just for display; we'll track per step
  // Replay to show steps
  let display_lo = 0, display_hi = N;
  steps.forEach((s, idx) => {
    const info = fmt('Step %v%: char=’%char%’  [%lo_before%, %hi_before%) → [%lo_after%, %hi_after%)', { v: idx + 1, char: s.char, lo_before: s.lo_before, hi_before: s.hi_before, lo_after: s.lo_after, hi_after: s.hi_after });
    addStep(info, s.lo_after >= s.hi_after ? 'done' : '');
    display_lo = s.lo_after; display_hi = s.hi_after;
  });
  renderSATable(lo, hi);
  if (count > 0) {
    setResult(fmt('✓ "%pattern%" occurs %count% time%v% (rows %lo%–%v2% highlighted).', { pattern: pattern, count: count, v: count > 1 ? 's' : '', lo: lo, v2: hi - 1 }), 'ok');
    console.log(fmt('FM-index: "%pattern%" found %count% time(s) at SA rows [%lo%,%hi%)', { pattern: pattern, count: count, lo: lo, hi: hi }));
  } else {
    setResult(fmt('✗ "%pattern%" not found in ""%TEXT%".', { pattern: pattern, TEXT: TEXT }), 'bad');
    console.log(fmt('FM-index: "%pattern%" not found.', { pattern: pattern }));
  }
});

document.getElementById('reset-btn').addEventListener('click', () => {
  document.getElementById('pattern').value = '';
  clearSteps();
  setResult('');
  renderSATable();
});

// Allow Enter key in input
document.getElementById('pattern').addEventListener('keydown', e => {
  if (e.key === 'Enter') document.getElementById('search-btn').click();
});

// Initial render
renderSATable();
renderCTable();

Result

Console

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 Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/fm-index/Content licensed under CC BY-NC 4.0.

Cookies & privacy

The FM-Index

The compressed index that powers genomic search