FM-index
From Wikipedia, the free encyclopedia
In computer science, an FM-index is a type of substring index based on the Burrows-Wheeler transform, with some similarities to the suffix array.
It is named after the creators of the algorithm, 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.
It allows both the query time and storage space requirements to be sublinear 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".[2]
[edit] References
- ^ Paolo Ferragina and Giovanni Manzini (2000). "Opportunistic Data Structures with Applications". Proceedings of the 41st Annual Symposium on Foundations of Computer Science. p.390.
- ^ Paolo Ferragina and Rossano Venturini "FM-Index version 2"
