FM-index
Encyclopedia
The FM-index is 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, 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".
Burrows-Wheeler transform
The Burrows–Wheeler transform , is an algorithm used in data compression techniques such as bzip2. It was invented by Michael Burrows and David Wheeler in 1994 while working at DEC Systems Research Center in Palo Alto, California...
,
with some similarities to the Suffix Array
Suffix array
In computer science, a suffix array is an array of integers giving the starting positions of suffixes of a string in lexicographical order.-Details:Consider the string...
.
It is named after the creators of the algorithm, 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.
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".