Skip to content

22. Succinct structures

[Source: include/ADS/succinct/BitVector.h, BitStream.h, RankSelect.h, CompactRankSelect.h, InterleavedRankSelect.h, RRRBitVector.h, EliasFano.h, PartitionedEliasFano.h, LAVector.h, PackedArray.h, JacobsonTree.h, LoudsTree.h, BalancedParentheses.h, BPTree.h, WaveletMatrix.h, HuffmanWaveletTree.h, MoveStructure.h, EliasFanoGraph.h, BVGraph.h, K2Tree.h]

We are concerned in this chapter with the data structures that take about as many bits as the information they hold, and that answer their queries without being decoded. The headers of ADS/succinct follow chapter 15, Compressed Data Structures, of Ferragina 2023, and the representation of Elias and Fano of its chapter 11, Integer Coding; the book of Montresor does not treat them. Both operations on which all of them are built, the rank and the select of a vector of bits, are defined in §22.1 together with the lower bounds against which the space is measured. We then give the vector of bits and the streams of bits (§22.2), the directories of rank and select, from the fastest to the smallest (§22.3 and §22.4), and the vector compressed to its entropy (§22.5). On them we build, in turn, the sequences of integers searched in place (§22.6), the arrays of small fields (§22.7), the trees (§22.8), the sequences of symbols and the permutations (§22.9) and the graphs (§22.10). Finally, §22.11 describes how the directories and the wavelet structures are built on several threads. In the sets of §1.9, CompactRankSelect.h, InterleavedRankSelect.h, LAVector.h, MoveStructure.h, PackedArray.h, PartitionedEliasFano.h, RRRBitVector.h and WaveletMatrix.h are advanced and the other headers of this chapter are base.

Some members are common to the classes of the chapter, and we describe them once here. All the static sequences (BitVector, the directories of RankSelect.h and CompactRankSelect.h, EliasFano, PartitionedEliasFano, LAVector and WaveletMatrix) are random-access ranges with the aliases of the standard containers (value_type, size_type, difference_type, reference, const_reference, const_iterator and iterator, the same), whose iterators read the items by subscript (SubscriptIterator of BitVector.h), from begin() and cbegin() to end() and cend(). Each structure gives its space in bits by sizeInBits(); besides, the directories give their bits beyond those of the vector by directoryBits(), EliasFano and BVGraph the bits of their codes alone by codeBits(), BalancedParentheses the bits of its range min-max tree by treeBits(), and LAVector the bits of its corrections by correctionsInBits() (and their width by correctionBits()). Finally, the trees mark a missing node (or place) by the constant nil.

22.1 Rank, select and the lower bounds

A vector of bits \(B[ 0 , m )\) with \(n\) 1s has, for \(b \in \{ 0 , 1 \}\), the operations

\[ \mathrm{rank}_b( i ) = | \{ j < i : B[ j ] = b \} | , \qquad \mathrm{select}_b( k ) = \min \{ i : \mathrm{rank}_b( i + 1 ) = k \} , \tag{22.1} \]

i.e., the number of the bits \(b\) before the place \(i\) (cf. (22.1)), and the place of the \(k\)-th bit \(b\), with \(1 \le k\) up to the number of the bits \(b\). Hence \(\mathrm{rank}_b( \mathrm{select}_b( k ) ) = k - 1\), and \(\mathrm{rank}_0( i ) = i - \mathrm{rank}_1( i )\). We count the places from 0, as the library does, while Ferragina's book counts them from 1; its \(\mathrm{Rank}_1\) and \(\mathrm{Select}_1\) are therefore our \(\mathrm{rank}_1\) and \(\mathrm{select}_1\) with the places shifted by one. We regard the two operations as the primitives of the area: a structure that codes its objects as bits uses the select to go from the number of an object to its place in the bits, and the rank to go back.

A representation of the objects of a class of \(N\) elements needs \(Z = \lceil \log_2 N \rceil\) bits for some of them, the information-theoretic lower bound. We call it succinct if it takes \(Z + o( Z )\) bits, and compact if it takes \(O( Z )\) bits. In both cases it should answer its queries in about the time of the plain representation (possibly up to a constant). Three bounds recur in the chapter. The vectors of \(m\) bits with \(n\) 1s are \(\binom{m}{n}\). Similarly, the sets of \(n\) integers of \([ 0 , u )\) are \(\binom{u}{n}\), i.e., about \(n \log_2( u / n ) + n \log_2 e\) bits when \(n\) is much smaller than \(u\). Finally, the ordered trees of \(n\) nodes (and the binary trees of \(n\) nodes) are the Catalan number \(C_n = \binom{2 n}{n} / ( n + 1 ) \approx 4^n / ( n^{3/2} \sqrt{\pi} )\), i.e., \(2 n - \Theta( \log n )\) bits.

Lemma 22.1. With \(H_0( B ) = \frac{n}{m} \log_2 \frac{m}{n} + \frac{m - n}{m} \log_2 \frac{m}{m - n}\), the empirical entropy of a vector of \(m\) bits with \(n\) 1s,

\[ \log_2 \binom{m}{n} \le m H_0( B ) . \tag{22.2} \]

Proof. With \(p = n / m\), one has \(\binom{m}{n} p^n ( 1 - p )^{m - n} \le \sum_k \binom{m}{k} p^k ( 1 - p )^{m - k} = 1\), and the logarithm of \(p^{-n} ( 1 - p )^{-( m - n )}\) is \(m H_0( B )\). \(\square\)

Table 22.1 collects the notation of the area. We analyze the costs in the model of the word RAM with words of \(\Theta( \log m )\) bits, in which the sideways sum of a word (the number of its 1s, \(\lvert x \rvert\) or \(\mathrm{popcount}( x )\)) and the place of its \(k\)-th 1 cost \(O( 1 )\) time. Indeed, the first is one instruction of today's processors, and the second a few broadword operations (§22.2).

Table 22.1. The notation of the chapter.

Symbol Meaning
\(B\), \(m\), \(n\) a vector of bits, its length and the number of its 1s
\(\mathrm{rank}_b( i )\), \(\mathrm{select}_b( k )\) as in (22.1); rank1(), select1(), rank0(), select0() in the code
\(H_0\) the empirical entropy of order 0 of a vector of bits, or of a sequence of symbols of frequencies \(f_c\), \(\sum_c ( f_c / n ) \log_2( n / f_c )\)
\(x_0 , \ldots , x_{n-1}\), \(u\) a non-decreasing sequence of integers, and the bound of its items
\(\ell\), \(L\), \(H\) the low bits of an item of Elias-Fano, and the vectors of the low and of the high parts
\(\sigma\), \(w\) the size of an alphabet of symbols, and the bits of a symbol of a wavelet matrix
\(E( i )\) the excess of a sequence of parentheses, the open ones less the closed ones in \(B[ 0 , i ]\)
\(\lvert x \rvert\), \(\mathrm{popcount}( x )\) the number of the 1s of a word

22.2 Vectors of bits and streams

BitVector packs the bits in words of 64 bits, the bit \(i\) in the bit \(i \bmod 64\) (from the least significant one) of the word \(\lfloor i / 64 \rfloor\) (Figure 22.1). Besides the access to a bit in \(O( 1 )\) time, the class appends a bit or a field of up to 64 bits (push_back() and append()) in \(O( 1 )\) amortized time, and it reads a field of up to 64 bits (get()) in \(O( 1 )\) time with two shifts at most (Algorithm 22.1). Its words fill lines of the cache of 64 bytes, with at least one word past the last bit. They start on a line (on a huge page from 2 MB on, which may spare the misses of the TLB of a random access), and the space is therefore \(m + O( 512 )\) bits for \(m\) bits. We keep the bits past the size at 0, which is the invariant of the class. For this reason a field is read with no test of the end, and the rank of a word needs no mask at the end of the vector. Unlike std::vector< bool >, whose layout is left to the implementation, BitVector exposes its words, which a directory of rank or a code read a word at a time needs. Its words are a Words, a vector on the allocator of the lines; copyBits() ors a run of bits of a word array into another from any place, reserve( n ) makes room for \(n\) bits and toString() writes the bits as '0' and '1', the bit 0 first.

Figure 22.1. Three words of a BitVector of \(n = 100\) bits, each word with its bit 0 on the right: the field read by get( 58 , 13 ) crosses from the word 0 to the word 1, and the bits past the size are 0 (the word 2 is there although no bit of the vector is in it). Below, a stream that holds \(\gamma( 9 ) \gamma( 3 )\), read from the place \(p\).

Algorithm 22.1. The append and the read of a field of BitVector; \(W\) are the words.

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{append}( v , \mathit{len} ) \cr 2 & \quad w \gets \lfloor n / 64 \rfloor;\ o \gets n \bmod 64 \cr 3 & \quad W[ w ] \gets W[ w ] \vee ( v \ll o )\quad \triangleright \ \text{the bits past } n \text{ are } 0 \cr 4 & \quad \textbf{if}\ o + \mathit{len} > 64\ \textbf{then}\ W[ w + 1 ] \gets v \gg ( 64 - o ) \cr 5 & \quad n \gets n + \mathit{len} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{get}( i , \mathit{len} ) \cr 2 & \quad w \gets \lfloor i / 64 \rfloor;\ o \gets i \bmod 64 \cr 3 & \quad r \gets ( W[ w ] \gg o ) \vee ( ( W[ w + 1 ] \ll 1 ) \ll ( 63 - o ) ) \cr 4 & \quad \textbf{return}\ r \bmod 2^{\mathit{len}} \end{array} \]

Finding the place of the \(k\)-th 1 of a word, by selectInWord(), is the last step of each select of the library, in place of the tables of the small blocks of the classical analysis (Jacobson 1989; Clark 1996). It is the broadword method of Vigna 2008 (Algorithm 22.2), with \(L_8 = \sum_{j < 8} 2^{8 j}\) and \(H_8 = 2^7 L_8\).

Algorithm 22.2. The broadword select in a word (Vigna 2008).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{selectInWord}( x , k ) \cr 2 & \quad s \gets \text{the sideways sums of the bytes of } x \cr 3 & \quad s \gets s \cdot L_8\quad \triangleright\ \text{the byte } j \text{ of } s \text{ counts the 1s of the bytes } 0 , \ldots , j \cr 4 & \quad b \gets \lfloor \mathrm{ctz}( ( s + ( 127 - k ) L_8 ) \wedge H_8 ) / 8 \rfloor\quad \triangleright\ \text{the first byte past } k \cr 5 & \quad r \gets k - \text{the byte } b - 1 \text{ of } s \ \text{(0 if } b = 0 \text{)} \cr 6 & \quad v \gets \text{the byte } b \text{ of } x \cr 7 & \quad \textbf{return}\ 8 b + T[ 8 v + r ]\quad \triangleright \ T \text{ the places of the 1s of each byte by rank} \end{array} \]

Lemma 22.2. Let \(s_j\) be the number of the 1s of the bytes \(0 , \ldots , j\) of \(x\), and \(k < \lvert x \rvert\). The byte \(j\) of \(s + ( 127 - k ) L_8\) has its high bit if and only if \(s_j > k\), and the first such byte holds the \(k\)-th 1 of \(x\), counting from 0.

Proof. Since the sideways sums of the 8 bytes are at most 8, one product by \(L_8\) puts their prefix sums \(s_j \le 64\) in the bytes, and no byte overflows, since \(s_j < 256\). Adding \(127 - k\) to the byte \(j\) gives at most \(64 + 127 < 256\), and therefore no carry crosses into the next byte; the sum is at least 128, i.e., it has its high bit, if and only if \(s_j \ge k + 1\). Hence the first byte \(b\) with \(s_b > k\) is the one that holds the 1 of rank \(k\), which is the \(( k - s_{b-1} )\)-th 1 of the byte. \(\square\)

In the implementation, the trailing zeros of the masked word give \(b\), and the 1 inside the byte is read in a table of \(256 \cdot 8\) bytes, indexed by the byte and by the rank in it, as in Vigna 2008. The select has thus neither a loop nor an instruction of a particular processor, while the deposit of the bit \(2^k\) on the 1s of the word (the instruction pdep of BMI2) would need a branch on the processor.

We write the codes of the integers of §21.7 on the streams of bits of BitStream.h. A BitWriter appends bits to a BitVector, and a BitReader reads them back from a place that moves forward, both in \(O( 1 )\) time per field of up to 64 bits (Algorithm 22.3). The functions write() and read() move a field with its least significant bit first, the order of the words. The functions writeBinary() and readBinary() move it with its most significant bit first, the order in which the codes are written on paper, and they turn the field around by three rounds of masks and a swap of the bytes. Also, writeUnary( q ) writes \(q\) zeros and a 1, and readUnary() counts the zeros up to the 1 a word at a time, by the trailing zeros of the word, in \(O( 1 + q / 64 )\) time. A single bit is moved by writeBit() and readBit(); seek( p ) moves the reader to the place \(p\), atEnd() is true when all the bits have been read, and release() hands the bits written over to the caller, leaving the writer empty. In the literature the fast decoders write the codes into words rather than bytes, e.g., the streams of the WebGraph framework of Boldi and Vigna 2004. Indeed, a codeword of up to 64 bits spans at most two words, and the unary part is decoded by one instruction per word.

Algorithm 22.3. The binary and the unary fields of the streams of bits.

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{writeBinary}( v , \mathit{len} ) \cr 2 & \quad r \gets \text{the } \mathit{len} \text{ low bits of } v \text{ in the reverse order} \cr 3 & \quad \mathrm{write}( r , \mathit{len} ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{writeUnary}( q ) \cr 2 & \quad \textbf{while}\ q \ge 64\ \textbf{do}\ \mathrm{write}( 0 , 64 );\ q \gets q - 64 \cr 3 & \quad \mathrm{write}( 2^q , q + 1 )\quad \triangleright\ q \ \text{zeros, then a 1} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{readUnary}() \cr 2 & \quad q \gets 0 \cr 3 & \quad \textbf{loop} \cr 4 & \qquad \mathit{len} \gets \min\{ 64 , \text{the bits left} \}; \ w \gets \mathrm{get}( p , \mathit{len} ) \cr 5 & \qquad \textbf{if}\ w \ne 0\ \textbf{then} \cr 6 & \qquad\quad z \gets \mathrm{ctz}( w );\ p \gets p + z + 1; \ \textbf{return}\ q + z \cr 7 & \qquad q \gets q + \mathit{len};\ p \gets p + \mathit{len} \end{array} \]

Lemma 22.3. (i) A BitVector of \(m\) bits keeps at most \(\lfloor m / 64 \rfloor + 10\) words, i.e., \(m + O( 512 )\) bits, with at least one word past the last bit and the bits past the size at 0. (ii) get( i , len ), \(len \le 64\), reads at most two words, and push_back() and append() take \(O( 1 )\) amortized time. (iii) readUnary() reads \(q\) zeros and the 1 in at most \(\lfloor q / 64 \rfloor + 1\) steps of one word each.

Proof. (i) The constructor of \(m\) bits takes \(\lceil ( \lfloor m / 64 \rfloor + 9 ) / 8 \rceil 8 \le \lfloor m / 64 \rfloor + 9\) words, rounded down to a multiple of 8, i.e., at least \(\lfloor m / 64 \rfloor + 2\); an append grows the words by 8 only when fewer than \(\lfloor m' / 64 \rfloor + 2\) are there for the new size \(m'\), which keeps the count below \(\lfloor m' / 64 \rfloor + 10\). The constructor writes 0s past the size, and an append writes only the bits of its field, whose value has no 1 above its length (a precondition). (ii) A field of at most 64 bits from the place \(i\) lies in the words \(\lfloor i / 64 \rfloor\) and the next one. An append writes at most two words, and the growth of the words by 8 at a time reallocates them geometrically (the growth of std::vector beyond its capacity), which is \(O( 1 )\) amortized per append. (iii) Each step reads up to 64 bits from the current place: if they are all 0 it counts them and moves past them, and otherwise the trailing zeros of the word give the 1. All the steps but the last read 64 zeros each (or the last bits of the vector, after which the precondition stops the reader). \(\square\)

22.3 Rank and select

One can reduce the rank to a few counts by the two-level directory of Jacobson.

Lemma 22.4 (the directory of Jacobson). With superblocks of \(Z\) bits, each with the 1s before it in \(\log_2 m\) bits, and blocks of \(z\) bits, each with the 1s before it since its superblock in \(\log_2 Z\) bits,

\[ \mathrm{rank}_1( i ) = R_S[ \lfloor i / Z \rfloor ] + R_b[ \lfloor i / z \rfloor ] + \mathrm{rank}_1 \text{ of } B[ z \lfloor i / z \rfloor , i ) , \tag{22.3} \]

and with \(Z = \log_2^2 m\) and \(z = \log_2 m / 2\) the counts take \(o( m )\) bits, with the rank in \(O( 1 )\) time.

Proof. The places before \(i\) are split into those before its superblock, those of its superblock before its block, and those of its block before \(i\); counting the 1s of each part gives the three terms of (22.3). Also, the superblocks take \(( m / \log_2^2 m ) \log_2 m = m / \log_2 m\) bits, and the blocks \(( 2 m / \log_2 m ) \log_2 \log_2^2 m = O( m \log \log m / \log m )\), both \(o( m )\). Finally, the last term of (22.3) is read in a table of the \(2^z = \sqrt{m}\) blocks of \(z\) bits and of their \(z\) prefixes, of \(O( \sqrt{m} \log m \log \log m )\) bits. \(\square\)

In the library we replace the table by the sideways sum of a word, one instruction of the processor, which lets \(z\) be a word and \(Z\) a constant. RankSelect (chapter 15 of Ferragina 2023) keeps one word for each block of 256 bits: the 1s before the block in its 40 high bits, and those before its words 1, 2 and 3, relative to the block, in 8 bits each (Figure 22.2). Hence one can compute (22.3) by one read of the directory and one of the bits, with no branch, at the price of \(64 / 256 = 25\%\) of space more instead of \(o( m )\) (Algorithm 22.4). This fraction is constant, but it is "small" at the practical sizes, since \(m / \log_2 m\) is still 2.5% of \(m\) for \(m = 2^{40}\), a "large" vector. Above \(2^{40}\) bits, a third level counts the 1s before each \(2^{40}\) bits in 64 bits.

Figure 22.2. The directory of RankSelect. Above, a block of 256 bits and its entry \(D[ t ]\), with the 1s before the block and the relative ranks 13, 53 and 60 of its words 1, 2 and 3 (the sideways sums of the words being 13, 40, 7 and 22): the rank of a place \(i\) in the word 2 adds 53 and the 1s of the word before \(i\) (violet). Below, a group of the inventory of select, its first place \(P[ j ]\) and the offsets of its 1s of rank multiple of \(2^g\).

Algorithm 22.4. The directory of RankSelect and its rank, with the blocks of 256 bits.

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{directory}( W ) \cr 2 & \quad c \gets 0 \cr 3 & \quad \textbf{foreach}\ \text{block } t \text{ of four words} \ W[ 4 t .. 4 t + 3 ]\ \textbf{do} \cr 4 & \qquad p_j \gets \mathrm{popcount}( W[ 4 t + j ] )\ \text{for } j = 0 , 1 , 2 , 3 \cr 5 & \qquad r \gets ( p_0 + 2^8 p_1 + 2^{16} p_2 ) \cdot ( 1 + 2^8 + 2^{16} ) \bmod 2^{24}\quad \triangleright\ \text{the relative ranks} \cr 6 & \qquad D[ t ] \gets 2^{24} c + r;\ c \gets c + p_0 + p_1 + p_2 + p_3 \cr 7 & \quad \textbf{foreach}\ \text{value } b \text{ of the selects } s \ \textbf{do}\ \text{build the inventory of } b \text{ (if not } \mathit{Lazy} \text{)} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{rank1}( i ) \cr 2 & \quad e \gets D[ \lfloor i / 256 \rfloor ];\ q \gets \lfloor i / 64 \rfloor \bmod 4 \cr 3 & \quad r \gets \lfloor e / 2^{24} \rfloor + \text{the count of the } \text{word } q \text{ in } e\ \text{(0 for } q = 0 \text{)} \cr 4 & \quad \textbf{if}\ m > 2^{40}\ \textbf{then}\ r \gets r + T[ \lfloor i / 2^{40} \rfloor ] \cr 5 & \quad \textbf{return}\ r + \mathrm{popcount}( W[ \lfloor i / 64 \rfloor ] \bmod 2^{i \bmod 64} ) \end{array} \]

We build the directory in one pass on the words. Here the sideways sums \(p_0 , \ldots , p_3\) of the words of a block, at most 64 each, are put in the bytes of a word, and one product gives their prefix sums in the bytes, which do not overflow,

\[ ( p_0 + 2^8 p_1 + 2^{16} p_2 ) \cdot ( 1 + 2^8 + 2^{16} ) \bmod 2^{24} = p_0 + 2^8 ( p_0 + p_1 ) + 2^{16} ( p_0 + p_1 + p_2 ) , \tag{22.4} \]

i.e., the three relative ranks of the entry. When the bits come from words in memory above \(2^{23}\) bits, the words are copied in the same pass, since reading them twice costs more than a copy in the caches. The implementation follows the pseudocode. Note that the 1s of the word up to \(i\) need no test of the end, since the words exist past the size.

We do not reduce the select to the rank by a binary search, which would cost \(O( \log m )\) steps. Clark 1996 cuts the 1s in groups of \(\log_2^2 m\) and writes down the places of all the 1s of a group that spans more than \(\log_2^4 m\) bits; these take \(O( m / \log m )\) bits in all, since such groups are at most \(m / \log_2^4 m\). All the other groups are cut again, and the last level is solved by a table. This gives \(O( 1 )\) time in \(o( m )\) bits, at the price of three levels whose constants are rather large at the sizes of the practice. We follow instead the inventories of the simple select of Vigna 2008, with groups of constant size, for the 1s and for the 0s. We cut the 1s in groups of \(2^\ell\), with \(\ell = \lfloor \log_2( 1.5 \cdot 4096 \, k / m ) \rfloor\) for \(k\) of them, and a group thus spans between 3072 and 6144 bits on average. For each group the place of its first 1 is kept in 64 bits, and the places of its 1s of rank multiple of \(2^g\), \(g = \max\{ \ell - 5 , 0 \}\), in 16 bits from it, i.e., at most 32 offsets, a line of the cache. Hence \(\mathrm{select}_1( k )\) reads the place of the 1 of rank \(k - 1\) rounded down to a multiple of \(2^g\). It counts the rest of the 1s word by word, by the sideways sums, and it ends in the word by selectInWord() (Algorithm 22.5).

Algorithm 22.5. The select of RankSelect by the inventories of Vigna 2008.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{select}( k ) \cr 2 & \quad r \gets k - 1;\ j \gets \lfloor r / 2^\ell \rfloor \cr 3 & \quad \textbf{if}\ \text{the group } j \text{ is sparse } \ \textbf{then} \cr 4 & \qquad \textbf{return}\ \text{the place by a binary search of the } \text{blocks of } D \text{ between } P[ j ] \text{ and } P[ j + 1 ] \cr 5 & \quad p \gets P[ j ] + O[ \lfloor r / 2^g \rfloor ]\quad \triangleright\ \text{the 1 of rank } 2^g \lfloor r / 2^g \rfloor \cr 6 & \quad \textbf{if}\ g = 0\ \textbf{then return}\ p \cr 7 & \quad t \gets r \bmod 2^g;\ w \gets \lfloor p / 64 \rfloor;\ x \gets W[ w ] \text{ with the bits before } p \text{ cleared} \cr 8 & \quad \textbf{while}\ t \ge \mathrm{popcount}( x )\ \textbf{do} \ t \gets t - \mathrm{popcount}( x );\ w \gets w + 1;\ x \gets W[ w ] \cr 9 & \quad \textbf{return}\ 64 w + \mathrm{selectInWord}( x , t ) \end{array} \]

Lemma 22.5. (i) The entries of Algorithm 22.4 hold the 1s before each block and the relative ranks of its words 1 to 3 without overflow, (22.4) gives the latter, and rank1( i ) is their sum plus the 1s of the word of \(i\) before \(i\). (ii) For \(1 \le k \le n\), Algorithm 22.5 returns \(\mathrm{select}_1( k )\); in a group that is not sparse it reads fewer than \(2^{16} / 64 + 1\) words of the vector, and in a sparse one it makes \(O( \log( m / 256 ) )\) steps. (iii) The directory of rank takes 64 bits per 256 bits of the vector, and the inventory of the 1s 64 bits per group and at most 32 offsets of 16 bits.

Proof. (i) The relative ranks are at most \(3 \cdot 64 = 192\), which fit in 8 bits; in (22.4) each partial sum is at most 192, so that no byte carries into the next one, and the product modulo \(2^{24}\) leaves in the byte \(j\) the sum \(p_0 + \cdots + p_j\). The rank of \(i\) in the word \(q\) of its block is then the 1s before the block, plus the relative rank of \(q\) (0 for \(q = 0\)), plus the 1s of the word \(q\) before \(i\), which is (22.3) with the word as the last block. (ii) The 1 of rank \(r = k - 1\) (from 0) is in the group \(j = \lfloor r / 2^\ell \rfloor\). If the group is sparse, its 1 is found by a binary search on the counts of the directory between the places of the first 1s of the groups \(j\) and \(j + 1\), over at most \(m / 256\) blocks. Otherwise line 5 gives the place \(p\) of the 1 of rank \(2^g \lfloor r / 2^g \rfloor \le r\), which is \(r\) itself for \(g = 0\). The 1 of rank \(r\) is the \(t\)-th 1, from 0, at or after \(p\), with \(t = r \bmod 2^g\), and the loop of line 8 skips the words that hold fewer than \(t + 1\) of the 1s still to pass, until selectInWord() finds it (Lemma 22.2). The 1s from \(p\) to the 1 of rank \(r\) lie in the group, which spans fewer than \(2^{16}\) bits since it is not sparse; hence the loop reads fewer than \(2^{16} / 64 + 1\) words. (iii) A group of \(2^\ell\) 1s keeps its first place in 64 bits and the offsets of its 1s of rank multiple of \(2^g\), at most \(2^{\ell - g} \le 32\) of them, in 16 bits each. \(\square\)

On bits spread evenly, a group spans between 3072 and 6144 bits on average by the choice of \(\ell\), and the scan of line 8 then covers a few words; this, and not (ii), is the case for which the inventories are designed.

A select is thus (typically) three accesses to the memory and a few words, \(O( 1 )\) time where the 1s are spread evenly, with about \(576 / 6144\) to \(576 / 3072\), i.e., 9.4% to 18.8%, of \(m\) bits more for each value. A group that spans \(2^{16}\) bits or more (quite a "sparse" one) has offsets that do not fit in 16 bits; it is sparse, and its 1s are found by a binary search on the directory of rank between its ends, \(O( \log( m / 256 ) )\) time in the worst case. A group that spans less is scanned over fewer than \(2^{16} / 64 = 1024\) words, and usually over a few, as long as the bits are not "clustered". Also, a group of fewer than 32 bits \(b\) (below about 1% of them) keeps the place of each one, and its select reads no bit at all. These are the trade-offs of the practical designs: we find them in the rank9 and the inventories of Vigna 2008, in the darray of Okanohara and Sadakane 2007, and in the structures of Gog and Petri 2014.

We build the inventories of select in the constructor (RankSelect, the default), or at the first select of each value (LazyRankSelect), in a pass on the directory. A structure that only ranks then never pays for them; also, a RankSelectOptions::Selects asks for the selects of the 1s, of the 0s, of both or of neither. Note that the first call builds an inventory once, whichever thread calls it, with std::call_once and a flag read with acquire semantics before it, and a copy keeps the inventories already built. We remark that the lazy form may cost the select 10 to 15%, since the load of the flag with acquire semantics makes the compiler read the fields of the inventory again at each query, whereas the eager form (the template parameter Lazy false) keeps them in plain fields.

22.4 Compact and interleaved directories

RankSelect spends about 50% of \(m\) bits (with both selects) for the fastest queries. CompactRankSelect is its compact counterpart, the flat directory of Kurpicz 2022, after the poppy of Zhou, Andersen and Kaminsky 2013, in about 3.5% of \(m\) bits. It cuts the bits in superblocks of 4096 bits, each one in 8 blocks of 512 bits, a line of the cache. One entry of 128 bits per superblock holds the 1s before it since its top region of \(2^{32}\) bits, in 32 bits, and the 1s before each of its blocks since the superblock, \(c_0 = 0 , c_1 , \ldots , c_7 \le 3584\), in 12 bits each; a count of 64 bits per top region completes the rank (Figure 22.3). Hence

\[ \mathrm{rank}_1( i ) = T[ \lfloor i / 2^{32} \rfloor ] + S[ \lfloor i / 4096 \rfloor ] + c_{\lfloor i / 512 \rfloor \bmod 8} + \sum_{j < 8} \big\lvert w_j \wedge ( 2^{\min( 64 , \max( 0 , o - 64 j ) )} - 1 ) \big\rvert , \tag{22.5} \]

with \(o = i \bmod 512\) and \(w_j\) the words of the block: one access to the entries, one to the line of the block, and the sideways sums of its 8 words cut at \(i\), with no branch (Algorithm 22.6). With Highway, we cut the 8 words of the line at \(i\) and count them a vector at a time, the masks of the words made from the lanes of \(\mathrm{clamp}( i - 64 j , 0 , 64 )\), by the count of the lanes of Highway (Mula, Kurz and Lemire 2018). We compute the sum on the line by one kernel of BitVector.h, detail::lineRank(), whose variants (the one on Highway, and the scalar one with or without BMI2) are chosen by ADS_WITH_HIGHWAY and by the target, and which InterleavedRankSelect below calls on the lines that hold its counts. In all, the entries take \(128 / 4096 = 3.125\%\) of \(m\) bits.

Figure 22.3. (a) A superblock of CompactRankSelect, its 8 blocks of 512 bits and its entry of 128 bits: the rank of a place \(i\) in the block 5 adds the count \(S\) of the superblock, \(c_5\) and the 1s of the line before \(i\) (violet). (b) A line of InterleavedRankSelect, its count \(h_\ell\) of 16 bits in front of its 496 bits.

Algorithm 22.6. The rank and the select of CompactRankSelect (Kurpicz 2022).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{rank1}( i ) \cr 2 & \quad r \gets T[ \lfloor i / 2^{32} \rfloor ] + S[ \lfloor i / 4096 \rfloor ] + c_{\lfloor i / 512 \rfloor \bmod 8} \cr 3 & \quad o \gets i \bmod 512 \cr 4 & \quad \textbf{for}\ j \gets 0\ \textbf{to}\ 7\ \textbf{do}\quad \triangleright\ \text{with no branch} \cr 5 & \qquad r \gets r + \mathrm{popcount}( w_j \bmod 2^{\min( 64 , \max( 0 , o - 64 j ) )} ) \cr 6 & \quad \textbf{return}\ r \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{select}( k ) \cr 2 & \quad j \gets \lfloor ( k - 1 ) / 4096 \rfloor \cr 3 & \quad s \gets \text{the last superblock in } [ Z[ j ] , Z[ j + 1 ] ] \text{ with } \mathrm{before}( s ) < k\text{, by a binary search} \cr 4 & \quad r \gets k - \mathrm{before}( s ) \cr 5 & \quad q \gets \text{the last block } h \text{ of } s \text{ with } c_h < r;\ r \gets r - c_q \cr 6 & \quad p \gets \text{the last word } h \text{ of the block with } \sum_{h' < h} \mathrm{popcount}( w_{h'} ) < r \cr 7 & \quad r \gets r - \sum_{h' < p} \mathrm{popcount}( w_{h'} ) \cr 8 & \quad \textbf{return}\ \text{the place of } w_p + \mathrm{selectInWord}( w_p , r - 1 ) \end{array} \]

Its select keeps the superblock of each 4096-th bit \(b\), in 32 bits each, i.e., at most \(32 / 4096 < 0.8\%\) of \(m\) bits for each value. It finds the \(k\)-th bit \(b\) by a binary search on the entries between two samples. Then it finds the block by the 7 counts of the superblock, and the word by the sums of the 8 words of its line, both by comparisons with no branch; the bit is found by selectInWord(). This is \(O( \log( m / 4096 ) )\) steps in the worst case, and \(O( 1 )\) where the bits \(b\) are spread "evenly" (a sample each 2 to 8 superblocks for a density between 1/2 and 1/8). Its trade with RankSelect is, roughly, the "classical" one of the literature: a sum of up to 8 words and a search of the entries instead of one word and an inventory, in 15 times fewer bits.

InterleavedRankSelect takes the layout of SPIDER of Laws et al. 2024, with the counts inside the lines of the bits. A line of 512 bits holds 496 bits of \(B\). In its first 16 bits it holds the 1s before it since its superblock of 128 lines (63488 bits, so that the count fits in 16 bits); a superblock keeps the 1s before it in 64 bits apart. Hence

\[ \mathrm{rank}_1( i ) = S[ \lfloor \ell / 128 \rfloor ] + h_\ell + \lvert B_\ell[ 0 , i \bmod 496 ) \rvert , \qquad \ell = \lfloor i / 496 \rfloor , \tag{22.6} \]

with one access to the memory of the vector, the line, against the two of the directories kept apart. Its array of the superblocks, one word per 63488 bits, typically stays in the caches, and the counts take \(16 / 512 = 3.125\%\) of the line. Its select keeps the line of each 8192-th bit \(b\) with the bits \(b\) before that line, in 96 bits, i.e., at most \(96 / 8192 < 1.2\%\) of \(m\) bits for each value. As SPIDER does, it guesses the line of the \(k\)-th bit \(b\) between two samples \(( \ell_j , c_j )\) by interpolation,

\[ \hat\ell = \ell_j + \frac{( k - 1 - c_j ) ( \ell_{j+1} - \ell_j )} {c_{j+1} - c_j} , \tag{22.7} \]

and then corrects the guess a line at a time by the counts of the lines (hopefully a step or two where the bits \(b\) are spread evenly, but \(\ell_{j+1} - \ell_j\) in the worst case). It ends in the line by the sums of its words and selectInWord() (Algorithm 22.7).

Algorithm 22.7. The rank and the select of InterleavedRankSelect (Laws et al. 2024).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{rank1}( i ) \cr 2 & \quad \ell \gets \lfloor i / 496 \rfloor \cr 3 & \quad \textbf{return}\ S[ \lfloor \ell / 128 \rfloor ] + h_\ell + \text{the 1s of } L_\ell \text{ in its bits } [ 16 , 16 + i \bmod 496 ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{select}( k ) \cr 2 & \quad j \gets \lfloor ( k - 1 ) / 8192 \rfloor \cr 3 & \quad \ell \gets \min\{ \ell_{j+1} , \ell_j + \lfloor ( k - 1 - c_j ) ( \ell_{j+1} - \ell_j ) / ( c_{j+1} - c_j ) \rfloor \} \cr 4 & \quad \textbf{while}\ \ell > \ell_j\ \textbf{and}\ \mathrm{before}( \ell ) \ge k\ \textbf{do}\ \ell \gets \ell - 1 \cr 5 & \quad \textbf{while}\ \ell < \ell_{j+1}\ \textbf{and} \ \mathrm{before}( \ell + 1 ) < k\ \textbf{do}\ \ell \gets \ell + 1 \cr 6 & \quad r \gets k - \mathrm{before}( \ell ) \cr 7 & \quad \textbf{foreach}\ \text{word } x \text{ of } L_\ell \text{,} \text{ its count cleared}\ \textbf{do} \cr 8 & \qquad \textbf{if}\ r \le \mathrm{popcount}( x ) \ \textbf{then return}\ \text{the place of } x + \mathrm{selectInWord}( x , r - 1 ) \cr 9 & \qquad r \gets r - \mathrm{popcount}( x ) \end{array} \]

Lemma 22.6. (22.5) and (22.6) give \(\mathrm{rank}_1( i )\), and their counts fit in the fields that hold them; the entries of CompactRankSelect take \(128 / 4096\) of the bits and the counts of InterleavedRankSelect \(16 / 512\) of each line.

Proof. In (22.5), the places before \(i\) are split into four parts. They are those before its top region of \(2^{32}\) bits, those of the region before its superblock, those of the superblock before its block, and those of the block before \(i\); the last term counts the 1s of the words \(j\) of the block whose bits \(64 j , \ldots\) precede \(o\), all of them when \(o \ge 64 ( j + 1 )\) and none when \(o \le 64 j\). The count of a superblock is below \(2^{32}\), and \(c_j \le 7 \cdot 512 = 3584 < 2^{12}\). In (22.6) the places before \(i\) are those before its superblock of 128 lines, those of the lines of the superblock before the line \(\ell\), and those of the line before \(i\); the count \(h_\ell\) is at most \(127 \cdot 496 = 62992 < 2^{16}\). A superblock of 4096 bits has one entry of 128 bits, and a line of 512 bits gives 16 of them to its count. \(\square\)

Table 22.2 summarizes the four vectors of bits with rank and select. In our experience RankSelect is usually preferable when the queries dominate, since its rank typically reads one entry and one word; CompactRankSelect and InterleavedRankSelect cost about seven times fewer bits and a sum of up to 8 words per rank, the second with one miss of the cache instead of two. RRRBitVector (§22.5) is perhaps the one to choose when the 1s (or the 0s) are "rare", since its space follows (22.2) instead of \(m\), at the price of the decoding of a block at each query. Their measured speeds belong to the campaign of Appendix B.

Table 22.2. The vectors of bits with rank and select, for \(m\) bits.

Realization Space beyond \(m\) rank1( i ) select1( k )
RankSelect, LazyRankSelect 25% for the rank, 9.4% to 18.8% for the select of each value \(O( 1 )\), one entry and one word \(O( 1 )\) when the bits are spread evenly, \(O( \log( m / 256 ) )\) in a sparse group
CompactRankSelect 3.125%, and less than 0.8% for the select of each value \(O( 1 )\), one entry and the 8 words of a line \(O( 1 )\) when the bits are spread evenly, \(O( \log( m / 4096 ) )\) in the worst case
InterleavedRankSelect 3.125% inside the lines, and less than 1.2% for the select of each value \(O( 1 )\), one line \(O( 1 )\) when the bits are spread evenly, the lines between two samples in the worst case
RRRBitVector the whole vector in \(m H_0( B ) + 0.175 m\) bits \(O( 32 + b )\), blocks of \(b = 63\) bits \(O( \log( m / 2016 ) + 32 + b )\)

22.5 Compressed vectors of bits

RRRBitVector is the compressed vector of Raman, Raman and Rao 2007 in the practical form of Claude and Navarro 2008. It cuts \(B\) in blocks of \(b = 63\) bits, and writes a block of \(c\) 1s as its class \(c\), in 6 bits, and as its offset, its place among the \(\binom{b}{c}\) blocks of class \(c\), in \(\lceil \log_2 \binom{b}{c} \rceil\) bits. We compute the offset by the combinatorial number system.

Lemma 22.7 (the combinatorial number system). The vectors of \(b\) bits with \(c\) 1s at the places \(p_1 < \cdots < p_c\) are numbered from 0 to \(\binom{b}{c} - 1\) by

\[ o = \sum_{t=1}^{c} \binom{p_t}{t} , \tag{22.8} \]

their rank in the colexicographic order. The place \(p\), scanned from \(b - 1\) down, holds the \(t\)-th 1, \(t\) being the 1s not yet met, if and only if \(\binom{p}{t} \le o\), where \(o\) is the remainder after the 1s above.

