How to Learn the FM-Index: Burrows–Wheeler Transform, Backward Search, Rank Queries and Compressed Full-Text Search

Quick Read. The FM-index is one of the most important examples of a data structure that is both compressed and searchable. A beginner should first understand the Burrows–Wheeler Transform as a reversible reordering of a string’s rotations or suffix order. An intermediate learner should understand the first column, last column, cumulative character counts and rank queries. An advanced learner should derive backward search one character at a time. A professional should understand sampling, locate versus count queries, alphabet handling, memory layout and why compressed indexing matters in large text and bioinformatics systems.

One-sentence answer

The FM-index combines the Burrows–Wheeler Transform with rank-support data so that pattern matching can be performed directly over a compressed representation, shrinking a current suffix-array interval from the end of the pattern toward the beginning.

Why this algorithmic idea is remarkable

Many learners first meet compression and searching as opposite goals. Compression seems to hide information in a compact form; searching seems to demand direct access to information. The FM-index shows that this opposition is not absolute. With the right transformation and auxiliary data, a text can be stored near its compressed size while still supporting efficient full-text pattern queries.

The original Ferragina–Manzini work on compressed full-text indexing exploited the relationship between suffix arrays and the Burrows–Wheeler Transform. That relationship is the centre of the lesson. Do not start by memorising formulas. Start by understanding what rows of suffix order are telling you.

Level 1 — Beginner: start from suffix order

Consider BANANA$, where $ is a unique sentinel smaller than the ordinary alphabet symbols. Sort all suffixes lexicographically. The suffix array is the list of starting positions in that order. If you write the character immediately preceding each sorted suffix, wrapping the sentinel case appropriately, you obtain the Burrows–Wheeler last column, usually called L.

Another way to visualise the same transform is to sort all cyclic rotations and read the last column. The rotation-table picture is excellent for beginners because it makes the transform visible. The suffix-array picture is usually better for professional implementations because it connects directly to indexing.

The first key idea: F and L contain the same characters

Let F be the first column of the sorted rows and L the last. They are permutations of the same multiset of characters. More importantly, if repeated characters are numbered by their occurrence order, the kth occurrence of a character in L corresponds to the kth occurrence of the same character in F. This is the LF-mapping idea.

That correspondence lets us move from one text position to the preceding text position without reconstructing the entire text. Backward search turns that navigation into pattern matching.

Level 2 — Intermediate: C and Occ/rank

The FM-index normally teaches two compact pieces of information.

• C[c] is the number of characters in the text that are lexicographically smaller than character c. It therefore tells you where the block of suffixes beginning with c starts in F.
• Occ(c, i), often implemented as a rank query, counts how many copies of c occur in L[0..i) or an equivalent half-open convention.

The indexing convention matters. Many bugs come from mixing inclusive and exclusive rank definitions. Pick one convention, write it at the top of your implementation, and test boundary positions aggressively.

Backward search

Suppose the current suffix-array interval [l, r) contains exactly the suffixes beginning with the pattern fragment already processed. To prepend a character c, update the interval:

l = C[c] + Occ(c, l)
r = C[c] + Occ(c, r)

Then continue with the next character of the pattern moving right-to-left. If at any point l == r, the pattern does not occur. If the process finishes, the interval size r - l is the number of matches.

Why searching backwards is natural

Suffix arrays group strings by common prefix. If you already know the interval for pattern P, the LF structure tells you which rows have a particular preceding character c. Those are exactly the rows corresponding to cP. The FM-index therefore extends a query on the left, so the pattern must be consumed from right to left.

A worked miniature search

Use BANANA$ and search for ANA. Begin with the full suffix-array interval. Process the final A first, restricting the interval to suffixes beginning with A. Then prepend N, shrinking the interval to suffixes beginning with NA. Finally prepend A, leaving the suffixes beginning with ANA. The final interval size is the occurrence count.

Do this by hand before writing code. The purpose of the exercise is to make the interval semantics visible: the two numbers are not arbitrary pointers; they describe a contiguous block in suffix order.

Level 3 — Advanced: rank is where the engineering begins

A classroom implementation can store a prefix-count table for every character and every position, making Occ constant time but using substantial space. A professional compressed index cannot casually spend alphabet × text length counters. It uses succinct rank-support structures, bitvectors, wavelet trees, wavelet matrices or alphabet-specific encodings to answer rank queries compactly.

This creates a useful systems lesson: the mathematical FM-index is a family of design points. Query speed, construction time, memory footprint, alphabet size, cache behaviour and support for locating text positions all interact.

Count, locate and extract are different jobs

