fm-index · shipping · also Ferragina-Manzini index

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

related
Burrows-Wheeler transform, Rank/select, Wavelet tree, r-index

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

  1. Ferragina and Manzini: Opportunistic Data Structures with Applications, FOCS 2000 author draft, sections 2-3 (accessed 2026-11-17)
  2. Ferragina and Manzini: Indexing Compressed Text, JACM 52(4), 552-581 (2005), sections 3.1 and 3.3 (accessed 2026-11-17)
  3. Navarro: Wavelet Trees for All, Journal of Discrete Algorithms 25 (2014), section 5.1 (accessed 2026-11-17)
  4. Hesela: exact BWT search and text-position versus row-sampling example, executable model and observations (accessed 2026-11-17)
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.

JSON: /data/terms/fm-index.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. FM-index. Hesela. 2026-11-17. https://hesela.dev/terms/fm-index/