#succinct #rank #select

succinct

Succinct data structures for Rust

17 releases

Uses old Rust 2015

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

#600 in Data structures

Download history 190/week @ 2022-11-28 265/week @ 2022-12-05 276/week @ 2022-12-12 133/week @ 2022-12-19 319/week @ 2022-12-26 199/week @ 2023-01-02 197/week @ 2023-01-09 129/week @ 2023-01-16 150/week @ 2023-01-23 239/week @ 2023-01-30 187/week @ 2023-02-06 211/week @ 2023-02-13 323/week @ 2023-02-20 183/week @ 2023-02-27 248/week @ 2023-03-06 228/week @ 2023-03-13

1,039 downloads per month
Used in 10 crates (6 directly)

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

~185–270KB