Proof. Note that the vectors that precede a given one in the colexicographic order are, for each \(t\), those that agree with it above \(p_t\) and have their \(t\) lowest 1s below \(p_t\), i.e., \(\binom{p_t}{t}\) of them, which gives (22.8). Since \(\sum_{t' < t} \binom{p_{t'}}{t'} < \binom{p_t}{t}\), the highest term of (22.8) is the largest \(\binom{p}{c} \le o\), which gives the decoding. \(\square\)

Figure 22.4. A block of \(b = 8\) bits (63 in the library) with its 1s at the places 1, 4 and 6: its class 3 and its offset 27 by (22.8), in 6 bits. Below, the classes of four blocks and their offsets of variable width; the blocks of class 0 and 8 take no bit of offset.

Theorem 22.1. RRRBitVector takes at most \(m H_0( B ) + 0.175 m\) bits, with the rank in \(O( 32 + b )\) time and the select in \(O( \log( m / 2016 ) + 32 + b )\) time.

Proof. Note that the product of the \(\binom{b}{c_j}\) of the blocks counts a part of the vectors of \(m\) bits with \(n\) 1s, and therefore by (22.2) \(\sum_j \log_2 \binom{b}{c_j} \le m H_0( B )\); the offsets, rounded up, take at most \(m H_0( B ) + m / b\) bits, and the classes \(6 m / b\). A superblock of 32 blocks (2016 bits) keeps the 1s before it and the place of its first offset, at most \(128 / 2016 = 6.3\%\) of \(m\). In all, one has \(m H_0( B ) + ( 7 / 63 + 128 / 2016 ) m < m H_0( B ) + 0.175 m\). As for the time, the rank of a place sums the classes of the blocks of its superblock before its own, and of their offsets the lengths, at most 31 of each, and rebuilds its block from the highest place down by Lemma 22.7, at most \(b\) steps. Similarly, the select finds the superblock by a binary search on the counts, the block by the classes, and the 1 in the rebuilt block. \(\square\)

Algorithm 22.8. The construction, the rank and the select of RRRBitVector (Raman, Raman and Rao 2007).

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{build}( B ) \cr 2 & \quad n \gets 0 \cr 3 & \quad \textbf{foreach}\ \text{block } j \text{ of } 63 \text{ bits } x \text{ of } B\ \textbf{do} \cr 4 & \qquad \textbf{if}\ j \bmod 32 = 0\ \textbf{then} \ \mathrm{append}( R , n );\ \mathrm{append}( P , | O | ) \cr 5 & \qquad c \gets \mathrm{popcount}( x );\ \mathrm{append}( C , c ) \cr 6 & \qquad o \gets \sum_{t=1}^{c} \binom{p_t}{t}\quad \triangleright \ p_1 < \cdots < p_c \text{ the places of the 1s of } x \cr 7 & \qquad \mathrm{append}( O , o \text{ in } \lceil \log_2 \binom{63}{c} \rceil \text{ bits} );\ n \gets n + c \cr 8 & \quad \mathrm{append}( R , n );\ \mathrm{append}( P , | O | ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{rank1}( i ) \cr 2 & \quad j \gets \lfloor i / 63 \rfloor;\ s \gets \lfloor j / 32 \rfloor;\ r \gets R[ s ];\ q \gets P[ s ] \cr 3 & \quad \textbf{for}\ h \gets 32 s\ \textbf{to}\ j - 1\ \textbf{do}\ r \gets r + C[ h ];\ q \gets q + \lceil \log_2 \binom{63}{C[ h ]} \rceil \cr 4 & \quad c \gets C[ j ];\ o \gets \text{the offset at the place } q \text{ of } O;\ t \gets c \cr 5 & \quad \textbf{for}\ p \gets 62\ \textbf{downto}\ i \bmod 63 \ \textbf{while}\ t > 0\ \textbf{do} \cr 6 & \qquad \textbf{if}\ \binom{p}{t} \le o\ \textbf{then}\ o \gets o - \binom{p}{t};\ t \gets t - 1 \cr 7 & \quad \textbf{return}\ r + t\quad \triangleright\ t \text{ the 1s } \text{below the place } i \bmod 63 \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{select1}( k ) \cr 2 & \quad s \gets \text{the last superblock with } R[ s ] < k \text{, by} \text{ a binary search} \cr 3 & \quad r \gets k - R[ s ];\ q \gets P[ s ];\ j \gets 32 s \cr 4 & \quad \textbf{while}\ r > C[ j ]\ \textbf{do}\ r \gets r - C[ j ]; \ q \gets q + \lceil \log_2 \binom{63}{C[ j ]} \rceil;\ j \gets j + 1 \cr 5 & \quad o \gets \text{the offset at the place } q \text{ of } O;\ t \gets C[ j ] \cr 6 & \quad \textbf{for}\ p \gets 62\ \textbf{downto}\ 0\ \textbf{do} \cr 7 & \qquad \textbf{if}\ \binom{p}{t} \le o\ \textbf{then} \cr 8 & \qquad\quad \textbf{if}\ t = r\ \textbf{then return}\ 63 j + p \cr 9 & \qquad\quad o \gets o - \binom{p}{t};\ t \gets t - 1 \end{array} \]

Note that a query walks only the places it needs: the rank stops at its place or at the last 1, the select at its bit. We write the walk with no branch, the binomials coming from a table of \(64 \times 64\) entries.

The function select0() does the same with the 0s of each block, counted as its length less its class. We rebuild the block in full when it is sparse in 0s.

22.6 Sequences of integers

In the representation of Elias 1974 and Fano (chapters 11 and 15 of Ferragina 2023, EliasFano.h) one codes a non-decreasing sequence \(x_0 \le \cdots \le x_{n-1}\) of integers of \([ 0 , u )\) in about the bits of the lower bound, and searches it in place.

Theorem 22.2 (Elias and Fano). Let each \(x_i\) be split into its \(\ell = \lceil \log_2( u / n ) \rceil\) low bits, written in \(L\), and its bucket \(\lfloor x_i / 2^\ell \rfloor\), written by setting the bit

\[ H[ \lfloor x_i / 2^\ell \rfloor + i ] = 1 . \tag{22.9} \]

Then the sequence takes at most \(2 n + n \lceil \log_2( u / n ) \rceil\) bits, and \(x_i = 2^\ell ( \mathrm{select}_1( H , i + 1 ) - i ) + L[ i ]\).

Proof. Note that the places (22.9) are strictly increasing, since the buckets do not decrease and \(i\) grows, and therefore the \(( i + 1 )\)-th 1 of \(H\) is the one of \(x_i\), from which its bucket is read back by subtracting \(i\). Also, the 0s of \(H\) before that 1 are as many as the bucket, and hence \(H\) has \(n\) 1s. It has at most \(\lfloor ( u - 1 ) / 2^\ell \rfloor + 1 \le n\) 0s, since \(2^\ell \ge u / n\); \(L\) has \(n \ell\) bits. \(\square\)

Against the \(n \log_2( u / n ) + n \log_2 e\) bits of the lower bound, this is less than 2 bits per item more when \(n\) is much smaller than \(u\) (Figure 22.5). With the directory of RankSelect on \(H\), access( i ) takes \(O( 1 )\) time, a select and a field (Algorithm 22.9).

Figure 22.5. The sequence 3, 4, 7, 13, 14, 15, 21, 43 in \(\lbrack 0 , 44 )\) by Elias-Fano, with \(\ell = \lceil \log_2( 44 / 8 ) \rceil = 3\): the low parts \(L\), the buckets, and \(H\), a 1 for each item and a 0 at the end of each bucket. The access to \(x_6\) (violet) finds the seventh 1 of \(H\) at the place 8.

Algorithm 22.9. The construction, the access and the search of Elias-Fano.

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{build}( x , u ) \cr 2 & \quad \ell \gets \lceil \log_2( u / n ) \rceil\ \text{(0 if } u \le n \text{)} \cr 3 & \quad H \gets n + \lfloor ( u - 1 ) / 2^\ell \rfloor + 1 \text{ bits } \text{equal to 0};\ L \gets \text{an empty vector of bits} \cr 4 & \quad \textbf{for}\ i \gets 0\ \textbf{to}\ n - 1\ \textbf{do} \cr 5 & \qquad \mathrm{append}( L , x_i \bmod 2^\ell , \ell ) \cr 6 & \qquad H[ \lfloor x_i / 2^\ell \rfloor + i ] \gets 1 \cr 7 & \quad \text{build the directory of rank and select of } H \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{access}( i ) \cr 2 & \quad h \gets \mathrm{select}_1( H , i + 1 ) - i\quad \triangleright\ \text{the bucket of } x_i \cr 3 & \quad \textbf{return}\ h \cdot 2^\ell + L[ i \ell .. ( i + 1 ) \ell - 1 ] \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{nextGEQ}( x ) \cr 2 & \quad \textbf{if}\ n = 0\ \textbf{or}\ x \ge u\ \textbf{then return} \ n \cr 3 & \quad h \gets \lfloor x / 2^\ell \rfloor;\ \mathit{pos} \gets 0 \ \text{if } h = 0 \text{, else } \mathrm{select}_0( H , h ) + 1 \cr 4 & \quad p \gets \mathit{pos} - h\quad \triangleright\ \text{the first } \text{item of the bucket } h \cr 5 & \quad \textbf{while}\ H[ \mathit{pos} ] = 1\ \textbf{and} \ \mathit{low}( p ) < x \bmod 2^\ell\ \textbf{do} \cr 6 & \qquad p \gets p + 1;\ \mathit{pos} \gets \mathit{pos} + 1\quad \triangleright\ \text{past 8 items, a binary search} \cr 7 & \quad \textbf{return}\ p \end{array} \]

The function nextGEQ( x ) gives the place of the first item \(\ge x\), which is the rank of \(x\) (the items \(< x\)) and gives the predecessor and the successor.

Lemma 22.8. Let \(h = \lfloor x / 2^\ell \rfloor\). The first item \(\ge x\) is either in the bucket \(h\), whose items start after the \(h\)-th 0 of \(H\), or it is the first item of a later bucket; and among the items of the bucket \(h\) the low bits decide, since they are sorted.

Proof. The items of a bucket \(h' < h\) are below \(( h' + 1 ) 2^\ell \le h 2^\ell \le x\), and those of a bucket \(h' > h\) are at least \(( h + 1 ) 2^\ell > x\). Those of the bucket \(h\) share the high bits of \(x\), and they are compared with \(x\) by their low bits, which are in non-decreasing order within the bucket. Finally, the \(h\)-th 0 of \(H\) ends the bucket \(h - 1\), and the 1s after it, up to the next 0, are the items of the bucket \(h\). \(\square\)

Hence nextGEQ() costs a \(\mathrm{select}_0\) and a search of the low bits of the bucket, and contains( x ) tests its result (\(\ell\) itself is lowWidth()). The first 8 items of the bucket are scanned; past them, which the clusters of a sequence may give, the end of the bucket is found by \(\mathrm{select}_0\) too and its low bits by a binary search, so that a bucket of \(c\) items costs \(O( 1 + \log c )\) steps beyond the selects. The \(n\) items fall in \(\lceil u / 2^\ell \rceil\) buckets, at most \(n\) by the proof of Theorem 22.2, and hence a bucket holds at least one item on average.

Ferragina's book computes the rank by a binary search on the select, in \(O( \log n )\) time; the bucket found by \(\mathrm{select}_0\) is the design of the quasi-succinct indices of Vigna 2013 and of the sdarray of Okanohara and Sadakane 2007. Viewed as the places of the 1s of a vector of \(u\) bits with \(n\) 1s, as in chapter 15 of Ferragina, access( i ) is \(\mathrm{select}_1( i + 1 )\) of that vector and nextGEQ( i ) is \(\mathrm{rank}_1( i )\), in \(n ( 2 + \log( u / n ) ) + o( n )\) bits rather than \(u + o( u )\). We write \(H\) with the 1s for the items and the 0s for the buckets, as in chapter 11 of Ferragina; its chapter 15 swaps them, which only swaps \(\mathrm{select}_0\) and \(\mathrm{select}_1\). LazyEliasFano builds the inventories of \(H\) at the first query that needs them, as LazyRankSelect does.

Elias-Fano depends only on \(n\) and \(u\), and it ignores the "clusters" of a sequence. In the partitioned form of Ottaviano and Venturini 2014 (PartitionedEliasFano) we cut a strictly increasing sequence into blocks of 128 items. We code the block \(j\), of \(m\) items, relative to \(b_j = x_{128 j - 1} + 1\), the end of the block before (0 for the first block). Its values \(v = x - b_j\) are in \([ 0 , u_j )\), with \(u_j\) the last of them plus 1, and the block is coded in the cheapest of three codes (Figure 22.6). It takes no bit if \(u_j = m\) (all the values are there). It is a vector of \(u_j\) bits, the bit \(v\) for the value \(v\), if \(u_j\) is at most the bits of Elias-Fano. Otherwise it is Elias-Fano with \(\ell = \lfloor \log_2( u_j / m ) \rfloor\), in \(m \ell + m + \lfloor ( u_j - 1 ) / 2^\ell \rfloor + 1\) bits. The function kinds() counts the blocks of each of the three codes, and contains( x ) is a nextGEQ() here too, as in LAVector.

Figure 22.6. The sequence 3, 4, 5, 6, 7, 8, 9, 10, 20, 41, 70, 99 in blocks of 4 items (128 in the library): the first block is a vector of 7 bits, the second (violet) holds all the values of its range and takes no bit, the third is coded by Elias-Fano; each block has a record with its last item and the place of its code.

Lemma 22.9. A block of \(m\) items with \(u > m\) costs at most \(\min\{ u , \, 2 m + m \lceil \log_2( u / m ) \rceil \}\) bits, i.e., never more than Elias-Fano with the \(\ell\) of Theorem 22.2 on its universe (with equality for \(u = m 2^\ell\)); hence the codes of all the blocks take at most

\[ \sum_j m_j \Bigl( 2 + \Bigl\lceil \log_2 \frac{u_j}{m_j} \Bigr\rceil \Bigr) \le n \Bigl( 3 + \log_2 \frac{u}{n} \Bigr) \tag{22.10} \]

bits, at most one bit per item above the bound of Theorem 22.2 with the logarithm not rounded up.

Proof. Let \(\ell = \lfloor \log_2( u / m ) \rfloor\), the width of the code, so that \(m 2^\ell \le u < m 2^{\ell + 1}\). Its Elias-Fano form takes \(m \ell + m + \lfloor ( u - 1 ) / 2^\ell \rfloor + 1\) bits, and \(( u - 1 ) / 2^\ell < 2 m\) gives at most \(m \ell + 3 m\). If \(u / m\) is not a power of 2, \(\lceil \log_2( u / m ) \rceil = \ell + 1\) and this is \(2 m + m \lceil \log_2( u / m ) \rceil\). If \(u = m 2^\ell\), the term \(\lfloor ( u - 1 ) / 2^\ell \rfloor + 1\) is \(m\), and the cost is \(m \ell + 2 m = 2 m + m \log_2( u / m )\). The code taken is the cheapest of the vector of \(u\) bits and of this form (and no bit when \(u = m\)), which gives the first claim. For the sum, \(\lceil y \rceil < y + 1\) gives \(\sum_j m_j ( 3 + \log_2( u_j / m_j ) )\), and \(\sum_j u_j \le u\), since the universes of the blocks are disjoint ranges of \([ 0 , u )\); by the concavity of the logarithm (the inequality of Jensen on the weights \(m_j / n\)), \(\sum_j m_j \log_2( u_j / m_j ) \le n \log_2( \sum_j u_j / n ) \le n \log_2( u / n )\). \(\square\)

We remark that the extra bit per item of (22.10) comes from the rounding of the logarithm in each block, and it can be reached: on two blocks with \(u_1 / m = 1.5\) and \(u_2 / m = 2.5\) the ceilings sum to 3 per item, while the whole sequence, with \(u / n = 2\), has 1.

Besides, the records of the blocks cost a field of fixed width per block: the last item, the place of the code, and its kind with \(\ell\) in 8 bits (so that a query computes no logarithm). Also, the last item of each eighth block is kept apart for the searches. On the dense runs of an inverted index the cost is usually far smaller than that of Elias-Fano. The function access( i ) reads the records of the block of \(i\) and of the one before (next to each other) and selects the item in the code of the block, a scan of its few words. Also, nextGEQ( x ) finds the first block whose last item is at least \(x\) by a search of the items apart in the layout of Eytzinger (Khuong and Morin 2017), a complete binary tree by levels whose descent fetches the nodes three levels ahead. At most 8 records follow, and the item is found in its block by the high part, or by the sideways sums of the vector up to \(x\) (Algorithm 22.10). Ottaviano and Venturini also choose the ends of the blocks by an approximate dynamic program on the cost of the codes, which gains a further 10% or so on the lists of an index; the blocks here have the fixed size of their uniform partition.

Algorithm 22.10. The construction, the access and the search of the partitioned Elias-Fano (Ottaviano and Venturini 2014).

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{build}( x , u ) \cr 2 & \quad \textbf{foreach}\ \text{block } j \text{ of } m \le 128 \text{ items}\ \textbf{do} \cr 3 & \qquad b_j \gets x_{128 j - 1} + 1\ \text{(0 for } j = 0 \text{)};\ u_j \gets x_{\mathrm{last}} - b_j + 1 \cr 4 & \qquad \ell \gets \lfloor \log_2( u_j / m ) \rfloor;\ e \gets m \ell + m + \lfloor ( u_j - 1 ) / 2^\ell \rfloor + 1 \cr 5 & \qquad \textbf{if}\ u_j = m\ \textbf{then}\ \text{no code (full)} \cr 6 & \qquad \textbf{else if}\ u_j \le e\ \textbf{then}\ \text{the } u_j \text{ bits with a 1 at each } x - b_j \cr 7 & \qquad \textbf{else}\ \text{the Elias-Fano code of the values } x - b_j \text{ with } \ell \text{ low bits} \cr 8 & \qquad \text{the record of } j \text{: its last item, the place of } \text{its code, its kind and } \ell \cr 9 & \quad \text{the last items of the blocks } 0 , 8 , 16 , \ldots \text{ in the layout of Eytzinger} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{access}( i ) \cr 2 & \quad j \gets \lfloor i / 128 \rfloor;\ k \gets i \bmod 128;\ b \gets \text{the last item of } j - 1 \text{, plus 1} \cr 3 & \quad \textbf{if}\ j \text{ is full }\ \textbf{then return}\ b + k \cr 4 & \quad \textbf{if}\ j \text{ is a vector }\ \textbf{then return}\ b + ( \mathrm{select}_1( p , k ) - p ) \cr 5 & \quad h \gets p + m \ell\quad \triangleright\ \text{the start of the } \text{high part} \cr 6 & \quad \textbf{return}\ b + ( \mathrm{select}_1( h , k ) - h - k ) \cdot 2^\ell + \text{the low bits of } k \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{nextGEQ}( x ) \cr 2 & \quad \textbf{if}\ n = 0\ \textbf{or}\ x > \text{the last item } \ \textbf{then return}\ n \cr 3 & \quad t \gets 1;\ \textbf{while}\ t \le | E |\ \textbf{do}\ t \gets 2 t + [ E[ t ] < x ] \cr 4 & \quad a \gets \text{the rank of the first item apart} \ge x \text{,} \text{ from the trailing 1s of } t \cr 5 & \quad j \gets 8 ( a - 1 ) + 1\ \text{(0 if } a = 0 \text{)}; \ \textbf{while}\ \mathrm{last}( j ) < x\ \textbf{do}\ j \gets j + 1 \cr 6 & \quad v \gets \max\{ 0 , x - b_j \} \cr 7 & \quad \textbf{if}\ j \text{ is full }\ \textbf{then}\ k \gets v \cr 8 & \quad \textbf{else if}\ j \text{ is a vector }\ \textbf{then}\ k \gets \text{the 1s of its first } v \text{ bits} \cr 9 & \quad \textbf{else}\ k \gets \text{the place of } v \text{ in its } \text{code, as in } \mathrm{nextGEQ} \text{ of Elias-Fano} \cr 10 & \quad \textbf{return}\ 128 j + k \end{array} \]

Elias-Fano spends on each item the same bits, whatever the regularity of the gaps. In the LA-vector of Boffa, Ferragina and Vinciguerra 2021 (LAVector) one spends them instead on the distance of each item from a line. We cover the points \(( i , x_i )\) by the fewest segments whose lines are within \(\epsilon\) of each of their points, the optimal piecewise linear approximation of the PGM-index (Ferragina and Vinciguerra 2020, ADS/search/PGMIndex.h), and each item is stored as its correction with respect to the line of its segment (Figure 22.7).

Figure 22.7. The points \(( i , x_i )\) of a sequence of 16 items covered by two segments, each line with its band of half-width \(\epsilon = 2\); the item 5 (violet) is stored as its correction \(C[ 5 ]\), its distance from the line of its segment.

Lemma 22.10 (the corrections). Let the segment \(j\), over the places \([ p_j , p_{j+1} )\), have a line \(f( i ) = x_{p_j} + \gamma + \alpha ( i - p_j )\) with \(| f( i ) - x_i | \le \epsilon\) for each of its places, and let \(d_i = x_i - x_{p_j} - \lfloor \alpha ( i - p_j ) \rfloor\). Then the \(d_i\) take at most \(2 \epsilon + 2\) values, and with \(\beta_j = x_{p_j} + \min_i d_i\)

\[ x_i = \beta_j + \lfloor \alpha ( i - p_j ) \rfloor + C[ i ] , \qquad 0 \le C[ i ] < 2^c \text{ for } \epsilon = 2^{c-1} - 1 . \tag{22.11} \]

Proof. \(x_i - x_{p_j} - \alpha ( i - p_j )\) lies in \([ \gamma - \epsilon , \gamma + \epsilon ]\), and taking off the integer part of \(\alpha ( i - p_j )\) instead of the whole of it adds less than 1. Hence the \(d_i\) are integers in an interval of length less than \(2 \epsilon + 2\), at most \(2 \epsilon + 2 = 2^c\) of them, and \(C[ i ] = d_i - \min_i d_i\) takes \(c\) bits. \(\square\)

In the code the slope \(\alpha\) is kept in a double, whose rounding may spread the \(d_i\) by a few units on items of 64 bits. LAVector therefore computes the corrections with the rounded slope and gives each segment the width \(w_j\) of the range of the corrections of the segment, so that (22.11) holds with \(w_j\) in place of \(c\) (\(c\), or one bit more). One can count the space as follows. A segment takes 24 bytes (the base, the slope, and the place of its corrections with their width; its first item is its base plus its first correction). Its first place takes a field of \(\lceil \log_2 n \rceil\) bits, and the two tables that find a segment by a place and by a value about two fields of \(\lceil \log_2 m \rceil\) bits per segment. Hence the sequence takes about

\[ \sum_j w_j ( p_{j+1} - p_j ) + m \big( 192 + \lceil \log_2 n \rceil + 2 \lceil \log_2 m \rceil \big) \tag{22.12} \]

bits for \(m\) segments (Algorithm 22.11).

Algorithm 22.11. The construction, the access and the search of the LA-vector (Boffa, Ferragina and Vinciguerra 2021), and the choice of the width of the corrections.

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{build}( x , c ) \cr 2 & \quad \textbf{foreach}\ \text{segment } j \text{ of } \mathrm{approximate}( ( i , x_i ) , \epsilon )\ \textbf{do}\quad \triangleright\ \text{see } \mathrm{PGMIndex} \cr 3 & \qquad \textbf{for}\ i \gets p_j\ \textbf{to}\ p_{j+1} - 1 \ \textbf{do}\ d_i \gets x_i - x_{p_j} - T( \alpha_j ( i - p_j ) ) \cr 4 & \qquad \beta_j \gets x_{p_j} + \min_i d_i;\ w_j \gets \lceil \log_2( \max_i d_i - \min_i d_i + 1 ) \rceil \cr 5 & \qquad \textbf{for}\ i \gets p_j\ \textbf{to}\ p_{j+1} - 1 \ \textbf{do}\ \mathrm{append}( C , d_i - \min_i d_i , w_j ) \cr 6 & \quad \text{fill the table of the segment of every } 2^t \text{-th place and the table on the high bits of the first items} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{access}( i ) \cr 2 & \quad j \gets J[ \lfloor i / 2^t \rfloor ] \cr 3 & \quad \textbf{while}\ p_{j+1} \le i\ \textbf{do}\ j \gets j + 1 \cr 4 & \quad \textbf{return}\ \beta_j + T( \alpha_j ( i - p_j ) ) + C[ i ] \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{nextGEQ}( x ) \cr 2 & \quad \textbf{if}\ n = 0\ \textbf{or}\ x \le x_0\ \textbf{then return} \ 0 \cr 3 & \quad \textbf{if}\ x > x_{n-1}\ \textbf{then return}\ n \cr 4 & \quad h \gets \lfloor ( x - x_0 ) / 2^\ell \rfloor \cr 5 & \quad j \gets \text{the last segment in } [ V[ h ] - 1 , V[ h + 1 ] ] \text{ with } x_{p_j} < x\text{, by a binary search} \cr 6 & \quad a \gets p_j + \lfloor ( x - \beta_j - 2^{w_j} ) / \alpha_j \rfloor - 1;\ b \gets p_j + \lceil ( x - \beta_j + 1 ) / \alpha_j \rceil + 1 \cr 7 & \quad \textbf{if}\ \text{not}\ x_{a-1} < x \le x_b\ \textbf{then} \ ( a , b ) \gets ( p_j , p_{j+1} ) \cr 8 & \quad \textbf{return}\ \text{the first } i \in [ a , b ] \text{ with } x_i \ge x \text{, by a binary search} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{tuned}( x ) \cr 2 & \quad b \gets \mathrm{build}( x , 1 );\ t \gets c_{\mathrm{max}} \cr 3 & \quad \textbf{for}\ c \gets 3\ \textbf{to}\ t\ \textbf{step}\ 2 \ \textbf{do} \cr 4 & \qquad v \gets \mathrm{build}( x , c );\ \textbf{if}\ v \text{ takes} \text{ fewer bits than } b\ \textbf{then}\ b \gets v \cr 5 & \quad \textbf{foreach}\ c \in \{ c_b - 1 , c_b + 1 \}\ \textbf{do} \ \text{the same} \cr 6 & \quad \textbf{return}\ b \end{array} \]

Accessing \(x_i\) is (22.11) once the segment of \(i\) is known, which a table of the segment of each \(2^t\)-th place gives after a scan of the segments that start among the \(2^t\) places before \(i\), one on average for \(2^t \approx n / m\). In turn, the rank of \(x\) first finds the last segment whose first item is below \(x\), through a table of the first segment of each bucket of the high bits of the items, as the buckets of Elias-Fano. Then, since by (22.11) \(\beta_j + \lfloor \alpha ( i - p_j ) \rfloor \le x_i < \beta_j + \lfloor \alpha ( i - p_j ) \rfloor + 2^{w_j}\), the answer is among the places where the line goes from \(x - 2^{w_j}\) to \(x + 1\), about \(2^{w_j} / \alpha\) of them. A binary search on the corrections settles it in \(O( w_j - \log_2 \alpha )\) steps; when the floating point misplaces the window, which the search checks on the two items at its ends, the whole segment is searched.

Against Elias-Fano, which takes \(2 + \lceil \log_2( u / n ) \rceil\) bits per item, the LA-vector may win when the items follow lines "closely". This happens, e.g., on the places of a pattern repeated with some noise, on the keys of a process that grows at a steady rate, or on the dense runs of an inverted index, where \(m\) is small and \(c\) is the logarithm of the noise instead of the average gap. On gaps drawn at random no line may follow the items better than the average gap does, the corrections need about \(\log_2( u / n )\) bits as the low bits of Elias-Fano, and the segments are an overhead. The function tuned() therefore tries the widths up to six bits above the logarithm of the average gap (or half the bits of the items, if more) and keeps the one of the fewest bits. In the journal form of Boffa, Ferragina and Vinciguerra 2022, the LA-vector chooses the width segment by segment, by a shortest path over the segments of all the widths. Its gain comes from segments of different widths, which the width \(w_j\) that each segment takes from its corrections already gives in part, and the library does not implement the shortest path.

22.7 Arrays of packed fields

An array of \(n\) values below \(2^B\) takes \(n B\) bits when its fields are packed in words, against the \(8 n\) of a byte per value. In the searches, the tables of "large" spaces of states may have \(10^9\) entries and more, e.g., the pattern databases of the heuristic search (Felner, Korf and Hanan 2004), and they fit in the memory only so packed. PackedArray< B > takes the widths that divide 64, \(B \in \{ 1 , 2 , 4 , 8 , 16 , 32 \}\). A word then holds \(64 / B\) fields (the constant PER, and MAX is \(2^B - 1\), the largest value of a field), and the field \(i\) is the bits \(( i \bmod 64 / B ) B\) on of the word \(\lfloor i B / 64 \rfloor\). A read is one load, one shift and one mask, with no test of a field that crosses two words, which BitVector::get( i , len ) pays for the other widths (Figure 22.8). A write clears the field by a mask and puts the value by an or, in the same word.

A saturated array (the template parameter Saturate) stores a value above \(2^B - 1\) as \(2^B - 1\), and counts it in clamped(), instead of breaking the contract. When the values are lower bounds, e.g., the distances of a pattern database, a value cut down is still a "good" lower bound, and \(B\) is then chosen for most of the values rather than for the largest one.

Figure 22.8. Above, a word of PackedArray< 4 > with its 16 fields, the field 15 on the left; the field 5 (violet) was written by set( 5 , 9 ). Below, a byte of TritArray, which holds five values in base 3, and the write of one digit by an addition.

A value of three states carries \(\log_2 3 \approx 1.585\) bits of information, but takes 2 bits in a field of PackedArray< 2 >. We may put five such values (trits) \(t_0 , \ldots , t_4\) in one byte as the number

\[ y = \sum_{j = 0}^{4} t_j 3^j \le 3^5 - 1 = 242 , \tag{22.13} \]

i.e., in 1.6 bits per value, 0.015 above the entropy and one fifth less than the fields of 2 bits (Breyer and Korf 2010, whose tables keep the distances modulo 3, from which the distance of a state is recovered along a path to the goal). TritArray reads the digit \(j = i \bmod 5\) of the byte \(\lfloor i / 5 \rfloor\) from a table of the five digits of each of the 243 bytes, 1215 bytes that stay in the cache of the first level. It writes the digit by adding \(( v - t_j ) 3^j\) to the byte, which by (22.13) changes only that digit.

Six values would need \(3^6 = 729 > 256\) codes, and \(3^{40} < 2^{64} < 3^{41}\) would put 40 values in a word, 1.6 bits each again, at the price of a division by a power of 3 per read; the byte is the unit with the same density and a read by a table. Both arrays are also built from a function \(f\) of the place by blocks of whole words (of whole bytes for the trits) on the threads of an executor (Algorithm 22.12). A word is written by the one thread that owns its block, and therefore no write needs an atomic and the array is the same as the sequential one; the work is \(O( n )\) calls of \(f\), with the depth of one block.

Algorithm 22.12. The parallel construction and the write of PackedArray and of TritArray.

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{build}( \mathit{ex} , n , f ) \cr 2 & \quad \textbf{foreach}\ \text{block } [ a , b ) \text{ of the } \text{words, in parallel}\ \textbf{do} \cr 3 & \qquad \textbf{for}\ w \gets a\ \textbf{to}\ b - 1\ \textbf{do} \cr 4 & \qquad\quad x \gets 0 \cr 5 & \qquad\quad \textbf{for}\ j \gets 0\ \textbf{to}\ \min\{ 64 / B , n - 64 w / B \} - 1\ \textbf{do} \cr 6 & \qquad\qquad x \gets x \vee ( \min\{ f( 64 w / B + j ) , 2^B - 1 \} \ll j B ) \cr 7 & \qquad\quad W[ w ] \gets x \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{set}( i , v ) \cr 2 & \quad c \gets v > 2^B - 1;\ v \gets \min\{ v , 2^B - 1 \} \cr 3 & \quad W[ \lfloor i B / 64 \rfloor ] \gets ( W[ \lfloor i B / 64 \rfloor ] \wedge \neg( ( 2^B - 1 ) \ll s ) ) \vee ( v \ll s ) \cr 4 & \quad \textbf{return}\ c \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{build}( \mathit{ex} , n , f ) \cr 2 & \quad \textbf{foreach}\ \text{block } [ a , b ) \text{ of the } \text{bytes, in parallel}\ \textbf{do} \cr 3 & \qquad \textbf{for}\ y \gets a\ \textbf{to}\ b - 1\ \textbf{do} \cr 4 & \qquad\quad x \gets 0 \cr 5 & \qquad\quad \textbf{for}\ j \gets \min\{ 5 , n - 5 y \} - 1 \ \textbf{downto}\ 0\ \textbf{do}\ x \gets 3 x + f( 5 y + j ) \cr 6 & \qquad\quad Y[ y ] \gets x \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{set}( i , v ) \cr 2 & \quad t \gets \mathrm{get}( i ) \cr 3 & \quad Y[ \lfloor i / 5 \rfloor ] \gets Y[ \lfloor i / 5 \rfloor ] + ( v - t ) \, 3^{i \bmod 5} \end{array} \]

22.8 Trees

One can code a tree by its shape and nothing more, in about the \(2 n\) bits of the lower bound of §22.1, and its nodes are then numbered by the places of their bits; the data of a node go in a vector indexed by its number. We give three codes, which differ in the operations that they answer in constant time.

Lemma 22.11 (the binary tree of Jacobson). Complete a binary tree of \(n\) nodes with a leaf in place of each missing child, and write by levels a 1 for a node and a 0 for a leaf added, in \(B[ 1 , 2 n + 1 ]\). Then the children of the \(x\)-th node are at the places \(2 x\) and \(2 x + 1\), and the item at the place \(p\) is the \(\mathrm{Rank}_1( p )\)-th node if \(B[ p ] = 1\).

Proof. A visit by levels lists the root at the place 1, and then the children of the nodes in the order of the nodes, two per node. Hence the children of the first \(x - 1\) nodes take the places \(2 , \ldots , 2 x - 1\), and those of the \(x\)-th one the next two. \(\square\)

One can see that, with rank and select in \(O( 1 )\) time, the left child of the \(x\)-th node is the \(\mathrm{Rank}_1( 2 x )\)-th node, if \(B[ 2 x ] = 1\), and its parent the \(\lfloor \mathrm{Select}_1( x ) / 2 \rfloor\)-th; in the notation of Ferragina's book, which names a node by its place \(p\), the left child is at the place \(2 \, \mathrm{Rank}_1( p )\) and the parent at \(\mathrm{Select}_1( \lfloor p / 2 \rfloor )\). Hence JacobsonTree (Jacobson 1989) takes \(2 n + 1 + o( n )\) bits, within \(O( \log n )\) of the lower bound, with left(), right() and parent() in \(O( 1 )\) time (Figure 22.9). In the library the nodes are numbered \(0 , \ldots , n - 1\) by levels and the places from 0, i.e., the node \(v\) is the \(( v + 1 )\)-th node and the place \(q\) is the place \(q + 1\) of Lemma 22.11. Then the node \(v\) is at the place \(\mathrm{select}_1( v + 1 )\); its left child is at the place \(2 ( v + 1 ) - 1 = 2 v + 1\), and it is the node \(\mathrm{rank}_1( 2 v + 1 )\) if that place holds a 1; and its parent is the \(\lfloor ( \mathrm{select}_1( v + 1 ) + 1 ) / 2 \rfloor\)-th node, i.e., the node \(\lfloor ( \mathrm{select}_1( v + 1 ) + 1 ) / 2 \rfloor - 1\) (Algorithm 22.13). This representation answers the navigation, but not the size of a subtree, which needs the order of a visit in depth.

Figure 22.9. A binary tree of 6 nodes completed with a leaf (faintest tint) in place of each missing child, the places of its nodes by levels from 1, and its code \(B\) of \(2 n + 1 = 13\) bits; C, the third node, has its children E and F at the places 6 and 7 (violet).

Algorithm 22.13. The code by levels of a binary tree, and its left child and parent (Jacobson 1989).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{levelCode}( c ) \cr 2 & \quad B \gets ( 1 )\quad \triangleright\ \text{the root} \cr 3 & \quad Q \gets \text{an empty queue};\ \mathrm{enqueue}( Q , 0 ) \cr 4 & \quad \textbf{while}\ Q \ne \emptyset\ \textbf{do} \cr 5 & \qquad u \gets \mathrm{dequeue}( Q ) \cr 6 & \qquad \textbf{foreach}\ w \in ( c[ u ].\mathit{first} , c[ u ].\mathit{second} )\ \textbf{do} \cr 7 & \qquad\quad \textbf{if}\ w = \textbf{nil}\ \textbf{then}\ B \gets B \cdot 0\ \textbf{else}\ B \gets B \cdot 1;\ \mathrm{enqueue}( Q , w ) \cr 8 & \quad \textbf{return}\ B \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{left}( v ) \cr 2 & \quad \textbf{if}\ B[ 2 v + 1 ] = 0\ \textbf{then return nil} \cr 3 & \quad \textbf{return}\ \mathrm{rank}_1( 2 v + 1 ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{parent}( v ) \cr 2 & \quad \textbf{if}\ v = 0\ \textbf{then return nil} \cr 3 & \quad \textbf{return}\ \lfloor ( \mathrm{select}_1( v + 1 ) + 1 ) / 2 \rfloor - 1 \end{array} \]

For a tree of any degree, LOUDS (the level-order unary degree sequence of Jacobson, LoudsTree) puts a dummy root of degree 1 above the root and writes the degree \(d\) of each node, by levels, as \(0^d 1\). Hence the code has \(n\) 0s, one per node (each node is the child of somebody), and \(n + 1\) 1s, one per node and the dummy root, i.e., \(2 n + 1\) bits (Figure 22.10).

Lemma 22.12. In the code of LOUDS, the \(k\)-th 0 is the \(k\)-th node by levels, and the children of the \(k\)-th node are the 0s after the \(( k + 1 )\)-th 1. Hence, with the nodes numbered from 0 and the places from 0,

\[ \mathrm{parent}( v ) = \mathrm{select}_0( v + 1 ) - v - 1 , \qquad \mathrm{leftmostChild}( v ) = \mathrm{select}_1( v + 1 ) - v , \tag{22.14} \]

the latter when a 0 follows the \(( v + 1 )\)-th 1, and \(\mathrm{degree}( v ) = \mathrm{select}_1( v + 2 ) - \mathrm{select}_1( v + 1 ) - 1\).

Proof. Each node writes a 0 for each of its children, in the order by levels. These 0s come in the order of the nodes that they stand for, since the visit by levels lists the children of the nodes in the order of the nodes, and the dummy root writes the 0 of the root. Furthermore, the \(( k + 1 )\)-th 1 ends the unary degree of the \(k\)-th node (the first 1 being that of the dummy root), and its children are the 0s that follow it. In particular, the 0 of \(v\) is at \(q = \mathrm{select}_0( v + 1 )\), and the 1s before it are \(q - v\), of which the first is the dummy root's; hence its parent is the node \(q - v - 1\). Similarly, the 0 after the \(( v + 1 )\)-th 1, at \(p + 1\) with \(p = \mathrm{select}_1( v + 1 )\), is the \(( p + 1 - v )\)-th 0, i.e., the node \(p - v\). \(\square\)

Figure 22.10. An ordered tree of 8 nodes, numbered by levels and, in parentheses, in preorder. Above, its code by LOUDS after the dummy root 01, the unary degree of each node bracketed; the degree of the node 1 (violet) is the 0s 6 and 7, its children 4 and 5. Below, its balanced parentheses in preorder and their excess \(E\): the pair of the node 1 opens at 1 and closes at 8, the first place after 1 where the excess falls to \(E( 1 ) - 1 = 1\) (dashed).

Its functions are leftmostChild() and rightSibling(), the names of the TREE of the book (ADS/tree/Tree.h); the \(i\)-th child is the first one plus \(i\), since the children of a node are consecutive in the order by levels, which a visit in depth does not give (Algorithm 22.14). LOUDS does not answer the size of a subtree nor the depth of a node; it is the simplest of the succinct trees and, arguably, the "fastest" for the navigation from the root down (Arroyuelo, Cánovas, Navarro and Sadakane 2010), e.g., in the tries of the indices.

Algorithm 22.14. The code by LOUDS of an ordered tree.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{louds}( c ) \cr 2 & \quad B \gets ( 0 , 1 )\quad \triangleright\ \text{the dummy root,} \text{ of degree 1} \cr 3 & \quad Q \gets \text{an empty queue};\ \mathrm{enqueue}( Q , 0 ) \cr 4 & \quad \textbf{while}\ Q \ne \emptyset\ \textbf{do} \cr 5 & \qquad u \gets \mathrm{dequeue}( Q ) \cr 6 & \qquad \textbf{foreach}\ w \in c[ u ]\ \textbf{do}\ B \gets B \cdot 0;\ \mathrm{enqueue}( Q , w ) \cr 7 & \qquad B \gets B \cdot 1 \cr 8 & \quad \textbf{return}\ B \end{array} \]

In turn, the balanced parentheses (BPTree, after Munro and Raman 2001) write an open parenthesis, a 1, when a visit in depth enters a node, and a closed one, a 0, when it leaves it. Hence the nodes of a subtree are consecutive in preorder, and a node is the pair of its parentheses. With the excess \(E( i )\), the open parentheses less the closed ones in \(B[ 0 , i ]\) (and \(E( -1 ) = 0\)), one has

\[ \mathrm{findClose}( i ) = \min \{ j > i : E( j ) = E( i ) - 1 \} , \tag{22.15} \]

(cf. Figure 22.10), and similarly for findOpen() and enclose(), the open parenthesis of the pair that encloses the one at \(i\).

Lemma 22.13. In a balanced sequence of parentheses, (i) (22.15) gives the closed parenthesis that matches the open one at \(i\); (ii) findOpen( j ) is \(k + 1\) for the last \(k < j\) with \(E( k ) = E( j )\), and enclose( i ) is \(k + 1\) for the last \(k < i\) with \(E( k ) = E( i ) - 2\); (iii) the first place after (or before) a start whose excess is at most a target \(t\) below the excess of the start has the excess \(t\); (iv) \(E( i ) = 2 \, \mathrm{rank}_1( i + 1 ) - ( i + 1 )\).

Proof. (iv) Among the \(i + 1\) parentheses of \(B[ 0 , i ]\), the open ones are \(\mathrm{rank}_1( i + 1 )\) and the closed ones the rest. (iii) The excess changes by \(\pm 1\) from a place to the next, and therefore it cannot pass from above \(t\) to below \(t\) without taking the value \(t\). (i) The parenthesis at \(i\) is open, so that \(E( i ) = E( i - 1 ) + 1\). The parentheses strictly inside its pair form a balanced sequence, whose prefixes have a nonnegative excess, and hence \(E( j ) \ge E( i )\) inside the pair; the matching closed parenthesis at \(c\) gives \(E( c ) = E( i ) - 1\), and \(c\) is therefore the least \(j > i\) with that excess. (ii) For the closed parenthesis at \(j\) and its match at \(o\), the parentheses between them are balanced, so that \(E( o - 1 ) = E( j )\) and \(E( k ) > E( j )\) for \(o \le k < j\); hence \(o - 1\) is the last \(k < j\) with \(E( k ) = E( j )\). The pair that encloses the one at \(i\) opens at the last place \(o' < i\) whose parenthesis is open and whose pair contains \(i\). Between \(o'\) and \(i\) the parentheses are balanced pairs, so that \(E( i - 1 ) = E( o' )\), i.e., \(E( o' - 1 ) = E( i ) - 2\), and each \(k\) with \(o' \le k < i\) has \(E( k ) \ge E( i ) - 1\). \(\square\)

By (iii), each operation is a search for the first place, forward or backward, whose excess reaches a target, and by (iv) the excess of a place costs \(O( 1 )\) time.

BalancedParentheses answers the searches by the range min-max tree of Navarro and Sadakane 2014. It keeps, for each leaf of 512 bits, for each group of 16 leaves and for each node of a complete binary tree over the groups, the total excess of its range and its minimum prefix excess. A search runs on the excess relative to its start, and needs no rank. It scans the leaf of \(i\) a byte at a time, with the excess, the minimum and the place of each target of each of the 256 bytes in tables. Then it scans the leaves of the group of \(i\) by their excess and minimum in 16 bits. At last it climbs the tree, whose leaves are the groups, to the first range on its side whose minimum reaches the target, and goes down to its group, its leaf and its byte (Algorithm 22.15). A range whose minimum stays above the target holds no answer, by (iii) of Lemma 22.13, and it is skipped whole; the first range on the side of the search whose minimum reaches the target holds the answer, again by (iii). The search thus scans at most two leaves of \(512 / 8\) bytes, two groups of 16 leaves, and climbs and descends the binary tree over the \(n / 8192\) groups, i.e., \(O( \log( n / 8192 ) + 16 + 512 / 8 )\) time. In a tree, most searches end in the leaf of \(i\), at the cost of one miss of the cache.

Algorithm 22.15. The range min-max tree, and the forward search of findClose() (Navarro and Sadakane 2014).

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{build}( b ) \cr 2 & \quad \textbf{for}\ l \gets 0\ \textbf{to}\ \ell - 1\ \textbf{do} \cr 3 & \qquad e \gets 0;\ \mu \gets 0 \cr 4 & \qquad \textbf{foreach}\ \text{byte } y \text{ of the leaf } l \ \textbf{do} \cr 5 & \qquad\quad \mu \gets \min\{ \mu , e + \mathit{min}_8[ y ] \};\ e \gets e + \mathit{exc}_8[ y ]\quad \triangleright\ \text{by tables} \cr 6 & \qquad \mathit{lexc}[ l ] \gets e;\ \mathit{lmin}[ l ] \gets \mu;\ v \gets g + \lfloor l / 16 \rfloor \cr 7 & \qquad \mathit{min}[ v ] \gets \min\{ \mathit{min}[ v ] , \mathit{exc}[ v ] + \mu \};\ \mathit{exc}[ v ] \gets \mathit{exc}[ v ] + e \cr 8 & \quad \textbf{for}\ v \gets g - 1\ \textbf{downto}\ 1\ \textbf{do} \cr 9 & \qquad \mathit{exc}[ v ] \gets \mathit{exc}[ 2 v ] + \mathit{exc}[ 2 v + 1 ] \cr 10 & \qquad \mathit{min}[ v ] \gets \min\{ \mathit{min}[ 2 v ] , \mathit{exc}[ 2 v ] + \mathit{min}[ 2 v + 1 ] \} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{findClose}( i ) \cr 2 & \quad d \gets -1;\ e \gets 0;\ l \gets \text{the leaf of } i \cr 3 & \quad \text{scan the leaf } l \text{ from } i + 1 \text{, a byte } \text{at a time;}\ \textbf{if}\ \text{some } j \text{ has } e \le d \ \textbf{then return}\ j \cr 4 & \quad \textbf{foreach}\ \text{next leaf } l \text{ of its group} \ \textbf{do} \cr 5 & \qquad \textbf{if}\ e + \mathit{lmin}[ l ] \le d \ \textbf{then return}\ \text{the place found by the scan of } l \cr 6 & \qquad e \gets e + \mathit{lexc}[ l ] \cr 7 & \quad v \gets \text{the leaf of the tree for the group} \cr 8 & \quad \textbf{while}\ v > 1\ \textbf{and not}\ ( v \text{ is a left } \text{child}\ \textbf{and}\ e + \mathit{min}[ v + 1 ] \le d ) \ \textbf{do} \cr 9 & \qquad \textbf{if}\ v \text{ is a left child }\ \textbf{then}\ e \gets e + \mathit{exc}[ v + 1 ] \cr 10 & \qquad v \gets \lfloor v / 2 \rfloor \cr 11 & \quad \textbf{if}\ v = 1\ \textbf{then return nil} \cr 12 & \quad v \gets v + 1\quad \triangleright\ \text{the right sibling} \text{ that reaches } d \cr 13 & \quad \textbf{while}\ v \text{ is not a leaf }\ \textbf{do}\quad \triangleright\ \text{down to the leftmost range that reaches } d \cr 14 & \qquad \textbf{if}\ e + \mathit{min}[ 2 v ] \le d\ \textbf{then}\ v \gets 2 v\ \textbf{else}\ e \gets e + \mathit{exc}[ 2 v ];\ v \gets 2 v + 1 \cr 15 & \quad l \gets \text{the first leaf of the group } v \text{ with } e + \mathit{lmin}[ l ] \le d \text{, adding the } \mathit{lexc} \text{ of those before} \cr 16 & \quad \textbf{return}\ \text{the place found by the scan of } l \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{findOpen}( j ) \cr 2 & \quad k \gets \text{the last } k < j \text{ with } E( k ) - E( j ) \le 0 \text{, } E( -1 ) = 0 \text{, by the leaf of } j \text{, its} \text{ group and the tree} \cr 3 & \quad \textbf{return}\ k + 1 \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{enclose}( i ) \cr 2 & \quad \textbf{if}\ \text{no } k < i \text{ has } E( k ) - E( i ) \le -2\ \textbf{then return nil}\quad \triangleright\ \text{the outer } \text{level} \cr 3 & \quad \textbf{return}\ k + 1 \text{ for the last such } k \end{array} \]

In space, the tree takes \(32 / 512\) bits per parenthesis for the leaves (6.25%) and at most \(4 \cdot 128 / 8192\) for the groups, besides the directory of rank of CompactRankSelect, 3.5% of the bits, since no search needs a rank. The function forwardSearch( i , d ) gives the first \(j > i\) with \(E( j ) - E( i ) = d < 0\). This may also be the end of a subtree of the code by the degrees in depth (ADS/dictionary/SuccinctPatriciaTrie.h). Jacobson 1989 gives findClose() in \(O( \log n )\) time with the pioneers, and Munro and Raman in \(O( 1 )\) time with two levels of pioneers and tables, in \(2 n + o( n )\) bits. Then the range min-max tree of Navarro and Sadakane reaches \(O( 1 )\) time with a tree of degree \(\Theta( \log n )\) and tables. Its binary form with blocks of a few hundred bits, the one here, is usually the fastest in practice, at least on the trees of the benchmarks (Arroyuelo, Cánovas, Navarro and Sadakane 2010; Gog and Petri 2014; Grossi and Ottaviano 2013).

BPTree numbers the nodes in preorder, the node \(v\) being the \(( v + 1 )\)-th open parenthesis. The function parent( v ) is enclose() of its open parenthesis, leftmostChild( v ) is \(v + 1\) if the next parenthesis is an open one, and rightSibling( v ) is the open parenthesis after its closed one, if any (Algorithm 22.16). Furthermore, subtreeSize( v ) is \(( j - i + 1 ) / 2\) for its parentheses at \(i\) and \(j\), depth( v ) is the excess at its open parenthesis less 1, and \(u\) is an ancestor of \(v\) if \(u \le v < u + \mathrm{subtreeSize}( u )\), the test of isAncestor( u , v ). These may cost a search of the range min-max tree, or a select and a rank for leftmostChild(), depth() and isLeaf().

Lemma 22.14. With the node \(v\) at the open parenthesis \(i\) and its match at \(j\), the subtree of \(v\) has \(( j - i + 1 ) / 2\) nodes, numbered \(v , \ldots , v + ( j - i - 1 ) / 2\) in preorder, the depth of \(v\) is \(E( i ) - 1\), and the formulas of parent(), leftmostChild(), rightSibling() and isAncestor() above are right.

Proof. The visit in depth writes the parentheses of the subtree of \(v\) between entering and leaving \(v\), i.e., in \(B[ i , j ]\), two per node, and it enters these nodes consecutively in preorder, starting from \(v\). The open parentheses before \(i\) whose match is after \(i\) are those of the ancestors of \(v\), and the others before \(i\) are matched before it; hence \(E( i - 1 )\) is the number of the proper ancestors of \(v\), which is its depth, and \(E( i ) - 1 = E( i - 1 )\). The parent of \(v\) is the nearest of these ancestors, the pair that encloses \(i\) (Lemma 22.13); the first child of \(v\), if any, is entered right after \(v\), at \(i + 1\), and it is the node \(v + 1\); the next sibling of \(v\), if any, is entered right after leaving \(v\), at \(j + 1\). Finally, \(u\) is an ancestor of \(v\) (or \(v\) itself) if and only if \(v\) is in the subtree of \(u\), i.e., \(u \le v < u + \mathrm{subtreeSize}( u )\). \(\square\) Against LOUDS, the parentheses give the size of a subtree, the depth and the ancestors, and number the nodes of a subtree consecutively (from \(v\) to \(v + \mathrm{subtreeSize}( v ) - 1\)), at the price of the searches. We remark that DFUDS of Benoit et al. 2005, the degrees in unary in preorder, also gives the \(i\)-th child in \(O( 1 )\) time with the same matching; chapter 15 of Ferragina does not treat it, and neither does the library.

Algorithm 22.16. The parentheses of a tree by a visit in depth, and the parent and the next sibling in BPTree.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{parentheses}( c ) \cr 2 & \quad B \gets ( 1 );\ S \gets \text{the stack } ( ( 0 , 0 ) ) \cr 3 & \quad \textbf{while}\ S \ne \emptyset\ \textbf{do} \cr 4 & \qquad ( u , k ) \gets \mathrm{top}( S ) \cr 5 & \qquad \textbf{if}\ k < | c[ u ] |\ \textbf{then} \cr 6 & \qquad\quad w \gets c[ u ][ k ];\ \mathrm{top}( S ) \gets ( u , k + 1 ) \cr 7 & \qquad\quad B \gets B \cdot 1;\ \mathrm{push}( S , ( w , 0 ) )\quad \triangleright\ \text{enter } w \cr 8 & \qquad \textbf{else} \cr 9 & \qquad\quad B \gets B \cdot 0;\ \mathrm{pop}( S )\quad \triangleright\ \text{leave } u \cr 10 & \quad \textbf{return}\ B \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{parent}( v ) \cr 2 & \quad q \gets \mathrm{enclose}( \mathrm{select}_1( v + 1 ) ) \cr 3 & \quad \textbf{if}\ q = \textbf{nil}\ \textbf{then return nil} \cr 4 & \quad \textbf{return}\ \mathrm{rank}_1( q ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{rightSibling}( v ) \cr 2 & \quad q \gets \mathrm{findClose}( \mathrm{select}_1( v + 1 ) ) + 1 \cr 3 & \quad \textbf{if}\ q < | B |\ \textbf{and}\ B[ q ] = 1 \ \textbf{then return}\ \mathrm{rank}_1( q ) \cr 4 & \quad \textbf{return nil} \end{array} \]

Table 22.3 compares the trees, and the graphs of §22.10.

Table 22.3. The trees and the graphs and their costs, for \(n\) nodes and \(m\) edges.

Realization Space in bits Operations
JacobsonTree \(2 n + 1 + o( n )\) the children and the parent of a binary tree in \(O( 1 )\)
LoudsTree \(2 n + 1 + o( n )\) the parent, the degree, the \(i\)-th child and the next sibling in \(O( 1 )\)
BPTree, on BalancedParentheses \(2 n\), and 6.25% of them for the leaves of the range min-max tree, at most as much for its groups and 3.5% for a rank directory also the size of a subtree, the depth and the ancestors, by a search of the excess
EliasFanoGraph \(m ( 2 + \lceil \log_2( n^2 / m ) \rceil ) + n ( 2 + \lceil \log_2( m / n ) \rceil )\) the outdegree and the \(i\)-th successor in \(O( 1 )\), an edge by a nextGEQ()
BVGraph about 3 per edge on the Web graphs a list in \(O( R d )\), \(R\) the longest chain of references
K2Tree \(k^2 m ( \log_{k^2}( n^2 / m ) + O( 1 ) )\) in the worst case an edge in \(O( h )\), the successors and the predecessors of a node

22.9 Sequences of symbols and permutations

Our wavelet matrix, that of Claude, Navarro and Ordóñez 2015 (WaveletMatrix), holds a static sequence \(S[ 0 .. n - 1 ]\) of integers of \(w\) bits in \(n w\) bits plus the directories of rank and select, with the access, the rank and the select of any symbol in \(O( w )\) time.

Lemma 22.15 (the wavelet matrix). Let the level \(\ell\) of \(S\) hold the bit \(w - 1 - \ell\) of each item, the items passing to the next level stably sorted by that bit, the \(Z_\ell\) with a 0 first. Then the item at the place \(i\) of a level is at the place

\[ \mathrm{rank}_0( B_\ell , i ) \text{ if its bit is 0}, \qquad Z_\ell + \mathrm{rank}_1( B_\ell , i ) \text{ if it is 1} , \tag{22.16} \]

of the next one, and the items equal to \(c\) end consecutive, in the order of \(S\), at the last level.

Proof. A stable partition by a bit sends an item to the place given by the items with its bit before it, which is (22.16), and keeps the order among the items with the same bit. By induction on the levels, the items that share the first \(\ell\) bits stay consecutive, in the order of \(S\). Also, the place of the range of \(c\) at the last level depends on the bits of \(c\) alone. \(\square\)

Figure 22.11. The wavelet matrix of the sequence 4 7 6 5 3 2 1 0 2 1 4 1 of 3 bits: each level holds a bit of each item (the items above the bits, in the order of the level), the 0s first at the next level; the access to the item 2, the 6 = 110 (violet), moves to the places 9 and 11 by (22.16).

Hence access(), rank() and select() follow a place, or the two ends of a range, down the \(w\) levels by (22.16), or up by the select, in \(O( w )\) time (Figure 22.11); rank( c , i ) follows the places 0 and \(i\) down along the bits of \(c\), and the difference at the last level is the answer.

Furthermore, the \(k\)-th smallest item of a range, quantile( i , j , k ), goes down to the 0s or to the 1s according to how many 0s the range holds at each level, and countLess( i , j , c ) sums the 0s that the range leaves at the levels where \(c\) has a 1 (Algorithm 22.17). Instead, the wavelet tree of Grossi, Gupta and Vitter 2003 splits the alphabet in halves at its nodes, which need a pointer or an offset each. Our matrix keeps instead one vector of \(n\) bits per level and no tree, at the same costs, and it is arguably the form of choice for the large alphabets, and the base of the compressed indices of the integers (Navarro 2014 surveys the uses of the wavelet trees). Each level carries the directory of RankSelect, and the matrix therefore takes about \(1.5 \, n w\) bits, a query of rank being \(2 w\) ranks of one load and one sideways sum each.

Algorithm 22.17. The access, the rank, the select, the quantile and the count of the wavelet matrix (Claude, Navarro and Ordóñez 2015).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{access}( i ) \cr 2 & \quad c \gets 0 \cr 3 & \quad \textbf{for}\ \ell \gets 0\ \textbf{to}\ w - 1\ \textbf{do} \cr 4 & \qquad b \gets B_\ell[ i ];\ c \gets 2 c + b \cr 5 & \qquad \textbf{if}\ b = 1\ \textbf{then}\ i \gets Z_\ell + \mathrm{rank}_1( B_\ell , i )\ \textbf{else}\ i \gets \mathrm{rank}_0( B_\ell , i ) \cr 6 & \quad \textbf{return}\ c \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{rank}( c , i ) \cr 2 & \quad \textbf{if}\ c \ge 2^w\ \textbf{then return}\ 0 \cr 3 & \quad s \gets 0 \cr 4 & \quad \textbf{for}\ \ell \gets 0\ \textbf{to}\ w - 1\ \textbf{do} \cr 5 & \qquad \textbf{if}\ c_\ell = 1\ \textbf{then}\ s \gets Z_\ell + \mathrm{rank}_1( B_\ell , s );\ i \gets Z_\ell + \mathrm{rank}_1( B_\ell , i ) \cr 6 & \qquad \textbf{else}\ s \gets \mathrm{rank}_0( B_\ell , s );\ i \gets \mathrm{rank}_0( B_\ell , i ) \cr 7 & \quad \textbf{return}\ i - s \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{select}( c , k ) \cr 2 & \quad p \gets \text{the place of } c \text{ at the last level} + k - 1 \cr 3 & \quad \textbf{for}\ \ell \gets w - 1\ \textbf{downto}\ 0 \ \textbf{do} \cr 4 & \qquad \textbf{if}\ c_\ell = 1\ \textbf{then}\ p \gets \mathrm{select}_1( B_\ell , p - Z_\ell + 1 )\ \textbf{else}\ p \gets \mathrm{select}_0( B_\ell , p + 1 ) \cr 5 & \quad \textbf{return}\ p \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{quantile}( i , j , k ) \cr 2 & \quad c \gets 0 \cr 3 & \quad \textbf{for}\ \ell \gets 0\ \textbf{to}\ w - 1\ \textbf{do} \cr 4 & \qquad i_1 \gets \mathrm{rank}_1( B_\ell , i );\ j_1 \gets \mathrm{rank}_1( B_\ell , j );\ z \gets ( j - j_1 ) - ( i - i_1 ) \cr 5 & \qquad \textbf{if}\ k < z\ \textbf{then}\ c \gets 2 c;\ i \gets i - i_1;\ j \gets j - j_1\quad \triangleright\ \text{to the 0s} \cr 6 & \qquad \textbf{else}\ c \gets 2 c + 1;\ k \gets k - z;\ i \gets Z_\ell + i_1;\ j \gets Z_\ell + j_1 \cr 7 & \quad \textbf{return}\ c \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{countLess}( i , j , c ) \cr 2 & \quad \textbf{if}\ c \ge 2^w\ \textbf{then return}\ j - i \cr 3 & \quad r \gets 0 \cr 4 & \quad \textbf{for}\ \ell \gets 0\ \textbf{to}\ w - 1\ \textbf{while} \ i < j\ \textbf{do} \cr 5 & \qquad i_1 \gets \mathrm{rank}_1( B_\ell , i );\ j_1 \gets \mathrm{rank}_1( B_\ell , j ) \cr 6 & \qquad \textbf{if}\ c_\ell = 1\ \textbf{then}\ r \gets r + ( j - j_1 ) - ( i - i_1 );\ i \gets Z_\ell + i_1;\ j \gets Z_\ell + j_1 \cr 7 & \qquad \textbf{else}\ i \gets i - i_1;\ j \gets j - j_1 \cr 8 & \quad \textbf{return}\ r \end{array} \]

Lemma 22.16. For \(0 \le i < j \le n\) and \(k < j - i\), quantile( i , j , k ) returns the \(k\)-th smallest item of \(S[ i .. j - 1 ]\), from 0, and countLess( i , j , c ) the number of its items smaller than \(c\), each with \(2 w\) ranks.

Proof. By Lemma 22.15, before the level \(\ell\) the range \([ i , j )\) holds exactly the items of the original range whose first \(\ell\) bits are those chosen so far, the prefix \(c\) of the result. Line 4 computes the number \(z\) of those whose next bit is 0, which by (22.16) go to the range \([ i - i_1 , j - j_1 )\) of the next level, the others to \([ Z_\ell + i_1 , Z_\ell + j_1 )\). For the quantile, we keep the invariant that the answer is the \(k\)-th smallest item of the current range: all the items with the next bit 0 are smaller than those with the bit 1 and the same prefix, so that the answer has the bit 0 if and only if \(k < z\), and otherwise it is the \(( k - z )\)-th of the items with the bit 1. After \(w\) levels the prefix is the whole item. For the count, an item of the range is smaller than \(c\) if and only if, at the first bit where they differ, the item has 0 and \(c\) has 1. At a level where \(c\) has the bit 1, line 6 counts the items of the range with the bit 0, which agree with \(c\) on the bits before and are smaller, and follows those with the bit 1; where \(c\) has 0, the items with the bit 1 are larger and are dropped. The items equal to \(c\) are not counted. Each level costs two ranks. \(\square\)

A wavelet tree shaped by the code of Huffman (Mäkinen and Navarro 2005, HuffmanWaveletTree) takes \(n ( H_0 + 1 )\) bits instead of \(n w\), and it may be somewhat faster on a "skewed" alphabet, quite often the case of a text. We give the symbol \(c\) the canonical code of Huffman of its frequency, of length \(\ell_c\) (codeLength( c ), 0 for a symbol absent), with its bits from the highest. Our tree is the trie of the codes, and its internal node \(v\), reached by the prefix \(\pi_v\), keeps the bit after \(\pi_v\) of the code of each item whose code starts with \(\pi_v\), in the order of the sequence (Figure 22.12). We give the canonical codes by length and then by symbol, the first one 0, which is another convention than (21.5) of §21.2, with the same lengths. All the nodes have their bits in one vector \(B\) with rank and select, the node \(v\) from the place \(o_v\), with \(R_v = \mathrm{rank}_1( B , o_v )\) kept. An item of place \(i\) in the node \(v\) moves to the place

\[ i' = \mathrm{rank}_b( B , o_v + i ) - \mathrm{rank}_b( B , o_v ) \tag{22.17} \]

of its child by the bit \(b = B[ o_v + i ]\). A descent along the code of \(c\) gives access( i ), together with the rank of the symbol found (accessRank(), the LF-mapping of an FM-index in one descent). It also gives \(\mathrm{rank}_c( i )\), one rank a step, while \(\mathrm{select}_c( k )\) climbs from the leaf of \(c\) by one select a step, \(k' = \mathrm{select}_b( B , \mathrm{rank}_b( B , o_v ) + k ) - o_v + 1\) (Algorithm 22.18).

Figure 22.12. The wavelet tree of abracadabra shaped by the canonical code a 0, b 100, c 101, d 110, r 111 of its frequencies: each internal node keeps a bit for each item that reaches it (the items above the bits), and the bits of all the nodes are one vector, the nodes laid by levels.

Lemma 22.17. The bits of the nodes of HuffmanWaveletTree are \(\sum_c f_c \ell_c < n ( H_0 + 1 )\), for the frequencies \(f_c\) of the symbols.

Proof. An item of the symbol \(c\) leaves one bit in each of the \(\ell_c\) internal nodes on the code of \(c\). Hence the sum is \(n\) times the average length of the code of Huffman of the frequencies, which is below \(H_0 + 1\) by (21.4). \(\square\)

Beside the bits of \(B\), the tree takes the directory of rank and select, 25% of them with RankSelect and 3.5% with CompactRankSelect (the template parameter RS, time against bits), and \(O( \sigma )\) words of the nodes and of the codes. With withSelect false, the directory of RankSelect builds no inventory. This suits a tree that only ranks, such as the one of the FM-index of §21.11.

Algorithm 22.18. The construction, the access with the rank, the rank and the select of the wavelet tree of Huffman (Mäkinen and Navarro 2005).

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{build}( x ) \cr 2 & \quad f_c \gets \text{the occurrences of each } c \text{ in } x; \ \text{sort the symbols present by } f_c \cr 3 & \quad \textbf{repeat}\ \text{join the two lightest of the fronts of} \text{ the two queues into a node at the tail of the second} \cr 4 & \quad \textbf{until}\ \text{one node is left};\ \ell_c \gets \text{the depth of the leaf of } c \cr 5 & \quad \text{give the canonical codes, by length and then by symbol} \cr 6 & \quad \text{build the trie of the codes};\ \mathit{items}[ v ] \gets \text{the items whose code passes by } v \cr 7 & \quad \text{lay the nodes in } B \text{ by levels: } o_v \gets \text{the sum of } \mathit{items} \text{ of the nodes before} \cr 8 & \quad \textbf{foreach}\ c \in x \text{, in order}\ \textbf{do} \cr 9 & \qquad \textbf{foreach}\ \text{node } v \text{ on the code of } c \text{ and its bit } b \text{ there}\ \textbf{do} \cr 10 & \qquad\quad B[ \mathit{at}[ v ] ] \gets b;\ \mathit{at}[ v ] \gets \mathit{at}[ v ] + 1 \cr 11 & \quad R_v \gets \mathrm{rank}_1( B , o_v ) \text{ for each node } v \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{accessRank}( i ) \cr 2 & \quad v \gets \text{the root} \cr 3 & \quad \textbf{loop} \cr 4 & \qquad b \gets B[ o_v + i ];\ r \gets \mathrm{rank}_1( B , o_v + i ) - R_v \cr 5 & \qquad \textbf{if}\ b = 1\ \textbf{then}\ i \gets r\ \textbf{else} \ i \gets i - r \cr 6 & \qquad \textbf{if}\ \text{the child } b \text{ of } v \text{ is the} \text{ leaf of } c\ \textbf{then return}\ ( c , i ) \cr 7 & \qquad v \gets \text{the child } b \text{ of } v \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{rank}( c , i ) \cr 2 & \quad \textbf{if}\ c \text{ is not in the sequence }\ \textbf{then return}\ 0 \cr 3 & \quad v \gets \text{the root} \cr 4 & \quad \textbf{for}\ d \gets 0\ \textbf{to}\ \ell_c - 1\ \textbf{do} \cr 5 & \qquad r \gets \mathrm{rank}_1( B , o_v + i ) - R_v \cr 6 & \qquad \textbf{if}\ b_d = 1\ \textbf{then}\ i \gets r \ \textbf{else}\ i \gets i - r \cr 7 & \qquad v \gets \text{the child } b_d \text{ of } v \cr 8 & \quad \textbf{return}\ i \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{select}( c , k ) \cr 2 & \quad v_0 , \ldots , v_{\ell_c - 1} \gets \text{the nodes on the } \text{code } b_0 \cdots b_{\ell_c - 1} \text{ of } c \cr 3 & \quad \textbf{for}\ d \gets \ell_c - 1\ \textbf{downto}\ 0 \ \textbf{do} \cr 4 & \qquad \textbf{if}\ b_d = 1\ \textbf{then}\ p \gets \mathrm{select}_1( B , R_{v_d} + k ) \cr 5 & \qquad \textbf{else}\ p \gets \mathrm{select}_0( B , o_{v_d} - R_{v_d} + k ) \cr 6 & \qquad k \gets p - o_{v_d} + 1 \cr 7 & \quad \textbf{return}\ k - 1 \end{array} \]

Finally, the move structure of Nishimoto and Tabei 2021 (MoveStructure) represents a permutation \(\pi\) of \([ 0 , n )\) that shifts each of \(r\) intervals \([ p_i , p_{i+1} )\) alike, such as the LF-mapping of a transform of Burrows and Wheeler on its runs, or the function \(\phi\) of the r-index (§21.11). It keeps the starts \(p_i\), their images \(q_i\) and the interval \(d_i\) that holds \(q_i\), so that

\[ \pi( x ) = q_i + ( x - p_i ) , \qquad x \in [ p_i , p_{i+1} ) , \tag{22.18} \]

and the interval of \(\pi( x )\) is found from \(d_i\) forward, past the starts \(p_j \le \pi( x )\).

We say that the structure is balanced when no image \([ q_i , q_i + p_{i+1} - p_i )\) holds 4 starts or more. Its construction ensures it 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 (the cut may cascade), which is checked in turn (Algorithm 22.19). Then the intervals become at most \(2 r\) (Nishimoto and Tabei, for this balance), and the search forward takes at most 3 steps (Lemma 22.18 below); hence each step of a walk costs \(O( 1 )\) time, in \(O( r )\) words instead of the \(n\) of the permutation written in full. On the runs of the transform of abracadabra (cf. Table 21.7) the image of the run of a, the rows \([ 6 , 10 )\), is the rows \([ 2 , 6 )\), which hold the 4 starts 2, 3, 4 and 5; the balance cuts the run at the row 8 (Figure 22.13). We keep the intervals and the images in two ordered maps during the construction, \(O( r \log r )\) time, and each interval carries a tag (the symbol of its run), which its parts keep.

Figure 22.13. The LF-mapping of the transform ard$rcaaaabb of abracadabra as a move structure: each interval of rows (above, between the bars) is shifted alike onto its image (below). The run of a (violet) is cut at the row 8 by the balance (the orange bar), since its image \(\lbrack 2 , 6 )\) held 4 starts.

Algorithm 22.19. The balance and the move of Nishimoto and Tabei 2021.

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{balance}( I ) \cr 2 & \quad S \gets \text{the images of } I \cr 3 & \quad \textbf{while}\ S \ne \emptyset\ \textbf{do} \cr 4 & \qquad [ q , q + \lambda ) \gets \mathrm{pop}( S ) \text{, the image } \text{of } [ p , p + \lambda ) \cr 5 & \qquad \textbf{if}\ [ q , q + \lambda ) \text{ holds 4 starts or } \text{more of } P\ \textbf{then} \cr 6 & \qquad\quad t \gets \text{the third of them} - q \cr 7 & \qquad\quad \text{cut } [ p , p + \lambda ) \text{ into } [ p , p + t ) \text{ and } [ p + t , p + \lambda ) \text{, the tag kept} \cr 8 & \qquad\quad \mathrm{push}( S , [ q , q + t ) );\ \mathrm{push}( S , [ q + t , q + \lambda ) ) \cr 9 & \qquad\quad \mathrm{push}( S , \text{the image that holds the new } \text{start } p + t ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{move}( x , i ) \cr 2 & \quad y \gets q_i + ( x - p_i );\ j \gets d_i \cr 3 & \quad \textbf{while}\ p_{j+1} \le y\ \textbf{do}\ j \gets j + 1\quad \triangleright\ \text{at most 3 steps, by the balance} \cr 4 & \quad \textbf{return}\ ( y , j ) \end{array} \]

Lemma 22.18. If the structure is balanced, move( x , i ) with \(x \in [ p_i , p_{i+1} )\) returns \(\pi( x )\) and the interval that holds it after at most 3 iterations of line 3.

Proof. By (22.18), \(y = \pi( x )\) lies in the image \([ q_i , q_i + p_{i+1} - p_i )\), which starts in the interval \(d_i\). The loop moves \(j\) forward while the next start is at most \(y\), and stops at the interval that holds \(y\). Each start that it passes lies in \(( q_i , y ]\), inside the image, which holds at most 3 starts by the balance. \(\square\)

The bound of \(2 r\) on the intervals after the balance is the theorem of Nishimoto and Tabei 2021 for the cut of an image of 4 starts, which the construction of the library follows.

Table 22.4 summarizes the sequences of the area.

Table 22.4. The sequences and their costs.

Realization Space in bits Access Search
EliasFano \(n ( 2 + \lceil \log_2( u / n ) \rceil )\), plus the directory of \(H\) \(O( 1 )\) nextGEQ() in a \(\mathrm{select}_0\) and \(O( 1 + \log c )\) for a bucket of \(c\) items
PartitionedEliasFano at most that of Elias-Fano on each block of 128 items, plus a record per block a scan of the code of a block nextGEQ() by a search of the records and the scan of a block
LAVector (22.12) a lookup and a scan of the segments of \(2^t\) places nextGEQ() in \(O( w_j - \log_2 \alpha )\) once the segment is found
WaveletMatrix \(n w\), plus a directory per level \(O( w )\) rank, select, quantile and range counts in \(O( w )\)
HuffmanWaveletTree less than \(n ( H_0 + 1 )\), plus the directory and \(O( \sigma )\) words \(O( \ell_c )\), \(H_0 + 1\) on average rank and select of \(c\) in \(O( \ell_c )\)
MoveStructure \(O( r )\) words for a permutation of \(r\) intervals the image of a place and its interval in \(O( 1 )\) the interval of a place by a binary search

22.10 Graphs

A graph of \(n\) nodes and \(m\) edges, as sorted adjacency lists, is a set of \(m\) pairs among \(n^2\), i.e., \(\log_2 \binom{n^2}{m} \approx m \log_2( n^2 / m )\) bits for a graph with no regularity. EliasFanoGraph writes the edge \(( u , v )\) as the integer \(u n + v\). Its lists, each one sorted, are then one increasing sequence of \([ 0 , n^2 )\) coded by Theorem 22.2, and a second sequence of the prefix sums of the outdegrees gives where each list starts (Figure 22.14). This is the representation of the adjacency lists of large graphs in Unicorn (Curtiss et al. 2013) and in the quasi-succinct indices of Vigna 2013. Hence the outdegree and the \(i\)-th successor are accesses, in \(O( 1 )\) time, and an edge \(( u , v )\) is the test of nextGEQ( u n + v ) (Algorithm 22.20).

Figure 22.14. (a) The lists of a graph of 4 nodes as the sequence of the integers \(u n + v\) and the sequence of the starts of the lists; the list of 2 is the items 3 and 4 (violet). (b) The list of the node 16 of Boldi and Vigna 2004 coded by reference to that of the node 15: the copy bits of the reference (the items copied in violet), the extra nodes (orange), and the fields of its code with \(L_{\min} = 2\).

Algorithm 22.20. The construction of the graph in Elias-Fano.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{build}( a ) \cr 2 & \quad E \gets ();\ S \gets () \cr 3 & \quad \textbf{for}\ u \gets 0\ \textbf{to}\ n - 1\ \textbf{do} \cr 4 & \qquad \text{append } |E| \text{ to } S \cr 5 & \qquad \textbf{foreach}\ v \in a[ u ]\ \textbf{do}\ \text{append } u n + v \text{ to } E \cr 6 & \quad \text{append } |E| \text{ to } S \cr 7 & \quad \textbf{return}\ ( \text{Elias-Fano of } E \text{ in } [ 0 , n^2 ) , \text{Elias-Fano of } S \text{ in } [ 0 , |E| ] ) \end{array} \]

Lemma 22.19. Coding each list apart, in the universe of the list, takes

\[ \sum_u d_u \log_2 \frac{n}{d_u} \le m \log_2 \frac{n^2}{m} \tag{22.19} \]

bits beyond the \(2 m\) of the unary parts, \(d_u\) being the outdegree of \(u\).

Proof. By the concavity of the logarithm (the inequality of Jensen on the weights \(d_u / m\)), \(\sum_u ( d_u / m ) \log_2( n / d_u ) \le \log_2( \sum_u ( d_u / m ) ( n / d_u ) ) = \log_2( n^2 / m )\), the sum running over the \(u\) with \(d_u > 0\), which are at most \(n\). \(\square\)

Coded apart, the lists can thus take fewer bits when the degrees are skewed, at the price of a directory and an offset per list, the form that chapter 15 of Ferragina describes; the single sequence keeps one directory and the same \(O( 1 )\) access. Neither exploits the locality and the similarity of the lists of the Web, which the codes of Boldi and Vigna 2004 do. With the pages sorted by URL, most links stay in the host (locality), and the pages of a host link to the same pages (similarity). BVGraph codes the list of \(x\) as its outdegree, in \(\gamma\), followed by the reference \(r\): the list of \(x - r\), among the previous \(W\) lists, that shares the most successors with that of \(x\) (0 for none). Then comes the copy list of the reference, a bit per successor of \(x - r\) that records whether it is a successor of \(x\) too. It is written as copy blocks, i.e., its first bit and the lengths less 1 of its runs, the last one omitted since the outdegree of the reference implies it. Next come the successors not copied, the extra nodes. These are the runs of at least \(L_{\min}\) consecutive integers as intervals (each an Interval, its left extreme and its length), and the residuals as gaps less 1, the first ones of each relative to \(x\) by signedToNatural() (Algorithm 22.21).

Algorithm 22.21. The coding and the decoding of a list of BVGraph, and two of its steps (Boldi and Vigna 2004).

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{encode}( x , S ) \cr 2 & \quad \mathit{start}[ x ] \gets \text{the bits written so far}; \ \text{write } \gamma( |S| ) \cr 3 & \quad \textbf{if}\ S = ()\ \textbf{then return} \cr 4 & \quad b \gets \text{the } k \in [ 1 , \min\{ w , x \} ] \text{ with } \mathit{chain}[ x - k ] < r \text{ and the most items of } a[ x - k ] \text{ in } S \text{, 0 if none} \cr 5 & \quad \text{write } \gamma( b );\ E \gets S \cr 6 & \quad \textbf{if}\ b > 0\ \textbf{then} \cr 7 & \qquad ( f , \mathit{len} ) \gets \mathrm{copyBlocks}( \mathrm{copyList}( S , a[ x - b ] ) ) \cr 8 & \qquad \text{write } \gamma( |\mathit{len}| ) \text{, the bit } f \text{, and } \gamma( l ) \text{ for each } l \in \mathit{len} \cr 9 & \qquad E \gets S \setminus a[ x - b ];\ \mathit{chain}[ x ] \gets \mathit{chain}[ x - b ] + 1 \cr 10 & \quad ( I , \mathit{res} ) \gets \mathrm{intervals}( E , \mathit{lmin} );\ \text{write } \gamma( |I| ) \cr 11 & \quad \textbf{foreach}\ ( \mathit{left} , \mathit{len} ) \in I \ \textbf{do} \cr 12 & \qquad \text{write } \gamma( \zeta( \mathit{left} - x ) ) \text{ for the first, } \gamma( \mathit{left} - \mathit{right} - 2 ) \text{ for the others} \cr 13 & \qquad \text{write } \gamma( \mathit{len} - \mathit{lmin} ); \ \mathit{right} \gets \mathit{left} + \mathit{len} - 1 \cr 14 & \quad \textbf{foreach}\ g \in \mathrm{residualGaps}( \mathit{res} , x )\ \textbf{do}\ \text{write } \delta( g ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{successors}( x ) \cr 2 & \quad d \gets \text{the outdegree};\ \textbf{if}\ d = 0 \ \textbf{then return}\ () \cr 3 & \quad S \gets ();\ b \gets \text{the reference} \cr 4 & \quad \textbf{if}\ b > 0\ \textbf{then} \cr 5 & \qquad T \gets \mathrm{successors}( x - b );\ f \gets \text{the } \text{first bit} \cr 6 & \qquad \textbf{foreach}\ \text{block, of the length read or of the } \text{rest of } T \text{ for the last}\ \textbf{do} \cr 7 & \qquad\quad \textbf{if}\ f = 1\ \textbf{then}\ \text{append the } \text{next items of } T \text{ to } S\ \textbf{else}\ \text{skip } \text{them} \cr 8 & \qquad\quad f \gets 1 - f \cr 9 & \quad \textbf{foreach}\ \text{interval read}\ \textbf{do} \ \text{append its integers to } S \cr 10 & \quad \textbf{while}\ |S| < d\ \textbf{do}\ \text{append the next } \text{residual, from its gap, to } S \cr 11 & \quad \textbf{return}\ S \text{ sorted} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{copyBlocks}( c ) \cr 2 & \quad \textbf{if}\ c = ()\ \textbf{then return}\ ( 0 , () ) \cr 3 & \quad \mathit{len} \gets ();\ \mathit{run} \gets 1 \cr 4 & \quad \textbf{for}\ i \gets 1\ \textbf{to}\ |c| - 1\ \textbf{do} \cr 5 & \qquad \textbf{if}\ c[ i ] = c[ i - 1 ]\ \textbf{then} \ \mathit{run} \gets \mathit{run} + 1 \cr 6 & \qquad \textbf{else}\ \text{append } \mathit{run} - 1 \text{ to } \mathit{len};\ \mathit{run} \gets 1 \cr 7 & \quad \textbf{return}\ ( c[ 0 ] , \mathit{len} )\quad \triangleright\ \text{the last run omitted} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{intervals}( e , \mathit{lmin} ) \cr 2 & \quad I \gets ();\ \mathit{res} \gets ();\ i \gets 0 \cr 3 & \quad \textbf{while}\ i < |e|\ \textbf{do} \cr 4 & \qquad j \gets i + 1;\ \textbf{while}\ j < |e|\ \textbf{and}\ e[ j ] = e[ j - 1 ] + 1\ \textbf{do}\ j \gets j + 1 \cr 5 & \qquad \textbf{if}\ j - i \ge \mathit{lmin}\ \textbf{then} \ \text{append } ( e[ i ] , j - i ) \text{ to } I \cr 6 & \qquad \textbf{else}\ \text{append } e[ i .. j - 1 ] \text{ to } \mathit{res} \cr 7 & \qquad i \gets j \cr 8 & \quad \textbf{return}\ ( I , \mathit{res} ) \end{array} \]

A list is decoded from its place in the stream, kept for each node in an Elias-Fano sequence, after the list of its reference. Since the chains of references are at most \(R\) long, a list is decoded in \(O( R d )\) time for outdegrees up to \(d\). With the window \(W = 7\), the chains \(R = 3\) and \(L_{\min} = 4\) (the defaults of the WebGraph framework), the Web graphs usually take about 3 bits per edge, as Boldi and Vigna measure, against the \(\log_2 n\) bits of a plain list and the \(2 + \log_2( n^2 / m )\) of Elias-Fano. Also, the WebGraph framework codes the gaps by the \(\zeta\) codes, tuned to their power-law distribution, and reorders the nodes (e.g., by the layered label propagation of Boldi et al. 2011) to make the locality stronger; neither is in chapter 15 of Ferragina, nor in the library. The functions copyList(), copyBlocks(), intervals() and residualGaps() are the steps of the coding, given for the examples of that chapter.

The \(k^2\)-tree of Brisaboa, Ladra and Navarro 2014 (K2Tree) splits the adjacency matrix, padded to the side \(N = k^h \ge n\), into \(k^2\) submatrices of side \(N / k\). Each one is a child of the root, marked 1 if it has an edge and 0 otherwise, and each child marked 1 is split again, down to the cells. We write the marks by levels: \(T\) has those of all the levels but the last, and \(L\) those of the cells (Figure 22.15).

Lemma 22.20. The children of the node marked at the place \(p\) of \(T\) start at the place \(k^2 \, \mathrm{rank}_1( T , p + 1 )\) of \(T\) followed by \(L\).

Proof. Recall that the marks are written by levels, the \(k^2\) children of each node marked 1 in the order of the marks. Thus the children of the root take the places \(0 , \ldots , k^2 - 1\), and those of the \(j\)-th mark 1 of \(T\) come after the children of the root and of the \(j - 1\) marks 1 before it, i.e., they start at \(k^2 j\), with \(j = \mathrm{rank}_1( T , p + 1 )\). \(\square\)

Figure 22.15. The adjacency matrix of a graph of 8 nodes and 7 edges split by \(k = 2\) (the grey lines), and its marks by levels \(T\) and \(L\), in groups of \(k^2 = 4\); hasEdge( 5 , 5 ) follows the places 3, 8 and 23 (violet).

Hence no pointer is stored, as in LOUDS, and one can walk the tree by ranks only. The function hasEdge( u , v ) follows one path, in \(O( h )\) time. The function neighbors( u ) walks down the children that cross the row \(u\), \(k\) of the \(k^2\) at each level. Similarly, reverseNeighbors( v ) walks down those that cross the column \(v\), and the same bits therefore give the successors and the predecessors, which the lists give only by doubling them (Algorithm 22.22).

Algorithm 22.22. The construction of the \(k^2\)-tree by levels from the edges, the successors of a node, and the test of an edge (Brisaboa, Ladra and Navarro 2014).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{build}( n , E , k ) \cr 2 & \quad E \gets \text{the distinct edges, sorted};\ N \gets \text{the } \text{least power of } k \text{ not below } \max\{ n , k \} \cr 3 & \quad \mathit{level} \gets ( \text{the whole matrix with } E );\ s \gets N / k;\ T \gets ();\ L \gets () \cr 4 & \quad \textbf{while}\ \mathit{level} \ne ()\ \textbf{do} \cr 5 & \qquad \mathit{next} \gets () \cr 6 & \qquad \textbf{foreach}\ \text{submatrix } x \text{ of } \mathit{level} \text{, in order}\ \textbf{do} \cr 7 & \qquad\quad \text{split the edges of } x \text{ among its } k^2 \text{ children of side } s \text{, by counting} \cr 8 & \qquad\quad \textbf{for}\ j \gets 0\ \textbf{to}\ k^2 - 1 \ \textbf{do} \cr 9 & \qquad\qquad \beta \gets 1 \text{ if the child } j \text{ has an } \text{edge, else } 0 \cr 10 & \qquad\qquad \textbf{if}\ s = 1\ \textbf{then}\ L \gets L \cdot \beta\ \textbf{else}\ T \gets T \cdot \beta \cr 11 & \qquad\qquad \textbf{if}\ s > 1\ \textbf{and}\ \beta = 1 \ \textbf{then}\ \text{append the child } j \text{ to } \mathit{next} \cr 12 & \qquad \mathit{level} \gets \mathit{next};\ s \gets s / k \cr 13 & \quad \textbf{return}\ ( T , L ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{neighbors}( u ) \cr 2 & \quad \mathit{out} \gets ();\ \mathrm{walk}( N , u , 0 , 0 ); \ \textbf{return}\ \mathit{out} \cr 3 & \textbf{procedure}\ \mathrm{walk}( s , r , o , \mathit{base} ) \cr 4 & \quad c \gets s / k\quad \triangleright\ \text{the side of a child} \cr 5 & \quad \textbf{for}\ j \gets 0\ \textbf{to}\ k - 1\ \textbf{do}\quad \triangleright\ \text{the children that cross the row } r \cr 6 & \qquad p \gets \mathit{base} + \lfloor r / c \rfloor k + j \cr 7 & \qquad \textbf{if}\ \mathit{mark}( p ) = 1\ \textbf{then} \cr 8 & \qquad\quad \textbf{if}\ c = 1\ \textbf{then}\ \text{append } o + j \text{ to } \mathit{out} \cr 9 & \qquad\quad \textbf{else}\ \mathrm{walk}( c , r \bmod c , o + j c , \mathrm{rank}_1( p + 1 ) \, k^2 ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{hasEdge}( u , v ) \cr 2 & \quad s \gets N;\ \mathit{base} \gets 0 \cr 3 & \quad \textbf{loop} \cr 4 & \qquad c \gets s / k;\ p \gets \mathit{base} + \lfloor u / c \rfloor k + \lfloor v / c \rfloor \cr 5 & \qquad \textbf{if}\ \mathit{mark}( p ) = 0 \ \textbf{then return false} \cr 6 & \qquad \textbf{if}\ c = 1\ \textbf{then return true} \cr 7 & \qquad \mathit{base} \gets \mathrm{rank}_1( p + 1 ) \, k^2;\ u \gets u \bmod c;\ v \gets v \bmod c;\ s \gets c \end{array} \]

A row is read in \(O( \sqrt{m} )\) time on average for \(m\) edges spread uniformly, and in \(O( n )\) in the worst case. Each edge sets at most \(k^2\) marks per level, and below the level where the submatrices outnumber the edges these marks are distinct. This gives the bound \(k^2 m ( \log_{k^2}( n^2 / m ) + O( 1 ) )\) in the worst case, as Brisaboa, Ladra and Navarro prove, and possibly far fewer bits when the edges "cluster" and the empty submatrices are large, as in the Web graphs ordered by URL. A larger \(k\) gives fewer levels and faster queries, a smaller one fewer bits; the authors use a larger \(k\) at the top levels and a smaller one below (Brisaboa, Ladra and Navarro 2009). We build the tree from the edges, by levels, in \(O( m h )\) time, with no visit of the matrix, which the recursive construction of chapter 15 of Ferragina performs.

22.11 Parallel construction

All the structures built by a scan of their input are also built on the threads of an executor (ADS/parallel/Executor.h), with the same entries, bits and inventories as the sequential construction; a query thus gives the same answer whichever built the structure. In the directories of rank of RankSelect and CompactRankSelect, we cut the blocks into chunks of consecutive blocks. A first pass counts the 1s of each chunk, and the prefix sums of the counts give the 1s before each chunk, \(c_k\). A second pass writes the entries of each chunk from \(c_k\) on; these are those of the sequential scan, since the entry of a block depends only on the 1s before it (Algorithm 22.23). The counts of the top level are the \(c_k\) of the chunks that start a top block. Indeed, the chunks are a power of 2 of blocks below the size of a top block, which then holds whole chunks, or a multiple of it above; a top block that does not start a chunk lies in one, which writes its count. We write the size of the chunks and the copy and the count of their words once for both directories, and the entry of a block (or of a superblock) once for the sequential and the parallel construction of each. We build the inventories of select in two passes over the chunks: the first finds the places of the first bit of each group, and the second the offsets of the sampled bits from the place of their group, each sample found from the entry of its block by a select in a word. In all, the work is \(O( m / 64 )\) words, as in the sequential scan, plus the samples, and the depth is that of a chunk and of the prefix sums.

Algorithm 22.23. The parallel construction of the directories of RankSelect and of CompactRankSelect.

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{directory}( \mathit{ex} , W ) \cr 2 & \quad \textbf{foreach}\ \text{chunk } C_k\ \textbf{do in parallel} \ a_k \gets \text{the 1s of the words of } C_k \cr 3 & \quad c_0 \gets 0;\ c_{k + 1} \gets c_k + a_k \text{ for } k = 0 , \ldots , q - 2\quad \triangleright\ \text{the 1s before} \text{ each chunk} \cr 4 & \quad T[ j ] \gets c_k \text{ for the chunk } C_k \text{ that } \text{starts the top block } j \cr 5 & \quad \textbf{foreach}\ \text{chunk } C_k\ \textbf{do in parallel} \ \text{the entries of its blocks as in } \mathrm{directory}( W ) \text{, from } c = c_k \cr 6 & \quad \textbf{foreach}\ \text{value } b \text{ of the selects } s\ \textbf{do}\ \mathrm{inventory}( \mathit{ex} , b ) \text{ (if } \text{not } \mathit{Lazy} \text{)} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{directory}( \mathit{ex} , W ) \cr 2 & \quad \textbf{foreach}\ \text{chunk } C_k\ \textbf{do in parallel} \ a_k \gets \text{the 1s of the words of } C_k \cr 3 & \quad c_0 \gets 0;\ c_{k + 1} \gets c_k + a_k \text{ for } k = 0 , \ldots , q - 2 \cr 4 & \quad \textbf{foreach}\ \text{chunk } C_k\ \textbf{do in parallel} \cr 5 & \qquad \text{the entries of its superblocks from } c = c_k \text{, and its samples from the } \lceil c_k / 4096 \rceil \text{-th} \cr 6 & \quad \text{the closing samples, as in } \mathrm{directory}( W ) \end{array} \]

Lemma 22.21. The directories of Algorithm 22.23 are those of the sequential scan, with \(O( m / 64 )\) words of work besides the samples of select.

Proof. The entry of a block depends only on its words and on the 1s before it. The first pass counts the 1s of each chunk, and the prefix sums of the counts give the 1s before each chunk; the second pass, from that count, adds the 1s of the blocks of the chunk in order, as the sequential scan does from the start. A count of the top level is the number of the 1s before its top block, which is the \(c_k\) of the chunk that starts there. Indeed, the chunks are a power of 2 of blocks, so that a top block either holds whole chunks, the first of which starts at it, or lies inside one chunk, which writes its count while it scans. The first place of a group of select and the offsets of its sampled bits are functions of the bits, which the two passes over the chunks find from the entries by a select in a word (Lemma 22.2). Each pass reads each word \(O( 1 )\) times. \(\square\)

We build the wavelet matrix faster, also on one thread, by a property of its levels that lets one pass over the items write several levels.

Lemma 22.22 (the levels by the reversed prefixes). In the wavelet matrix of Lemma 22.15, let \(b_j( c )\) be the bit at the level \(\ell + j\) of the item \(c\), and

\[ \kappa_j( c ) = \sum_{i < j} 2^i \, b_i( c ) , \qquad 0 \le j \le k , \tag{22.20} \]

the bits of the levels \(\ell , \ldots , \ell + j - 1\) read from the last one. Then the order of the items at the level \(\ell + j\) is the stable sort of their order at the level \(\ell\) by \(\kappa_j\).

Proof. By Lemma 22.15, the order at the level \(\ell + j\) comes from the order at the level \(\ell\) by \(j\) stable partitions, by the bits \(b_0 , \ldots , b_{j-1}\) in this order. A sequence of stable partitions by the bits of a key, from the least significant to the most significant one, is the radix sort of the least significant digit first, which sorts stably by the key. Here the key has \(b_{j-1}\) as its most significant bit and \(b_0\) as its least significant one, i.e., it is \(\kappa_j\). \(\square\)

Hence the place of an item \(c\) at the level \(\ell + j\) is

\[ P_j[ \kappa_j( c ) ] + | \{ c' \text{ before } c \text{ at the level } \ell : \kappa_j( c' ) = \kappa_j( c ) \} | , \tag{22.21} \]

with \(P_j[ a ]\) the items whose key is below \(a\), and \(Z_{\ell + j}\) is the number of the items with \(b_j = 0\); both are sums of the counts of the \(2^k\) values of \(\kappa_k\), from which each \(\kappa_j = \kappa_k \bmod 2^j\) follows. One scan of the items in the order of the level \(\ell\) therefore writes the bits of the \(k\) levels \(\ell , \ldots , \ell + k - 1\) at the places (22.21), and moves the items to their order at the level \(\ell + k\). By contrast, the construction by the partitions of Lemma 22.15 moves them \(k\) times, once per level. With \(k \le 8\) this is \(\lceil w / 8 \rceil\) passes over the items instead of \(w\), the bits being written into \(2^k - 1\) streams, one per value of \(\kappa_j\) for each \(j < k\). We recognize here the sort by the prefixes of the bits of Dinklage, Ellert, Fischer, Kurpicz and Löbel 2021, applied to \(k\) levels at a time (Algorithm 22.24).

On several threads the items are cut into slices of at most \(2^{18}\) items, about four per thread, whose \(k\) levels, of 256 KB at most, stay in the second level of the cache while the slice writes them. Each slice writes the levels of its items at the places that the counts of its keys give by (22.21) within the slice. The levels are then gathered from the slices: each block of words of a level copies the runs of bits of the slices that fall in it, in the order (22.21) of the runs, and therefore no two threads write a word. This is the domain decomposition of Fuentes-Sepúlveda et al. 2017 and of Labeit, Shun and Blelloch 2017, with the merge of Dinklage et al.; the items move to the places (22.21) of the level \(\ell + k\) directly, since those of two slices never meet.

Algorithm 22.24. The construction of the wavelet matrix by the stable sorts by the prefixes of the bits, and the parallel construction of the wavelet tree of Huffman.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{build}( x , w ) \cr 2 & \quad \textbf{return}\ \mathrm{build}( \text{the calling thread} , x , w ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{build}( \mathit{ex} , x , w ) \cr 2 & \quad C \gets x;\ \ell \gets 0 \cr 3 & \quad \textbf{while}\ \ell < w\ \textbf{do} \cr 4 & \qquad k \gets \text{the levels of the pass, at most 8} \cr 5 & \qquad \textbf{foreach}\ \text{slice } X_s \text{ of } C \ \textbf{do in parallel}\ h_s[ a ] \gets | \{ c \in X_s : \kappa_k( c ) = a \} | \cr 6 & \qquad \textbf{for}\ j \gets 0\ \textbf{to}\ k\ \textbf{do} \ P_{j , s}[ a ] \gets \text{the items of } C \text{ with } \kappa_j < a \cr & \qquad\quad \text{or with } \kappa_j = a \text{ in the slices } \text{before } X_s \text{, by the sums of the } h \cr 7 & \qquad Z_{\ell + j} \gets \text{the items with } b_j = 0 \text{, for } j < k \cr 8 & \qquad \textbf{foreach}\ \text{slice } X_s\ \textbf{do in} \ \textbf{parallel} \cr 9 & \qquad\quad Q_{j , s}[ a ] \gets \text{the items of } X_s \text{ with } \kappa_j < a\quad \triangleright\ \text{places in} \text{ the slice} \cr 10 & \qquad\quad \textbf{foreach}\ c \in X_s \text{ in order} \ \textbf{do} \cr 11 & \qquad\qquad \textbf{for}\ j \gets 0\ \textbf{to}\ k - 1 \ \textbf{do}\ L_{s , j}[ Q_{j , s}[ \kappa_j( c ) ] ] \gets b_j( c );\ Q_{j , s}[ \kappa_j( c ) ] \gets Q_{j , s}[ \kappa_j( c ) ] + 1 \cr 12 & \qquad\qquad C'[ P_{k , s}[ \kappa_k( c ) ] ] \gets c; \ P_{k , s}[ \kappa_k( c ) ] \gets P_{k , s}[ \kappa_k( c ) ] + 1 \cr 13 & \qquad \textbf{foreach}\ \text{block of words of each } B_{\ell + j}\ \textbf{do in parallel} \cr 14 & \qquad\quad \text{copy into it the runs of the } L_{s , j} \text{ that fall in it, each at its place } P_{j , s} \cr 15 & \qquad C \gets C';\ \ell \gets \ell + k \cr 16 & \quad \textbf{return}\ \text{the levels } B_\ell \text{ with } \text{their directories, built on } \mathit{ex} \text{, and the } Z_\ell \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{build}( \mathit{ex} , x ) \cr 2 & \quad \textbf{foreach}\ \text{slice } X_s\ \textbf{do in parallel} \ h_s[ c ] \gets \text{the occurrences of each } c \text{ in } X_s \cr 3 & \quad f_c \gets \sum_s h_s[ c ];\ \text{the codes, the trie and } \text{the places } o_v \text{ as in } \mathrm{build}( x ) \cr 4 & \quad \mathit{at}_s[ v ] \gets o_v + \text{the items through } v \text{ in the slices before } X_s \text{, by the } h \cr 5 & \quad \textbf{foreach}\ \text{slice } X_s\ \textbf{do in parallel} \cr 6 & \qquad \textbf{foreach}\ c \in X_s \text{ in order and node } v \text{ on the code of } c \text{, with its bit } b\ \textbf{do} \cr 7 & \qquad\quad B[ \mathit{at}_s[ v ] ] \gets b;\ \mathit{at}_s[ v ] \gets \mathit{at}_s[ v ] + 1 \cr 8 & \quad \text{the directory of } B \text{ on } \mathit{ex};\ R_v \gets \mathrm{rank}_1( B , o_v ) \text{ for each node } v \end{array} \]

We build the wavelet tree of Huffman in slices too. Here the counts of the symbols of each slice give the place of each slice in each node of the trie of the codes, and each slice writes the bits of its items along their codes into a stream per node, with no item moved. A stream gathers its bits into a word and stores the word when it is full. The store is plain when the word is inside its range, and an atomic or when the word is at one of its ends, which it may share with the stream of another slice (the words are 0 at first, and only the 1s are written; cf. the class BitRuns of BitVector.h). On one thread the tree is built by the sequential scan, which writes each bit at its place. In all, the work is \(O( n w )\) bits, \(O( n w / 64 )\) words copied and \(O( n \lceil w / 8 \rceil )\) moves of items for the matrix, or \(O( \sum_c f_c \ell_c )\) bits for the tree, plus \(O( q 2^k )\) counts for \(q\) slices (\(O( q \sigma )\) for the tree, whose slices therefore hold at least \(\sigma\) items each), and the depth is that of a slice. The other parallel constructions of the literature (Shun 2015; Dinklage, Fischer, Kurpicz and Tarnowski 2023) trade the passes against the memory in other ways, and we leave the comparison to Appendix B.

22.12 The interface

We collect here, header by header, the declarations of the namespace ADS that a user calls in this chapter, without the contracts, the documentation and the members that only the implementation uses; each block points to the section that describes its functions, and the example at the end shows the main structures at work. The program of the example compiles against the headers as it stands, and its assertions hold.

BalancedParentheses.h (§22.8).

// declarations of <ADS/succinct/BalancedParentheses.h>
class BalancedParentheses
{
 public:
 static constexpr std::size_t nil = std::size_t( -1 );
 BalancedParentheses( void );
 explicit BalancedParentheses( BitVector b );
 std::size_t size( void ) const;
 bool operator[]( std::size_t i ) const;
 std::int64_t excess( std::size_t i ) const;
 std::size_t findClose( std::size_t i ) const;
 std::size_t forwardSearch( std::size_t i , std::int64_t d ) const;
 std::size_t findOpen( std::size_t j ) const;
 std::size_t enclose( std::size_t i ) const;
 const CompactRankSelect & bits( void ) const;
 std::size_t treeBits( void ) const;
 };

BitStream.h (§22.2).

// declarations of <ADS/succinct/BitStream.h>
class BitWriter
{
 public:
 BitWriter( void ) = default;
 std::size_t size( void ) const;
 void writeBit( bool b );
 void write( Word v , int len );
 void writeBinary( Word v , int len );
 void writeUnary( std::uint64_t q );
 const BitVector & bits( void ) const;
 BitVector release( void );
 };
class BitReader
{
 public:
 explicit BitReader( const BitVector & b , std::size_t p = 0 );
 std::size_t position( void ) const;
 void seek( std::size_t p );
 bool atEnd( void ) const;
 bool readBit( void );
 Word read( int len );
 Word readBinary( int len );
 std::uint64_t readUnary( void );
 };

BitVector.h (§22.11).

// declarations of <ADS/succinct/BitVector.h>
using Words = std::vector< Word , detail::LineAllocator< Word > >;
constexpr int selectInWord( Word x , int k );
template< class O , class T >
class SubscriptIterator;  // random access, *it reads ( *o )[ i ]
class BitVector
{
 public:
 BitVector( void ) = default;
 explicit BitVector( std::size_t n , bool b = false );
 explicit BitVector( std::string_view s );
 BitVector( std::span< const Word > w , std::size_t n );
 std::size_t size( void ) const;
 bool empty( void ) const;
 bool operator[]( std::size_t i ) const;
 void set( std::size_t i , bool b = true );
 void push_back( bool b );
 void append( Word v , int len );
 Word get( std::size_t i , int len ) const;
 void put( std::size_t i , Word v , int len );
 std::size_t count( void ) const;
 const Words & words( void ) const;
 std::string toString( void ) const;
 void reserve( std::size_t n );
 void clear( void );
 using const_iterator = SubscriptIterator< BitVector , bool >;
 const_iterator begin( void ) const;
 const_iterator end( void ) const;
 };

BPTree.h (§22.8).

// declarations of <ADS/succinct/BPTree.h>
class BPTree
{
 public:
 static constexpr std::size_t nil = std::size_t( -1 );
 BPTree( void ) = default;
 explicit BPTree( const std::vector< std::vector< std::size_t > > & c );
 explicit BPTree( BitVector b );
 std::size_t size( void ) const;
 std::size_t root( void ) const;
 std::size_t parent( std::size_t v ) const;
 std::size_t leftmostChild( std::size_t v ) const;
 std::size_t rightSibling( std::size_t v ) const;
 std::size_t degree( std::size_t v ) const;
 std::size_t subtreeSize( std::size_t v ) const;
 std::size_t depth( std::size_t v ) const;
 bool isAncestor( std::size_t u , std::size_t v ) const;
 bool isLeaf( std::size_t v ) const;
 const BalancedParentheses & parentheses( void ) const;
 };

BVGraph.h (§22.10).

// declarations of <ADS/succinct/BVGraph.h>
class BVGraph
{
 public:
 using List = std::vector< std::size_t >;
 using Interval = std::pair< std::size_t , std::size_t >;
 BVGraph( void ) = default;
 explicit BVGraph( const std::vector< List > & a , std::size_t w = 7 ,
                   std::size_t r = 3 , std::size_t lmin = 4 );
 std::size_t order( void ) const;
 std::size_t edges( void ) const;
 std::size_t outdegree( std::size_t x ) const;
 List successors( std::size_t x ) const;
 std::size_t reference( std::size_t x ) const;
 std::size_t codeBits( void ) const;
 std::size_t sizeInBits( void ) const;
 static BitVector copyList( const List & s , const List & ref );
 static std::pair< bool , std::vector< std::size_t > >
 copyBlocks( const BitVector & c );
 static std::pair< std::vector< Interval > , List >
 intervals( const List & e , std::size_t lmin );
 static std::vector< std::uint64_t > residualGaps( const List & res ,
                                                   std::size_t x );
 };

CompactRankSelect.h (§22.1).

// declarations of <ADS/succinct/CompactRankSelect.h>
class CompactRankSelect
{
 public:
 CompactRankSelect( void );
 explicit CompactRankSelect( BitVector b );
 CompactRankSelect( std::span< const Word > w , std::size_t n );
 template< Executor E >
 CompactRankSelect( E & ex , BitVector b );
 template< Executor E >
 CompactRankSelect( E & ex , std::span< const Word > w , std::size_t n );
 const BitVector & bits( void ) const;
 std::size_t size( void ) const;
 bool operator[]( std::size_t i ) const;
 std::size_t ones( void ) const;
 std::size_t zeros( void ) const;
 std::size_t rank1( std::size_t i ) const;
 std::size_t rank0( std::size_t i ) const;
 std::size_t select1( std::size_t k ) const;
 std::size_t select0( std::size_t k ) const;
 std::size_t directoryBits( void ) const;
 using const_iterator = SubscriptIterator< CompactRankSelect , bool >;
 const_iterator begin( void ) const;
 const_iterator end( void ) const;
 };

EliasFanoGraph.h (§22.10).

// declarations of <ADS/succinct/EliasFanoGraph.h>
class EliasFanoGraph
{
 public:
 EliasFanoGraph( void ) = default;
 explicit EliasFanoGraph(
   const std::vector< std::vector< std::size_t > > & a );
 std::size_t order( void ) const;
 std::size_t edges( void ) const;
 std::size_t outdegree( std::size_t u ) const;
 std::size_t successor( std::size_t u , std::size_t i ) const;
 std::vector< std::size_t > successors( std::size_t u ) const;
 bool hasEdge( std::size_t u , std::size_t v ) const;
 std::size_t sizeInBits( void ) const;
 };

EliasFano.h (§22.6).

// declarations of <ADS/succinct/EliasFano.h>
template< bool Lazy >
class BasicEliasFano
{
 public:
 BasicEliasFano( void ) = default;
 explicit BasicEliasFano( const std::vector< std::uint64_t > & x );
 BasicEliasFano( const std::vector< std::uint64_t > & x , std::uint64_t u );
 std::size_t size( void ) const;
 bool empty( void ) const;
 std::uint64_t universe( void ) const;
 std::uint64_t access( std::size_t i ) const;
 std::uint64_t operator[]( std::size_t i ) const;
 std::size_t nextGEQ( std::uint64_t x ) const;
 bool contains( std::uint64_t x ) const;
 int lowWidth( void ) const;
 const BitVector & low( void ) const;
 const BasicRankSelect< Lazy > & high( void ) const;
 std::size_t codeBits( void ) const;
 std::size_t sizeInBits( void ) const;
 std::vector< std::uint64_t > decode( void ) const;
 using const_iterator = SubscriptIterator< BasicEliasFano , std::uint64_t >;
 const_iterator begin( void ) const;
 const_iterator end( void ) const;
 };
using EliasFano = BasicEliasFano< false >;
using LazyEliasFano = BasicEliasFano< true >;

HuffmanWaveletTree.h (§22.6).

// declarations of <ADS/succinct/HuffmanWaveletTree.h>
template< class RS = RankSelect >
class HuffmanWaveletTree
{
 public:
 HuffmanWaveletTree( void ) = default;
 explicit HuffmanWaveletTree( std::span< const std::uint32_t > x ,
                              bool withSelect = true );
 template< Executor E >
 HuffmanWaveletTree( E & ex , std::span< const std::uint32_t > x ,
                     bool withSelect = true );
 std::size_t size( void ) const;
 bool empty( void ) const;
 std::size_t sigma( void ) const;
 std::uint32_t access( std::size_t i ) const;
 std::uint32_t operator[]( std::size_t i ) const;
 std::pair< std::uint32_t , std::size_t > accessRank( std::size_t i ) const;
 std::size_t rank( std::uint32_t c , std::size_t i ) const;
 std::pair< std::size_t , std::size_t > rank( std::uint32_t c , std::size_t i ,
                                             std::size_t j ) const;
 std::size_t select( std::uint32_t c , std::size_t k ) const;
 int codeLength( std::uint32_t c ) const;
 std::size_t sizeInBits( void ) const;
 };

InterleavedRankSelect.h (§22.1).

// declarations of <ADS/succinct/InterleavedRankSelect.h>
class InterleavedRankSelect
{
 public:
 InterleavedRankSelect( void );
 explicit InterleavedRankSelect( const BitVector & b );
 InterleavedRankSelect( std::span< const Word > w , std::size_t n );
 std::size_t size( void ) const;
 std::size_t ones( void ) const;
 std::size_t zeros( void ) const;
 bool operator[]( std::size_t i ) const;
 std::size_t rank1( std::size_t i ) const;
 std::size_t rank0( std::size_t i ) const;
 std::size_t select1( std::size_t k ) const;
 std::size_t select0( std::size_t k ) const;
 std::size_t directoryBits( void ) const;
 };

JacobsonTree.h (§22.8).

// declarations of <ADS/succinct/JacobsonTree.h>
class JacobsonTree
{
 public:
 static constexpr std::size_t nil = std::size_t( -1 );
 JacobsonTree( void );
 explicit JacobsonTree(
   const std::vector< std::pair< std::size_t , std::size_t > > & c );
 explicit JacobsonTree( BitVector b );
 std::size_t size( void ) const;
 std::size_t root( void ) const;
 std::size_t left( std::size_t v ) const;
 std::size_t right( std::size_t v ) const;
 std::size_t parent( std::size_t v ) const;
 bool isLeaf( std::size_t v ) const;
 const BitVector & bits( void ) const;
 };

K2Tree.h (§22.10).

// declarations of <ADS/succinct/K2Tree.h>
class K2Tree
{
 public:
 using Edge = std::pair< std::size_t , std::size_t >;
 K2Tree( void ) = default;
 K2Tree( std::size_t n , const std::vector< Edge > & e , std::size_t k = 2 );
 std::size_t order( void ) const;
 std::size_t edges( void ) const;
 std::vector< std::size_t > neighbors( std::size_t u ) const;
 std::vector< std::size_t > reverseNeighbors( std::size_t v ) const;
 bool hasEdge( std::size_t u , std::size_t v ) const;
 const BitVector & levels( void ) const;
 const BitVector & leaves( void ) const;
 std::size_t sizeInBits( void ) const;
 };

LAVector.h (§22.6).

// declarations of <ADS/succinct/LAVector.h>
class LAVector
{
 public:
 LAVector( void ) = default;
 explicit LAVector( const std::vector< std::uint64_t > & x , int c = 7 );
 static LAVector tuned( const std::vector< std::uint64_t > & x );
 std::size_t size( void ) const;
 bool empty( void ) const;
 int correctionBits( void ) const;
 std::size_t segments( void ) const;
 std::uint64_t access( std::size_t i ) const;
 std::uint64_t operator[]( std::size_t i ) const;
 std::uint64_t select( std::size_t k ) const;
 std::size_t nextGEQ( std::uint64_t x ) const;
 std::size_t rank( std::uint64_t x ) const;
 bool contains( std::uint64_t x ) const;
 std::size_t correctionsInBits( void ) const;
 std::size_t sizeInBits( void ) const;
 std::vector< std::uint64_t > decode( void ) const;
 using const_iterator = SubscriptIterator< LAVector , std::uint64_t >;
 const_iterator begin( void ) const;
 const_iterator end( void ) const;
 };

LoudsTree.h (§22.8).

// declarations of <ADS/succinct/LoudsTree.h>
class LoudsTree
{
 public:
 static constexpr std::size_t nil = std::size_t( -1 );
 LoudsTree( void );
 explicit LoudsTree( const std::vector< std::vector< std::size_t > > & c );
 explicit LoudsTree( BitVector b );
 std::size_t size( void ) const;
 std::size_t root( void ) const;
 std::size_t degree( std::size_t v ) const;
 std::size_t parent( std::size_t v ) const;
 std::size_t leftmostChild( std::size_t v ) const;
 std::size_t rightSibling( std::size_t v ) const;
 std::size_t child( std::size_t v , std::size_t i ) const;
 bool isLeaf( std::size_t v ) const;
 const BitVector & bits( void ) const;
 };

MoveStructure.h (§22.10).

// declarations of <ADS/succinct/MoveStructure.h>
class MoveStructure
{
 public:
 MoveStructure( void ) = default;
 MoveStructure( std::span< const std::uint64_t > p ,
                std::span< const std::uint64_t > q ,
                std::span< const std::uint32_t > tag , std::uint64_t n );
 std::size_t intervals( void ) const;
 std::uint64_t size( void ) const;
 std::uint64_t start( std::size_t i ) const;
 std::uint32_t tag( std::size_t i ) const;
 std::pair< std::uint64_t , std::size_t > move( std::uint64_t x ,
                                               std::size_t i ) const;
 std::size_t interval( std::uint64_t x ) const;
 std::size_t sizeInBits( void ) const;
 };

PackedArray.h (§22.2).

// declarations of <ADS/succinct/PackedArray.h>
template< unsigned B , bool Saturate = false >
class PackedArray
{
 public:
 using Word = std::uint64_t;
 static constexpr std::size_t PER = 64 / B;
 static constexpr Word MAX = ( Word( 1 ) << B ) - 1;
 PackedArray( void ) = default;
 explicit PackedArray( std::size_t n , Word v = 0 );
 template< Executor E , class F >
 PackedArray( E & ex , std::size_t n , F && f );
 std::size_t size( void ) const;
 bool empty( void ) const;
 Word get( std::size_t i ) const;
 Word operator[]( std::size_t i ) const;
 bool set( std::size_t i , Word v );
 void push_back( Word v );
 std::size_t clamped( void ) const;
 const std::vector< Word > & words( void ) const;
 std::size_t bytes( void ) const;
 friend bool operator==( const PackedArray & a , const PackedArray & b );
 };
class TritArray
{
 public:
 TritArray( void ) = default;
 explicit TritArray( std::size_t n , unsigned v = 0 );
 template< Executor E , class F >
 TritArray( E & ex , std::size_t n , F && f );
 std::size_t size( void ) const;
 bool empty( void ) const;
 unsigned get( std::size_t i ) const;
 unsigned operator[]( std::size_t i ) const;
 void set( std::size_t i , unsigned v );
 void push_back( unsigned v );
 const std::vector< std::uint8_t > & data( void ) const;
 std::size_t bytes( void ) const;
 friend bool operator==( const TritArray & a , const TritArray & b );
 };

PartitionedEliasFano.h (§22.6).

// declarations of <ADS/succinct/PartitionedEliasFano.h>
class PartitionedEliasFano
{
 public:
 PartitionedEliasFano( void ) = default;
 explicit PartitionedEliasFano( std::span< const std::uint64_t > x );
 PartitionedEliasFano( std::span< const std::uint64_t > x , std::uint64_t u );
 std::size_t size( void ) const;
 bool empty( void ) const;
 std::uint64_t universe( void ) const;
 std::uint64_t access( std::size_t i ) const;
 std::uint64_t operator[]( std::size_t i ) const;
 std::size_t nextGEQ( std::uint64_t x ) const;
 bool contains( std::uint64_t x ) const;
 std::array< std::size_t , 3 > kinds( void ) const;
 std::size_t sizeInBits( void ) const;
 using const_iterator =
   SubscriptIterator< PartitionedEliasFano , std::uint64_t >;
 const_iterator begin( void ) const;
 const_iterator end( void ) const;
 };

RankSelect.h (§22.1).

// declarations of <ADS/succinct/RankSelect.h>
struct RankSelectOptions
{
 enum class Selects { NONE , ONES , ZEROS , BOTH };
 };
template< bool Lazy >
class BasicRankSelect : public RankSelectOptions
{
 public:
 BasicRankSelect( void );
 explicit BasicRankSelect( BitVector b , Selects s = Selects::BOTH );
 BasicRankSelect( std::span< const Word > w , std::size_t n ,
                  Selects s = Selects::BOTH );
 template< Executor E >
 BasicRankSelect( E & ex , BitVector b , Selects s = Selects::BOTH );
 template< Executor E >
 BasicRankSelect( E & ex , std::span< const Word > w , std::size_t n ,
                  Selects s = Selects::BOTH );
 const BitVector & bits( void ) const;
 std::size_t size( void ) const;
 bool operator[]( std::size_t i ) const;
 std::size_t ones( void ) const;
 std::size_t zeros( void ) const;
 std::size_t rank1( std::size_t i ) const;
 std::size_t rank0( std::size_t i ) const;
 std::size_t select1( std::size_t k ) const;
 std::size_t select0( std::size_t k ) const;
 std::size_t directoryBits( void ) const;
 using const_iterator = SubscriptIterator< BasicRankSelect , bool >;
 const_iterator begin( void ) const;
 const_iterator end( void ) const;
 };
using RankSelect = BasicRankSelect< false >;
using LazyRankSelect = BasicRankSelect< true >;

RRRBitVector.h (§22.1).

// declarations of <ADS/succinct/RRRBitVector.h>
class RRRBitVector
{
 public:
 RRRBitVector( void );
 explicit RRRBitVector( const BitVector & b );
 std::size_t size( void ) const;
 std::size_t ones( void ) const;
 std::size_t zeros( void ) const;
 bool operator[]( std::size_t i ) const;
 std::size_t rank1( std::size_t i ) const;
 std::size_t rank0( std::size_t i ) const;
 std::size_t select1( std::size_t k ) const;
 std::size_t select0( std::size_t k ) const;
 std::size_t sizeInBits( void ) const;
 };

WaveletMatrix.h (§22.6).

// declarations of <ADS/succinct/WaveletMatrix.h>
class WaveletMatrix
{
 public:
 WaveletMatrix( void ) = default;
 explicit WaveletMatrix( std::span< const std::uint64_t > x , int w = 0 );
 template< Executor E >
 WaveletMatrix( E & ex , std::span< const std::uint64_t > x , int w = 0 );
 template< class U >
  requires( std::is_same_v< U , std::uint8_t > ||
            std::is_same_v< U , std::uint16_t > ||
            std::is_same_v< U , std::uint32_t > )
 explicit WaveletMatrix( std::span< const U > x , int w = 0 );
 template< Executor E , class U >
  requires( std::is_same_v< U , std::uint8_t > ||
            std::is_same_v< U , std::uint16_t > ||
            std::is_same_v< U , std::uint32_t > )
 WaveletMatrix( E & ex , std::span< const U > x , int w = 0 );
 std::size_t size( void ) const;
 bool empty( void ) const;
 int width( void ) const;
 std::uint64_t access( std::size_t i ) const;
 std::uint64_t operator[]( std::size_t i ) const;
 std::size_t rank( std::uint64_t c , std::size_t i ) const;
 std::size_t select( std::uint64_t c , std::size_t k ) const;
 std::uint64_t quantile( std::size_t i , std::size_t j , std::size_t k ) const;
 std::size_t countLess( std::size_t i , std::size_t j ,
                        std::uint64_t c ) const;
 std::size_t sizeInBits( void ) const;
 using const_iterator = SubscriptIterator< WaveletMatrix , std::uint64_t >;
 const_iterator begin( void ) const;
 const_iterator end( void ) const;
 };
#include "ADS/succinct/BPTree.h"
#include "ADS/succinct/EliasFano.h"
#include "ADS/succinct/RankSelect.h"
#include "ADS/succinct/WaveletMatrix.h"
#include <cassert>

int main( void )
{
 const ADS::RankSelect b( ADS::BitVector( "0110100111" ) );  // bit 0 first
 assert( ( b.rank1( 5 ) == 3 ) && ( b.select1( 3 ) == 4 ) );
 const ADS::EliasFano ef( { 3 , 4 , 7 , 13 , 14 , 15 , 21 , 43 } );
 assert( ( ef.access( 3 ) == 13 ) && ( ef[ ef.nextGEQ( 16 ) ] == 21 ) );
 const std::vector< std::uint64_t > x = { 3 , 1 , 4 , 1 , 5 , 9 , 2 , 6 };
 const ADS::WaveletMatrix wm( x );
 assert( ( wm.rank( 1 , 4 ) == 2 ) && ( wm.quantile( 2 , 6 , 0 ) == 1 ) );
 const ADS::BPTree t( { { 1 , 2 } , { 3 } , {} , {} } );  // the children
 assert( ( t.degree( t.root() ) == 2 ) && ( t.subtreeSize( t.root() ) == 4 ) );
 }

22.13 Discussion and references

The rank and the select in \(o( m )\) bits are those of Jacobson 1989 and Clark 1996, and the compressed vector that of Raman, Raman and Rao 2007; the book of Navarro 2016 treats them, with the trees, the sequences and the graphs, in the form that the practice uses. Our directories follow the engineering of Vigna 2008, Gog and Petri 2014, Zhou, Andersen and Kaminsky 2013, Kurpicz 2022 and Laws et al. 2024, and the representation of Elias 1974 and Fano is that of Vigna 2013, with its partitioned form by Ottaviano and Venturini 2014 and the learned one by Boffa, Ferragina and Vinciguerra 2021. As for the trees, those by parentheses are due to Munro and Raman 2001 on the range min-max tree of Navarro and Sadakane 2014, and the wavelet structures those of Grossi, Gupta and Vitter 2003, Mäkinen and Navarro 2005 and Claude, Navarro and Ordóñez 2015. Finally, the graphs are those of Boldi and Vigna 2004 and Brisaboa, Ladra and Navarro 2014, and the move structure that of Nishimoto and Tabei 2021. Chapter 15 of Ferragina 2023 is the source of the structures of the book. Our chapter departs from it where the code departs, as remarked in place: the places from 0, the 1s and the 0s of \(H\) as in its chapter 11, the construction of the \(k^2\)-tree from the edges, and the single sequence of the edges of EliasFanoGraph.

The structures share the design of the practice, not that of the analysis. Indeed, the tables of the small blocks give way to the sideways sum and to the broadword select of a word, the levels of the directories have constant sizes chosen for the lines of the cache, and the space is a constant fraction of \(m\) instead of \(o( m )\). How much each choice costs or gains, against the libraries of reference (e.g., the SDSL of Gog, Beller, Moffat and Petri 2014), is measured by the campaign of Appendix B, and no number is given here.

All the structures of this chapter are persistent in the sense of §23.7. Hence store() writes one of them to a file, a stream or a buffer, restore() reads it back, and restoreMapped() opens a file in place, with the words of the vectors of bits, the directories of rank and select and the levels of the wavelet matrices as views over the mapping (in \(O( 1 )\) time, by Lemma 23.15). Since the words of a BitVector start on a line of the cache in the file as in memory, a mapped directory is read by the same kernels as one built in memory; some small arrays (the top counts and the places of the groups of select) are copied instead, which usually costs a fraction of a percent of the bits. In the archives of cereal a BitVector is written as the bit_vector of sdsl-lite (Gog et al. 2014), and each of the two libraries may read the vectors of bits of the other.

22.14 Exercises

Each exercise names the test of the library that solves it (run it with ctest -R <name>).

  1. Realize a vector of bits packed in words, with the bits past the size kept at 0, the append and the read of a field of up to 64 bits. Test: pearls_succinct.bit-vector.
  2. Find the place of the \(k\)-th 1 of a word by the broadword method of Lemma 22.2. Test: pearls_succinct.select-in-word.
  3. Realize the streams of bits with the binary fields read from the most significant bit and the unary codes read a word at a time. Test: pearls_succinct.bit-stream.
  4. Realize the directory of rank with the blocks of 256 bits and the inventories of select, eager and lazy, also from words in memory and above \(2^{40}\) bits. Tests: pearls_succinct.rank-select, engineered_succinct.rank-select-lazy, engineered_succinct.rank-select-words, succinct_top.rank-select-top, succinct_top.rank-select-words-top.
  5. Realize the flat directory of §22.4 and the one with the counts inside the lines. Tests: engineered_succinct.compact-rank-select, engineered_succinct.interleaved-rank-select.
  6. Realize the compressed vector of Theorem 22.1, with the offsets of the combinatorial number system. Test: engineered_succinct.rrr-bit-vector.
  7. Realize Elias-Fano with access() and nextGEQ() (Lemma 22.8), its partitioned form, and the LA-vector. Tests: pearls_succinct.elias-fano, engineered_succinct.partitioned-elias-fano, engineered_succinct.la-vector.
  8. Realize the arrays of fields of \(B\) bits, saturated or not, and the arrays of trits five to a byte, built on several threads. Tests: engineered_search.packed-array, engineered_search.trit-array.
  9. Realize the binary tree of Jacobson, the tree of LOUDS (Lemma 22.12), the balanced parentheses with the range min-max tree and the tree on them. Tests: pearls_succinct.jacobson-tree, pearls_succinct.louds-tree, pearls_succinct.balanced-parentheses, pearls_succinct.bp-tree.
  10. Realize the wavelet matrix with the quantiles and the counts of a range, and the wavelet tree of Huffman. Tests: engineered_succinct.wavelet-matrix, engineered_succinct.huffman-wavelet-tree.
  11. Realize the move structure with the balance of Nishimoto and Tabei. Test: engineered_succinct.move-structure.
  12. Realize the graph in Elias-Fano, the codes of Boldi and Vigna on the lists of Figure 22.14, and the \(k^2\)-tree. Tests: pearls_succinct.elias-fano-graph, pearls_succinct.bv-graph, pearls_succinct.k2-tree.
  13. Build the directories of rank and select, the wavelet matrix and the wavelet tree of Huffman on several threads, with the same bits as the sequential construction. Tests: engineered_parallel.parallel-rank-select, succinct_top.parallel-rank-select-top, engineered_parallel.parallel-wavelet-matrix, engineered_parallel.parallel-huffman-wavelet-tree.