FMindexes

The FM-index is a compressed full-text index that enables efficient substring queries on a text without requiring the text to be stored uncompressed. It combines the Burrows–Wheeler transform with a suffix-array based framework to support fast pattern matching in a space-efficient manner.

Core components include the Burrows–Wheeler transform of the text, the suffix array, a C array giving the total number of characters smaller than a given character, and an Occurrence function (Occ) that counts occurrences of a character up to a given position in the BWT. Using these, the backward search algorithm processes the pattern from right to left and repeatedly updates a matching interval in the suffix array, narrowing down where the pattern occurs.

The FM-index achieves fast queries while using space close to the compressed size of the original text. The Occ and rank queries are implemented with auxiliary structures such as wavelet trees or run-length encoded bitvectors, enabling compressed storage and constant- or near-constant-time access.

FM-indexes support exact pattern matching and counting of occurrences efficiently. Locating the actual positions of matches typically requires sampling the suffix array or applying LF-mapping, with performance depending on the chosen sampling strategy. Various variants exist that improve space or query time, including implementations based on compressed suffix arrays and enhanced wavelet-tree based structures.

Introduced by Ferragina and Manzini in 2000, the FM-index is a foundational concept in compressed indexing. It underpins modern substring search in large and repetitive data, contributing to practical search in DNA databases and other extensive text collections where memory efficiency is crucial.