↩ back to Exact Match

FM-Index

This site's Burrows-Wheeler Transform page names the FM-Index without building it: the "foundation" real genome aligners like BWA and Bowtie use to search a reference genome against millions of short reads. The FM-Index is what you get when you stop treating the transform as a compression preprocessing step and instead treat it as a search index in its own right. It needs no suffix array and no copy of the original text — just the transform itself (the same string that page's Encode button already produces) plus two small derived tables, C[] and a rank function Occ — to answer "does this pattern occur, and how many times" in time that depends only on the pattern's length, never the text's, by walking the pattern backward, one character at a time.

That makes it a third mechanism answering the same "index once, query many times" question this site's Suffix Array and Suffix Tree pages already answer — not a replacement for either, but the one built by reusing a reversible rearrangement instead of extending a sorted array or a trie. See Complexity for exactly what that trade costs and buys.

Try it

Enter a text (lowercase letters only, up to 16 characters) and press Build. The demo appends a sentinel ($) and sorts every rotation, the same way Burrows-Wheeler Transform does, to produce the first column F and last column L (the transform itself) shown below, plus the C[] table — everything the search needs, and nothing else. Then enter a pattern and press Step or Run: watch a range of rows [sp, ep] narrow one pattern character at a time, processed from the last character to the first, until what remains is exactly the rows whose rotation starts with the whole pattern. The final step locates each surviving row's real position in the text by walking the LF-mapping backward to the sentinel — no stored suffix array involved — and cross-checks the result against a plain brute-force scan.

Why it works

The first column F is every character of the text, sorted — so it's already grouped into contiguous blocks, one per distinct character, in a fixed, predictable order. That means F never needs to be stored at all: the block for character c runs from row C[c] to row C[c] + count(c) - 1, and C[] is O(σ) numbers, not O(n) characters. This demo displays F anyway, for visibility, but the search functions below never read it — L, the transform itself, is the index's only real payload.

A pattern is matched backward: last character first. At every step a range [sp, ep] tracks exactly the rows whose rotation currently starts with the suffix of the pattern matched so far. Extending that match one character to the left — from P[i+1..] to P[i..] — means finding, among rows sp..ep, every one whose preceding character (that's exactly what L records for each row) is P[i], then re-expressing those rows' positions in the block where P[i] sits in F. The Burrows-Wheeler Transform's own reversibility guarantees a stronger fact than "the same characters appear in both columns": the k-th occurrence of any character in L, read top to bottom, corresponds to the k-th occurrence of that same character in F — the exact rank-preserving correspondence (LF-mapping) this site's own Burrows-Wheeler Transform page invokes by name to justify its decoder, without needing the machinery to compute it directly. Occ(c, i), the count of c in L[0..i-1], is precisely that rank. So the new range is one arithmetic step, no scanning:

sp' = C[c] + Occ(c, sp)
ep' = C[c] + Occ(c, ep + 1) - 1

The direction is load-bearing, not a style choice. L only ever records the character before each row's suffix, so this recurrence can only extend a match by prepending a new leftmost character — matching the pattern's last character first is what makes every subsequent step a valid extension. Trying to extend a match by appending a character to its right instead needs to know which rows correspond to a longer suffix than the one currently tracked, information this recurrence structurally doesn't carry; see Pitfalls for exactly how often that mistake still produces a plausible-looking wrong answer.

None of this ever touches the original text, a suffix array, or even F — sp, ep, C, and Occ are all derived from L alone. That's the compressed self-index property real FM-indexes are built for: keep only the transform plus two small tables, and an arbitrary pattern still resolves to an exact row range in O(m) steps. This page's Occ is a full precomputed prefix table — simple to verify, but O(nσ) to store. Production FM-indexes replace it with a compact rank structure answering the identical query in far less space; this site's own Wavelet Tree is exactly that mechanism, since Occ(c, i) is precisely the rank query a wavelet tree built over L already answers, in O(log σ) time and close to information-theoretic-minimum space instead of one full-length array per character.

A row range proves how many matches exist, but sp and ep are positions in the sorted rotation order, not in the original text. Recovering an actual match position reuses the same LF-mapping mechanism Burrows-Wheeler Transform's own decoder needs but never builds: walking LF(row) = C[L[row]] + Occ(L[row], row) backward from a matching row moves exactly one position earlier through the original text each step, and row 0 is always the rotation beginning right after the sentinel — true position 0. So counting how many LF-steps a row takes to reach the row whose L character is the sentinel gives that row's real starting offset directly, with no suffix array stored at any point in the process. Real implementations bound this walk's worst case by sampling the suffix array every k positions rather than always walking to the sentinel.

Reference implementation

This is the exact scheme the demo above steps through (the BWT construction itself — sorting rotations to get L — is the same naive build Burrows-Wheeler Transform uses, omitted here since that page already covers it):

// C[c] = count of characters strictly less than c across the whole transform
function buildC(bwt) {
  const counts = {};
  for (const ch of bwt) counts[ch] = (counts[ch] || 0) + 1;
  const chars = Object.keys(counts).sort();
  const C = {};
  let total = 0;
  for (const ch of chars) { C[ch] = total; total += counts[ch]; }
  return C;
}

// Occ(c, i) = count of c in bwt[0..i-1] -- a full prefix table here for clarity;
// a production FM-index answers this with a compact rank structure (e.g. a Wavelet
// Tree over the transform) instead of one O(n)-length array per character.
function buildOcc(bwt) {
  const n = bwt.length;
  const chars = Array.from(new Set(bwt)).sort();
  const occ = {};
  chars.forEach(c => { occ[c] = new Array(n + 1).fill(0); });
  for (let i = 0; i < n; i++) {
    for (const c of chars) occ[c][i + 1] = occ[c][i];
    occ[bwt[i]][i + 1]++;
  }
  return occ;
}

// backward search: narrow [sp, ep] one pattern character at a time, LAST character first
function backwardSearch(pattern, C, Occ, n) {
  let sp = 0, ep = n - 1;
  for (let i = pattern.length - 1; i >= 0; i--) {
    const c = pattern[i];
    if (!(c in C) || !Occ[c]) return { sp: 1, ep: 0 }; // c never occurs -- empty range
    const newSp = C[c] + Occ[c][sp];
    const newEp = C[c] + Occ[c][ep + 1] - 1;
    if (newSp > newEp) return { sp: 1, ep: 0 };
    sp = newSp; ep = newEp;
  }
  return { sp, ep }; // every row in [sp, ep] is a match; count = ep - sp + 1
}

// LF-mapping: a row's position in the last column, mapped to its position in the first
function LF(row, bwt, C, Occ) {
  const c = bwt[row];
  return C[c] + Occ[c][row];
}

// locate a match's start position with no suffix array stored: walk LF until landing on
// the row whose L character is the sentinel -- that row is always true position 0
function locate(row, bwt, C, Occ) {
  let r = row, steps = 0;
  while (bwt[r] !== '$') { r = LF(r, bwt, C, Occ); steps++; }
  return steps;
}

Pitfalls

Matching the pattern forward instead of backward looks like the more natural loop direction, and is wrong 11.1% of the time. Nothing about the recurrence itself crashes or throws if the loop runs i = 0..pattern.length-1 instead of counting down — it just silently answers a different, unrelated question, since L only supports extending a match on its left (see Why it works). On this page's own default text "mississippi", searching for "ssip" backward correctly finds 1 occurrence (position 4); scanning the same pattern forward instead reports 0, even though "ssip" plainly occurs. Stress-tested directly: 100,000 random (text, pattern) trials against a brute-force scan (texts length 3–22, alphabets of size 1–5, patterns length 1–5) — the backward reference implementation above matched brute force in all 100,000; searching forward instead disagreed in 11,073 — 11.1% of the time.

Building C[] from "count of characters ≤ c" instead of "count of characters < c" is a one-symbol change that's wrong 34.0% of the time. The natural-looking off-by-one: accumulating each character's own count into the running total before recording it, instead of after, shifts every C[c] up by exactly count(c). On "mississippi" searched for "ip", the correct C[] table finds 1 occurrence (position 7); the shifted table reports 0, because the inflated C['i'] now points past the block of rows that actually start with i. Stress-tested the same way, 100,000 trials: the reference implementation 0 mismatches, this version wrong in 34,032 — 34.0% of the time — worse than the direction bug above because it corrupts every single query, not just ones with a specific structural overlap.

Locating a match without a stored suffix array needs the LF-mapping walk checked independently, not assumed correct because backward search itself is correct. They're different claims: backward search only proves a row range exists, not that walking LF from any row in it to the sentinel recovers that row's true text position. Checked directly: across 5,000 randomly generated texts, walking every one of a text's rows via the exact locate function above and comparing the resulting offset to that same row's independently known position (from the sort used to build F/L in the first place) — 0 mismatches across 67,503 row-locates.

Complexity

Build: the transform itself costs the same naive-sort bound as this site's Burrows-Wheeler Transform and Suffix Array pages, O(n log n) comparisons worst-case O(n² log n) on repetitive text (a real linear-time suffix array construction such as SA-IS sidesteps this). C[] is O(n) once the transform exists. Occ as built here is O(nσ) time and space — a full prefix table per character, traded for clarity; a compact rank structure (see Why it works) gets this close to O(n) bits total instead of O(nσ) words. Search: O(m) steps, one per pattern character, each O(1) with this page's precomputed Occ table (O(log σ) with a wavelet-tree-backed one) — independent of n once the index is built, unlike Suffix Array's O(m log n) binary search. Locate: O(occ · w), where w is each match's LF-walk length to the sentinel — worst case O(n) with no suffix-array sampling, as built here; real implementations bound this to O(k) by storing every k-th row's true position and walking at most k steps to the nearest sample.

This page answers the same question Suffix Array and Suffix Tree already do on this site — index the text once, answer any later pattern cheaply — through a third mechanism: a reversible rearrangement plus two small derived tables, instead of a sorted array or an edge-compressed trie. See Choosing an Exact-Match String Matcher for how it compares against all ten entries answering that shared question.