FM-index
An FM-index is a compressed full-text index that uses the Burrows-Wheeler transform and rank queries to count pattern occurrences.
Search: With zero-based half-open rows [l,r), let rank(c,p) count c in BWT[0:p] and C(c) count symbols smaller than c. Prepending c updates the interval to [C(c)+rank(c,l), C(c)+rank(c,r)); its width is the match count. Process the pattern right to left. [1]
Locate: Matching rows are not text offsets. LF mapping walks to a row whose text position is stored; the step count recovers the original position. Sampling every s-th text position bounds this walk by s-1 steps. Sampling every s-th sorted row does not give that bound. [2] [4]
Example: In banana$, the BWT is annb$aa. Searching ana yields rows [2,4), which correspond to text positions 3 and 1. With stride 4, text-position and row sampling each store two positions, yet their maximum walks are 3 and 5 steps respectively. [4]
Space: Wavelet trees can supply BWT rank queries. Index size also includes rank support, alphabet metadata and locate samples; count-only structures can omit the locate machinery. Construction workspace and query time must be evaluated for the selected implementation. [3] [2]
Relations
Limitations
- The worked model scans rank prefixes and materializes suffixes for construction; it demonstrates exact results, not a compressed implementation or a performance benchmark. [4]
Citations
- Ferragina and Manzini: Opportunistic Data Structures with Applications, FOCS 2000 author draft, sections 2-3
- Ferragina and Manzini: Indexing Compressed Text, JACM 52(4), 552-581 (2005), sections 3.1 and 3.3
- Navarro: Wavelet Trees for All, Journal of Discrete Algorithms 25 (2014), section 5.1
- Hesela: exact BWT search and text-position versus row-sampling example, executable model and observations
Sources & caveats
- Primary-source synthesis of the original indexing method and subsequent full journal treatment. The worked example uses zero-based half-open intervals, unlike the papers' one-based inclusive notation.
- Constructed finite evidence: all 255 binary-alphabet texts of length 0-7 are checked against 120 nonempty patterns; no real workload or fleet data are used.