In computer science, an FM-index is a compressed full-text substring index based on the Burrows-Wheeler transform, with some similarities to the suffix array. It was created by Paolo Ferragina and Giovanni Manzini, who describe it as an opportunistic data structure as it allows compression of the input text while still permitting fast substring queries. The name stands for Full-text index in Minute space.
It can be used to efficiently find the number of occurrences of a pattern within the compressed text, as well as locate the position of each occurrence. Both the query time and storage space requirements are sublinear[clarification needed] with respect to the size of the input data.
The original authors have devised improvements to their original approach and dubbed it “FM-Index version 2“. A further improvement, the alphabet-friendly FM-index, combines the use of compression boosting and wavelet trees to significantly reduce the space usage for large alphabets.
The FM-index has found use in, among other places, bioinformatics.
Bullard, Desmond R., and Richard P. Bowater. “Direct Comparison of Nick-Joining Activity of the Nucleic Acid Ligases from Bacteriophage T4.”Biochemical Journal 398.Pt 1 (2006): 135–144. PMC. Web. 5 July 2016.
Let S be a set of positive integers. The subtraction game with subtraction set S is played as follows. From a pile with a large number, say n, of chips, two players alternate moves. A move consists of removing s chips from the pile where s ∈S. Last player to move wins.