Incomputer science, anFM-index is a compressed full-textsubstring index based on theBurrows–Wheeler transform, with some similarities to thesuffix array. It was created by Paolo Ferragina and Giovanni Manzini,[1] 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.[2]
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. The query time, as well as the requiredstorage space, has asublinear complexity 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".[3] A further improvement, the alphabet-friendly FM-index, combines the use of compression boosting andwavelet trees[4] to significantly reduce the space usage for large alphabets.
The FM-index has found use in, among other places,bioinformatics.[5]
Using an index is a common strategy to efficiently search a large body of text. When the text is larger than what reasonably fits within a computer's main memory, there is a need to compress not only the text but also the index. When the FM-index was introduced, there were several suggested solutions that were based on traditional compression methods and tried to solve the compressed matching problem. In contrast, the FM-index is a compressed self-index, which means that it compresses the data and indexes it at the same time.
An FM-index is created by first taking theBurrows–Wheeler transform (BWT) of the input text. For example, the BWT of the stringT ="abracadabra$" is "ard$rcaaaabb", and here it is represented by the matrixM where each row is a rotation of the text, and the rows have been sorted lexicographically. The transform corresponds to the concatenation of the characters from the last column (labeledL).
| I | FL |
|---|---|
| 1 | $abracadabra |
| 2 | a$abracadabr |
| 3 | abra$abracad |
| 4 | abracadabra$ |
| 5 | acadabra$abr |
| 6 | adabra$abrac |
| 7 | bra$abracada |
| 8 | bracadabra$a |
| 9 | cadabra$abra |
| 10 | dabra$abraca |
| 11 | ra$abracadab |
| 12 | racadabra$ab |
The BWT in itself allows for some compression with, for instance,move to front andHuffman encoding, but the transform has even more uses. The rows in the matrix are essentially the sorted suffixes of the text and the first column F of the matrix shares similarities withsuffix arrays. How the suffix array relates to the BWT lies at the heart of the FM-index.
| c | $ | a | b | c | d | r |
|---|---|---|---|---|---|---|
| C[c] | 0 | 1 | 6 | 8 | 9 | 10 |
| a | r | d | $ | r | c | a | a | a | a | b | b | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
| $ | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| a | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 5 | 5 |
| b | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 |
| c | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| d | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| r | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
It is possible to make a last-to-first column mappingLF(i) from an indexi to an indexj, such thatF[j] =L[i], with the help of a tableC[c] and a functionOcc(c, k).
The last-to-first mapping can now be defined asLF(i) = C[L[i]] + Occ(L[i], i). For instance, on row 9,L isa and the samea can be found on row 5 in the first columnF, soLF(9) should be 5 andLF(9) = C[a] + Occ(a, 9) = 5. For any rowi of the matrix, the character in the last columnL[i] precedes the character in the first columnF[i] also in T. Finally, ifL[i] = T[k], thenL[LF(i)] = T[k - 1], and using the equality it is possible to extract a string ofT fromL.
The FM-index itself is a compression of the stringL together withC andOcc in some form, as well as information that maps a selection of indices inL to positions in the original stringT.
The operationcount takes a patternP[1..p] and returns the number of occurrences of that pattern in the original textT. Since the rows of matrixM are sorted, and it contains every suffix ofT, the occurrences of patternP will be next to each other in a single continuous range. The operation iterates backwards over the pattern. For every character in the pattern, the range that has the character as a suffix is found. For example, the count of the pattern "bra" in "abracadabra" follows these steps:
If the range becomes empty or the range boundaries cross each other before the whole pattern has been looked up, the pattern does not occur inT. BecauseOcc(c, k) can be performed in constant time, count can complete in linear time in the length of the pattern:O(p) time.
The operationlocate takes as input an index of a character inL and returns its positioni inT. For instancelocate(7) = 8. To locate every occurrence of a pattern, first the range of character is found whose suffix is the pattern in the same way thecount operation found the range. Then the position of every character in the range can be located.
To map an index inL to one inT, a subset of the indices inL are associated with a position inT. IfL[j] has a position associated with it,locate(j) is trivial. If it's not associated, the string is followed withLF(i) until an associated index is found. By associating a suitable number of indices, an upper bound can be found.Locate can be implemented to findocc occurrences of a patternP[1..p] in a textT[1..u] inO(p +occ logεu) time with bits per input symbol for anyk ≥ 0.[1]
FM index with backtracking has been successfully (>2000 citations) applied to approximate string matching/sequence alignment, See Bowtiehttps://bowtie-bio.sourceforge.net/index.shtml
The FM-Index is available in multiple languages, includingC++,[6]Java[7] andRust.[8] Despite all of them being an implementation of the FM-Index, some feature different data structures for compressing the input text, e.g. with the Rust version being available as both a standard FM-Index and a run-length encoded[9] FM-Index or the Java version using fixed block boosting compression[10] wavelet trees.