File RIndex.h

↰ Parent directory (ADS/compression)

The r-index of Gagie, Navarro and Prezza: the FM-index of a text s of n bytes in space proportional to the number r of the runs of its transform L of Burrows and Wheeler, rather than to n [see File FMIndex.h, File HuffmanFMIndex.h], so that a repetitive text (the versions of a document, the genomes of a species), where r is far smaller than n, takes far less; count( P ) in :math:` O( p ) ` steps of rank on the runs and locate( P ) in :math:` O( p + occ ) ` more of predecessor searches.

Definition (ADS/compression/RIndex.h)

Detailed Description

L is kept as its runs: the start of each run in an Elias-Fano sequence [see File EliasFano.h], the symbol of each run (its head) in a wavelet tree of Huffman [see File HuffmanWaveletTree.h], and the starts of the runs in the column F, the runs of each symbol c after those of the symbols before it, in one more Elias-Fano sequence: the run k of c starts in F at :math:` C[ c ] + S_c[ k ] , :math: S_c[ k ] ` the lengths of the first k runs of c, at the place :math:` R_c + k ` of the sequence, :math:` R_c ` the runs of the symbols below c (one sequence of r items in :math:` [ 0 , n ] ` rather than one for each symbol, which would cost the entropy of the heads more per run). The rank of c in L[ 0 , i ) is then :math:`[ rank_c( i ) = F_{R_c + k} - C[ c ] + [ h_j = c ] , ( i - p_j ) ,

qquad k = rank_c( h , j ) , ` with j the run of the place i - 1, :math:` p_j ` its start and :math:` h_j ` its head (one predecessor search, one descent of the tree for both ranks of c around j), and count( P ) is the backward search of the FM-index with it.

locate( P ) keeps, along the backward search, the place in s of the suffix of the last row of the range, :math:` SA[ e - 1 ] ` (the toehold): if :math:` L[ e - 1 ] = c ` the row moves by LF and the place decreases by 1, and else the last c before e - 1 ends a run of c, whose place is kept (a sample of SA at each end of a run). The other occurrences follow from the function :math:` phi( SA[ i ] ) = SA[ i - 1 ] `, which shifts every stretch between two places of the starts of the runs alike: :math:`[ phi( x ) = phi( y ) + ( x - y ) , qquad y = max { SA[ p_j ] :

SA[ p_j ] le x } , ` so that the places :math:` SA[ p_j ] ` of the starts of the runs, sorted, in Elias-Fano, give it by one predecessor search: :math:` phi( SA[ p_j ] )

= SA[ p_j - 1 ] ` is the sample at the end of the run j - 1, and only j is kept, in :math:` lceil log_2 r rceil ` bits. All of it takes O( r ) words: 5 sequences of r integers of :math:` lceil log_2 n rceil ` bits or less and the heads, whose rank and select are those of CompactRankSelect [see File CompactRankSelect.h], the smallest.

The symbols of L are the bytes plus 1, the end of the text being 0. The transform comes from the suffix array of SA-IS [see File BurrowsWheeler.h], O( n ) time and words; the r-index of the literature is built in O( r ) words from the run-length transform, which this one does not attempt.

The contracts [see File Contract.h]: n is below :math:` 2^{32} `, a pattern is not empty; each place found by locate() is an occurrence, an audit against the text kept for it only at the level of the audits. The functions are defined in RIndex.tpp.

  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

  1. Gagie, G. Navarro, N. Prezza, Optimal-time text indexing in BWT-runs bounded space, Proc. 29th SODA, 1459-1477, 2018, doi:10.1137/1.9781611975031.96

  1. Makinen, G. Navarro, Succinct suffix arrays based on run-length encoding, Proc. 16th CPM, LNCS 3537, 45-56, 2005, doi:10.1007/11496656_5

  1. Navarro, Indexing highly repetitive string collections, part II: compressed indexes, ACM Computing Surveys 54(2), 26, 2021, doi:10.1145/3432999

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes