IndexableBitVectors

This package exports following operations over bit vectors with extremely fast speed while keeping extra memory usage small:

• getindex(bv::IndexableBitVectors, i::Integer): i-th element of bv
• rank(b::Bool, bv::AbstractIndexableBitVector, i::Integer): the number of occurrences of bit b in bv[1:i]
• select(b::Bool, bv::AbstractIndexableBitVector, i::Integer): the index of i-th occurrence of b in bv.

And other shortcuts:

• rank0(bv, i) = rank(false, bv, i)
• rank1(bv, i) = rank(true, bv, i)
• select0(bv, i) = select(0, bv, i)
• select1(bv, i) = select(1, bv, i)

The following two types are exported:

• SucVector: rank values are precomputed in blocks.
• RRR: compressible indexable bit vector.

In general, queries on SucVector is faster than those on RRR, but RRR is compressible.

Conversions from bit vectors are defined for these types. So you just pass a bit vector to them:

julia> using IndexableBitVectors

julia> SucVector(bitrand(10))
10-element IndexableBitVectors.SucVector:
 false
 false
 false
 false
  true
  true
 false
 false
 false
  true

julia> RRR(bitrand(10))
10-element IndexableBitVectors.RRR:
 false
 false
 false
 false
  true
 false
 false
 false
  true
 false

The script and result of benchmarks can be found in the benchmarks directory. Plots are in a Jupyter notebook: benchmarks/plot.ipynb.