File MoveRIndex.h

↰ Parent directory (ADS/compression)

The r-index on move structures, after the move-r of Bertram, Fischer and Nalbach: the operations of the r-index [see File RIndex.h] with each step in O( 1 ) time instead of a predecessor search, from two move structures of Nishimoto and Tabei [see File MoveStructure.h], at the price of a few more words per run of the transform L of Burrows and Wheeler of the text.

Definition (ADS/compression/MoveRIndex.h)

Detailed Description

The LF-mapping shifts each run of L alike onto the column F, and is a move structure on the runs; the backward search keeps the first and the last row of the range, [ s , e ], with their intervals, and for the symbol c moves s to the first row at or after it whose symbol is c, the start of the next interval of c if its own is not of c, and e to the last one at or before it, the end of the previous interval of c (the rank and select of c on the tags of the intervals, in a wavelet tree of Huffman on RankSelect [see File HuffmanWaveletTree.h], the fastest), and then maps both by LF in O( 1 ) time each; count( P ) takes O( p ) steps and the ranks of the intervals whose tag is not c.

The function :math:` phi( SA[ i ] ) = SA[ i - 1 ] , taken cyclically ( :math: phi( SA[ 0 ] ) = SA[ n ] ), is a permutation of the places of the text that shifts each stretch between two places of the starts of the runs alike, and is a move structure too; locate( P ) keeps :math: SA[ e ] ` along the search (the toehold, from the samples of SA at the end of each interval, with the interval of :math:` phi ` of each), and then lists the occurrences by :math:` e - s ` steps of :math:` phi `, each in O( 1 ) time.

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].

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 MoveRIndex.tpp.

  1. Bertram, J. Fischer, L. Nalbach, Move-r: optimizing the r-index, Proc. 22nd SEA, LIPIcs 301, 1, 2024, doi:10.4230/LIPIcs.SEA.2024.1

  1. Nishimoto, Y. Tabei, Optimal-time queries on BWT-runs compressed indexes, Proc. 48th ICALP, LIPIcs 198, 101, 2021, doi:10.4230/LIPIcs.ICALP.2021.101

  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