IndexableBitVectors.jl

Fully indexable dictionaries - access/rank/select operations
Author BioJulia
Popularity
12 Stars
Updated Last
2 Years Ago
Started In
May 2015

IndexableBitVectors

Build Status IndexableBitVectors.jl

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

Benchmarks:

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