#succinct #rank #select

succinct

Succinct data structures for Rust

17 releases

0.5.2 Aug 29, 2019
0.4.4 Mar 28, 2018
0.4.2 Oct 17, 2016
0.4.0 Jun 28, 2016

#2 in #select

Download history 23/week @ 2019-07-14 26/week @ 2019-07-21 28/week @ 2019-07-28 46/week @ 2019-08-04 46/week @ 2019-08-11 40/week @ 2019-08-18 73/week @ 2019-08-25 53/week @ 2019-09-01 110/week @ 2019-09-08 72/week @ 2019-09-15 87/week @ 2019-09-22 49/week @ 2019-09-29 26/week @ 2019-10-06 22/week @ 2019-10-13 34/week @ 2019-10-20

312 downloads per month
Used in 2 crates

MIT/Apache

170KB
4K SLoC

Succinct Data Structures for Rust

Build Status Crates.io License: MIT License: Apache 2.0

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.

Dependencies

~235KB