• Count. Return how many times a pattern occurs. Backward search directly produces this from the final interval.
• Locate. Return the original text positions of the matches. This normally requires sampled suffix-array values plus repeated LF steps.
• Extract. Recover text regions. This may require additional sampling or companion structures.

A learner who says “the FM-index finds the pattern” has not yet separated these jobs. Professional design begins when the required query contract is explicit.

Level 4 — Professional: what changes in real systems?

• Alphabet encoding. DNA may have a tiny alphabet; Unicode text does not. Remapping symbols to dense integers can simplify rank structures.
• Sampling rate. More suffix-array samples speed locate queries but consume memory. Fewer samples compress better but require more LF steps.
• Construction strategy. Building the BWT for data larger than RAM requires external-memory or streaming-aware methods.
• Run-length compression. Highly repetitive collections may benefit from run-length-aware BWT indexes and related modern compressed indexes.
• Cache locality. Theoretical rank complexity does not reveal how many cache misses a representation creates.
• Parallelism. Query batches may parallelise well even when a single backward search is inherently sequential over pattern characters.
• Versioning. A classic FM-index is naturally static. Frequently changing text may require rebuilding, batching or a different dynamic indexing strategy.

Correctness: the interval invariant

The cleanest correctness proof uses one invariant: after processing a suffix of the query pattern, [l, r) contains exactly the suffix-array rows whose text suffixes begin with that processed query fragment. The C table selects the block beginning with the next character, while the two rank values count how many qualifying rows occur before the old interval boundaries. Therefore the updated interval contains exactly the rows beginning with the extended fragment.

This is an excellent algorithm-proof pattern to learn: define what a pair of state variables means, then prove that one update preserves that meaning.

Pseudocode for counting occurrences

count(pattern):
    l = 0
    r = n

    for c in reverse(pattern):
        if c is not in alphabet:
            return 0

        l = C[c] + rank(c, l)
        r = C[c] + rank(c, r)

        if l == r:
            return 0

    return r - l

Before implementing a compressed rank structure, make this version work with a simple prefix-count table. Separate algorithm correctness from compression engineering.

Testing strategy

• Verify that BWT inversion reconstructs the exact original text including the sentinel.
• For every character and every position, compare your rank implementation against a naive count.
• For small random strings, compare FM-index counts with direct substring search.
• Test absent characters, empty patterns, full-text patterns, repeated characters and sentinel boundaries.
• For locate support, compare every returned position with a naive suffix-array or direct-search oracle.
• Measure memory separately for the BWT, rank support, C table and samples. “Compressed” should be measured, not assumed.

Common misconceptions

• “The BWT itself is the FM-index.” The transform is the central reordered text; the FM-index adds rank/count support and usually sampling machinery.
• “The BWT always compresses the text.” The transform is reversible and tends to cluster similar contexts; actual compression requires an encoding stage.
• “Backward search scans the text backwards.” It scans the pattern backwards while updating an interval over suffix order.
• “Finding the count means locating the positions is free.” Locate normally requires additional sampled information and extra LF steps.
• “All rank structures are equivalent.” Their space, speed, alphabet handling and cache behaviour can differ dramatically.

A learning route from beginner to professional

• Beginner: manually sort suffixes and build F and L.
• Early intermediate: number repeated characters and trace LF mapping.
• Intermediate: calculate C and rank tables by hand and run backward searches.
• Advanced: implement count queries, prove the interval invariant, then add locate sampling.
• Professional: replace naive rank tables with a succinct structure and benchmark memory/query trade-offs on realistic alphabets and text distributions.

A strong study technique is to predict each interval before calculating it, then explain why the new interval is correct. After that, reconstruct the search loop from shuffled blocks, modify the rank convention, and finally implement from the invariant alone. This reduces the temptation to memorise a formula whose meaning is not yet owned.

When should you use an FM-index?

Use it when you need full-text substring search over large, mostly static data and memory matters enough that an uncompressed pointer-heavy index is unattractive. It is especially influential in sequence analysis and compressed text indexing. Do not choose it merely because its asymptotic story is impressive. If updates are frequent, the collection is small, or engineering simplicity dominates, a suffix array, search engine index, trie, database index or another structure may be better.

Authoritative sources and further reading

• Paolo Ferragina and Giovanni Manzini, Indexing Compressed Text, Journal of the ACM 52(4), 2005.
• Research summary from the University of Eastern Piedmont, including the relationship between suffix arrays, the BWT and compressed full-text indexing.
• For the learning progression, see current research on Parsons problems and computing-education learning theories and PRIMM.

Closing idea. The FM-index is worth learning because it changes the question from “How can I search after I decompress?” to “How can I design the representation so searching and compression cooperate?” That is a professional algorithm-design habit far beyond text indexing.