File MoveStructure.h

↰ Parent directory (ADS/succinct)

The move structure of Nishimoto and Tabei: a permutation :math:` pi ` of :math:` [ 0 , n ) ` that shifts each of m intervals alike, the interval :math:` [ p_i , p_{i+1} ) ` onto :math:` [ q_i , q_i + p_{i+1} - p_i ) ` (the LF-mapping of a transform of Burrows and Wheeler on its runs, the function :math:` phi ` of the r-index on the places of the starts of the runs [see File RIndex.h]), with :math:` pi( x ) ` and the interval of :math:` pi( x ) ` in O( 1 ) time from x and its interval, in O( m ) words rather than n.

Definition (ADS/succinct/MoveStructure.h)

Detailed Description

Each interval i keeps :math:` p_i , :math: q_i ` and the interval :math:` d_i ` that holds :math:` q_i , so that :math:`[ pi( x ) = q_i + ( x - p_i ) , qquad x in [ p_i , p_{i+1} ) , ` and its interval is found from :math: d_i ` forward, past the starts :math:` p_j le pi( x ) . The structure is balanced: no image :math: [ q_i , q_i + p_{i+1} - p_i ) ` holds 4 starts or more, which the construction ensures by cutting an interval whose image holds 4 starts at the third of them, so that the first part holds 2 (the new start may weigh on another image, which is checked in turn); the intervals become at most 2m (Nishimoto and Tabei, for this balance), and the search forward takes at most 3 steps. Each interval carries a tag of its own (the symbol of its run), which its parts keep.

The contracts [see File Contract.h]: the intervals partition [ 0 , n ) and their images too, and the places and the intervals of move() agree; the audit of the construction is the balance. The functions are defined in MoveStructure.tpp.

  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. Brown, T. Gagie, M. Rossi, RLBWT tricks, Proc. 20th SEA, LIPIcs 233, 16, 2022, doi:10.4230/LIPIcs.SEA.2022.16

  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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes