This package provides a number of implementations of rank/select queries for bits vectors. Ranking is counting the number of ones in an initial segment of a bit vector. Selection is finding the position of the rth one. Both operation can be performed in constant time on an array of n bits using o(n) additional bits, but in practice linear data structures with small constants and theoretically nonconstant time work much better. Sux4J proposes a number of new, very efficient implementation of rank and select oriented to 64bit processors (in other words: they will be fairly slow on 32bit processors). The implementations are based on broadword programming and described in Sebastiano Vigna, “Broadword Implementation of Rank/Select Queries”, in Proc. of the 7th International Workshop on Experimental Algorithms, WEA 2008, volume 5038 of Lecture Notes in Computer Science, pages 154−168. Springer, 2008.
For dense arrays, Rank9
is the basic rank implementation; Rank16
is
slightly slower but occupies much less space. Selection can be performed
using SimpleSelect
for reasonably uniform bit arrays,
or using Select9
, which occupies more space
but guarantees practical constanttime evaluation.
For sparse arrays (e.g., representation of pointers in a bitstream)
we provide SparseRank
and
SparseSelect
. Their main
feature is that they do not require the original bit array, as they use
an EliasFanoMonotoneLongBigList
to implement a succint dictionary containing the positions of bits set. If the bit array
is sufficiently sparse, such a representation provides significant gains in space occupancy.
All structures can be serialised. Since in some cases the original bit vector is stored inside the structure, to
avoid saving and loading twice the same vector we suggest to pack all structures into a RankSelect
instance.
Interface  Description 

BalancedParentheses 
A data structure providing primitives for balanced parentheses
represented in a bit array.

Rank 
A data structure providing ranking over a bit array.

Select 
A data structure providing selection over a bit array.

SelectZero 
A data structure providing zero selection over a bit array.

Class  Description 

AbstractRank 
An abstract implementation of
Rank providing a few obvious derived methods. 
HintedBsearchSelect 
A hinted binarysearch select implementation.

JacobsonBalancedParentheses 
An implementation of Jacobson's balanced parentheses data structure.

Rank11 
A
rank11 implementation. 
Rank16 
A
rank16 implementation. 
Rank9 
A
rank9 implementation. 
RankSelect 
A serialisationoriented container for associated rank/select(zero) structures.

Select9 
A
select9 implementation. 
SimpleSelect 
A simple select implementation based on a twolevel inventory, a spill list and broadword bit search.

SimpleSelectZero 
A simple zeroselect implementation based on a twolevel inventory, a spill list and broadword bit search.

SparseRank 
A rank implementation for sparse bit arrays based on the Elias–Fano representation of monotone functions.

SparseSelect 
A select implementation for sparse bit arrays based on the Elias–Fano representation of monotone functions.
