File FMIndex.h

↰ Parent directory (ADS/compression)

The FM-index of Ferragina and Manzini (section 14.5 of the notes): the transform of Burrows and Wheeler of s [see File BurrowsWheeler.h] as an index of its substrings, which replaces the suffix array and the text.

Definition (ADS/compression/FMIndex.h)

Detailed Description

  • count( P ) is the backward search (Algorithm 14.3): the rows of M’ prefixed by :math:` P[ i , p - 1 ] ` are a range [ first , last ), and those prefixed by :math:` c P[ i , p - 1 ] `, c = P[ i - 1 ], are [ C[ c ] + rank_c( first ) , C[ c ] + rank_c( last ) ), the LF-mapping of the first and of the last occurrence of c in L[ first , last ); so p steps, each two ranks, give the range of P and its number of occurrences, last - first, with no access to the text.

  • locate( P ) finds the place of each row of the range: the rows of the suffixes that start at a multiple of :math:` mu ` are marked, with their places, and from any row the LF-mapping, which moves one symbol to the left in s, reaches a marked row in t < :math:` mu ` steps, the place being that of the marked row plus t; :math:` O( mu ) ` steps per occurrence and :math:` O( ( n / mu ) log n ) ` bits of samples (Theorem 14.8).

  • extract( i , j ) gives s[ i , j ) from the row of the first sampled suffix at or after j, by :math:` j - i + O( mu ) ` steps of LF.

The rank of a symbol in L, the number of its occurrences in a prefix, is the count stored every b places for each symbol of the text plus a scan of fewer than b symbols, 8 at a time by the zero bytes of a word, O( b ) time and :math:` sigma ( n / b ) ` counts of 32 bits; the marks of the rows are a vector of bits with the rank directory of RankSelect [see File RankSelect.h], so a row is tested and its sample found in O( 1 ) time. The counts of L are the simplest rank on a sequence, which any structure of rank and select on sequences can replace [see File WaveletMatrix.h]: the wavelet tree of Grossi, Gupta and Vitter gives the rank in :math:` O( log sigma ) ` time on :math:` n H_0 + o( n log sigma ) ` bits, and the compressed representations of Ferragina, Manzini, Makinen and Navarro reach :math:` n H_k + o( n log sigma ) ` bits, the space of the compressed text (Lemma 14.3 and Theorem 14.7). The transform is built from the suffix array of SA-IS, O( n ) time [see File BurrowsWheeler.h]. Against the suffix array, which counts by binary search in :math:` O( p log n ) ` time and :math:` n log n ` bits plus the text, the FM-index counts in O( p b ) time here, O( p ) with a rank in O( 1 ), at the price of random accesses to L at each step; the r-index of Gagie, Navarro and Prezza samples only the ends of the runs of L, and takes space proportional to their number r, small on repetitive texts.

The contracts [see File Contract.h]: b and :math:` mu ` are positive, n is below :math:` 2^{32} , a pattern is not empty, :math: i le j le n `; each place found by locate() is an occurrence, an audit. The operations are defined in FMIndex.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 14

  1. Ferragina, G. Manzini, Opportunistic data structures with applications, IEEE Symposium on Foundations of Computer Science, 390-398, 2000, doi:10.1109/SFCS.2000.892127

  1. Ferragina, G. Manzini, Indexing compressed text, Journal of the ACM 52(4), 552-581, 2005, doi:10.1145/1082036.1082039

  1. Grossi, A. Gupta, J. S. Vitter, High-order entropy-compressed text indexes, ACM-SIAM Symposium on Discrete Algorithms, 841-850, 2003

  1. Ferragina, G. Manzini, V. Makinen, G. Navarro, Compressed representations of sequences and full-text indexes, ACM Transactions on Algorithms 3(2), 20, 2007, doi:10.1145/1240233.1240243

  1. Navarro, V. Makinen, Compressed full-text indexes, ACM Computing Surveys 39(1), 2, 2007, doi:10.1145/1216370.1216372

  1. Gagie, G. Navarro, N. Prezza, Fully functional suffix trees and optimal text searching in BWT-runs bounded space, Journal of the ACM 67(1), 2, 2020, doi:10.1145/3375890

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes