Succinct Data Structures for Rust

So far we have:

• bit vectors and bit buffer;
• integer vectors with arbitrary-sized (1- to 64-bit) elements;
• a variety of universal codes;
• constant-time rank queries; and
• O(lg lg n)-time select queries based on binary search over ranks.

Usage

It’s on crates.io, so you can add

[dependencies]
succinct = "0.5.2"

to your Cargo.toml.

Credits

• IntVec borrows some implementation techniques from nbitsvec. The main difference is that nbitsvec uses a typenum to put the element size (in bits) as a parameter to the vector type. Also, nbitsvec is likely to be faster.

• Some of the API is inspired by SDSL, a C++ succinct data structures library. It’s much more complete than succinct, and probably more correct and faster too.