Expand description
This crate provides a collection of data structures supported by fast implementations of rank and select queries. The data structures are static, meaning that they cannot be modified after they have been created.
Data structures
- BitVector with no overhead.
- Succinct Bit-Vector supporting fast rank and select queries.
- Elias-Fano encoding of monotone sequences supporting constant time predecessor queries.
- Two Range Minimum Query structures for constant time range minimum queries.
Performance
Performance was benchmarked against publicly available implementations of the same (or similar) data structures on crates.io at the time of writing. The benchmark results can be found in the Github repository. At the time of writing, this crate is the fastest implementation of all data structures except for one implementation of rank on bit-vectors (which pays for its speed with a missing select implementation).
Re-exports
pub use crate::elias_fano::EliasFanoVec;pub use bit_vec::fast_rs_vec::RsVec;pub use bit_vec::fast_rs_vec::RsVectorBuilder;pub use bit_vec::BitVec;pub use rmq::fast_rmq::FastRmq;
Modules
- This module contains a simple bit vector implementation with no overhead and a fast succinct bit vector implementation with rank and select queries.
- Elias-Fano encoding for sorted vectors of u64 values. It reduces the space required to represent all numbers (compression ratio dependent on data) and allows for constant time predecessor queries.
- Range minimum query data structures. These data structures allow to calculate the index of the minimum element in a range of a static array in constant time. The implementations are located in the binary_rmq and fast_rmq modules.