= FM-index
{c}
An <FM-index> is a compressed text index supporting <backward search> through the <Burrows-Wheeler transform> and occurrence counts. Character <rank queries> locate a matching interval; sampled <suffix array> positions then allow the actual text positions to be recovered. Query length, number of matches and the chosen sampling density control different parts of the search cost.<Opportunistic Data Structures with Applications by Paolo Ferragina and others>[§§3.1–3.2, counting and locating occurrences]{ref}
Back to article page
