Succinct.rs

Succinct Data Structures library for Rust.

Master API Docs | Released API Docs | Benchmark Results | Changelog

Succinct.rs is a library to provide succinct data structures with simple API and high performance.

Currently, Succinct Bit Vector is supported.

Table of Contents

• Table of Contents
  • Quickstart
  • Features
  • Versions
  • Roadmap
  • Contributing
  • License

Quickstart

To use with Succinct.rs, add the following to your Cargo.toml file:

toml [dependencies] succinct_rs = "0.1"

Succinct Bit Vector Usage

```rust extern crate succinct_rs;

use succinctrs::bitvector::{BitVectorBuilder, BitVectorString};

// 01001 built by from_length() and set_bit() let bv = BitVectorBuilder::fromlength(5) .setbit(1) .set_bit(4) .build();

asserteq!(bv.access(0), false); // [0]1001; 0th bit is '0' (false) asserteq!(bv.access(1), true); // 0[1]001; 1st bit is '1' (true) assert_eq!(bv.access(4), true); // 0100[1]; 4th bit is '1' (true)

asserteq!(bv.rank(0), 0); // [0]1001; Range [0, 0] has no '1' asserteq!(bv.rank(3), 1); // [0100]1; Range [0, 3] has 1 '1' assert_eq!(bv.rank(4), 2); // [01001]; Range [0, 4] has 2 '1's

asserteq!(bv.select(0), Some(0)); // []01001; Minimum i where range [0, i] has 0 '1's is i=0 asserteq!(bv.select(1), Some(1)); // 0[1]001; Minimum i where range [0, i] has 1 '1's is i=1 asserteq!(bv.select(2), Some(4)); // 0100[1]; Minimum i where range [0, i] has 2 '1's is i=4 asserteq!(bv.select(3), None); // There is no i where range [0, i] has 3 '1's

// 10010 built by from_str() let bv = BitVectorBuilder::fromstr(BitVectorString::new("10010")).build(); // Tips: BitVectorString::new() ignores '_'. ```

Features

• Arbitrary length support with minimum working memory: Succinct.rs provides virtually arbitrary length of data structures. There are carefully designed to use as small memory space as possible.
• Simple public APIs: Each data structures almost only have very basic operations for the data structure. succinct::BitVector, for example, has only access(), rank(), and select().
• Latest benchmark results are always accessible: Succinct.rs is continuously benchmarked in Travis CI using Criterion.rs. Graphical benchmark results are published here.

Succinct Bit Vector Complexity

When the length of a BitVector is N:

| | build() | access() | rank() | select() | |------------------|--------------------------------------------------------|------------|----------|------------| | Time-complexity | O(N) | O(1) | O(1) | O(log N) | | Space-complexity | N + o(N) | 0 | O(log N) | O(log N) |

(Actually, select()'s time-complexity can be O(1) with complex implementation but Succinct.rs, like many other libraries, uses binary search of rank()'s result).

Versions

Succinct.rs uses semantic versioning.

Since current major version is 0, minor version update might involve breaking public API change (although it is carefully avoided).

Rust Version Supports

Succinct.rs is continuously tested with these Rust versions in Travis CI:

• 1.33.0
• Latest stable version
• Beta version
• Nightly build

So it expectedly works with Rust 1.33.0 and any newer versions.

Older versions may also work, but are not tested or guaranteed.

Roadmap

Succinct.rs has plan to provide these succinct data structures.

1. Succinct Bit Vector (done)
2. LOUDS
3. SuRF

Contributing

Any kind of pull requests are appreciated.

Currently, there are not many rules for contribution. But at least your pull requests must pass Travis CI.

License

Succinct.rs is dual licensed under the Apache 2.0 license and the MIT license.