File BitVector.h

↰ Parent directory (ADS/succinct)

The vector of bits on which the succinct structures and the integer codes of Namespace ADS are built: the bits are packed in words of 64 bits, the bit i being the bit i mod 64 (from the least significant one) of the word :math:` lfloor i / 64 rfloor `, so that a field of up to 64 bits is read or written with two shifts at most.

Definition (ADS/succinct/BitVector.h)

Detailed Description

Besides the random access to a bit, in O( 1 ) time, BitVector appends a bit or a field of len bits, push_back() and append(), in O( 1 ) amortized time, and reads a field of len bits, get(), in O( 1 ) time; the space is :math:` n + O( 512 ) ` bits for n bits, the vector of words doubling as std::vector does. The words are whole lines of the cache of 64 bytes, with one word at least past the last bit, and they start on a line (on a huge page from 2 MB on, which spares the misses of the TLB of a random access); the bits past the size are 0 (the invariant). Hence count() and the rank of a word [see File RankSelect.h] need no mask at the end, a field is read with no test of the end, and a directory may read the words of a line of its own. Unlike std::vector< bool >, whose layout is left to the implementation, BitVector exposes its words, which is what a rank directory or a code reading a word at a time needs.

selectInWord() gives the place of the k-th 1 of a word by the broadword method of Vigna: the sideways sums of the bytes [see File Bitwise.h] are accumulated by one multiplication, the byte holding the k-th 1 is found by a comparison of the 8 bytes in parallel and the trailing zeros, and the 1 inside it by clearing the lower 1s, in O( 1 ) time and with no loop over the 64 bits. It is the last step of every select in Namespace ADS, in place of the tables of the small blocks of the classical analysis (Jacobson, Clark). SubscriptIterator is the random-access constant iterator of a structure read by its operator[], the bits of a BitVector or the items of a compressed sequence [see File EliasFano.h].

The contracts [see File Contract.h]: the places and the fields are in the vector, a field has at most 64 bits and its value fits in them, and selectInWord() needs k smaller than the 1s of the word; the invariant is that the bits past the size are 0. The functions are defined in BitVector.tpp.

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

  1. Jacobson, Space-efficient static trees and graphs, Proc. 30th FOCS, 549-554, 1989, doi:10.1109/SFCS.1989.63533

  1. Vigna, Broadword implementation of rank/select queries, Proc. WEA 2008, LNCS 5038, 154-168, 2008, doi:10.1007/978-3-540-68552-4_12

  1. Gog, M. Petri, Optimized succinct data structures for massive data, Software: Practice and Experience 44(11), 1287-1314, 2014, doi:10.1002/spe.2198

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions

Typedefs