File RRRBitVector.h

↰ Parent directory (ADS/succinct)

The compressed vector of bits of Raman, Raman and Rao (RRR), in the practical form of Claude and Navarro: a static vector B of m bits with n 1s in at most :math:` m H_0( B ) + 0.175 m ` bits, i.e., below m when the 1s (or the 0s) are rare or clustered, with access, rank and select.

Definition (ADS/succinct/RRRBitVector.h)

Detailed Description

B is cut in blocks of b = 63 bits; a block of c 1s is written as its class c, in 6 bits, and as its offset, its place among the :math:` binom{b}{c} ` blocks of class c, in :math:` lceil log_2 binom{b}{c} rceil ` bits. The offset of the block with its 1s at the places :math:` p_1 < cdots < p_c ` is its rank in the colexicographic order, \([ o = \sum_{t=1}^{c} \binom{p_t}{t} , \` the combinatorial number system, and the block is rebuilt from o from its highest place down: the place p holds the t-th 1 from the lowest, t the 1s not yet met, if and only if :math:\) binom{p}{t} le o , which is then taken away from o. A query walks only the places it needs: rank stops at its place or at the last 1, select at its bit. Since :math: sum_j log_2 binom{b}{c_j} le log_2 binom{m}{n} le m H_0( B ) ` (the product of the binomials of the blocks counts a part of the vectors of n 1s), the offsets take at most :math:` m H_0( B ) + m / b ` bits, the rounding up costing a bit per block, and the classes :math:` 6 m / b ; a superblock of 32 blocks (2016 bits) keeps the 1s before it and the place of its first offset, :math: 128 / 2016 = 6.3 % ` of m, in all :math:` m H_0( B ) + ( 7 / 63 + 128 / 2016 ) m < m H_0( B ) + 0.175 m ` bits. Hence:

  • access( i ) and rank1( i ) sum the classes of the blocks of the superblock before the one of i, and of their offsets the lengths, and rebuild the block of i: O( 32 + b ) time;

  • select1( k ) finds the superblock by a binary search on the counts, the block by the classes, and the 1 in the rebuilt block: :math:` O( log ( m / 2016 ) + 32 + b ) ` time; select0 likewise.

The contracts [see File Contract.h]: the places and the ranks are in range as for RankSelect [see File RankSelect.h]; the audit of the construction is that the vector gives back each bit. The functions are defined in RRRBitVector.tpp.

  1. Raman, V. Raman, S. S. Rao, Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets, ACM Transactions on Algorithms 3(4), 43, 2007, doi:10.1145/1290672.1290680

  1. Claude, G. Navarro, Practical rank/select queries over arbitrary sequences, Proc. 15th SPIRE, LNCS 5280, 176-187, 2008, doi:10.1007/978-3-540-89097-3_18

  2. Navarro, E. Providel, Fast, small, simple rank/select on bitmaps, Proc. 11th SEA, LNCS 7276, 295-306, 2012, doi:10.1007/978-3-642-30850-5_26

  1. Navarro, Compact Data Structures, Cambridge University Press, 2016, section 4.1, doi:10.1017/CBO9781316588284

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes