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 and LOUDS (Level-Order Unary Degree Sequence) are supported.
To use with Succinct.rs, add the following to your Cargo.toml file:
toml
[dependencies]
succinct_rs = "0.4"
```rust extern crate succinct_rs;
use succinct_rs::{BitVectorBuilder, BitString};
// 01001 built by from_length() and set_bit()
let bv = BitVectorBuilder::fromlength(5)
.setbit(1)
.set_bit(4)
.build();
// access(), rank(), and select() are supported.
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
// -----------------------------------------------
// 01001 built by from_bit_string()
let bv = BitVectorBuilder::frombitstring(BitString::new("01001")).build(); // Tips: BitString::new() ignores ''.
// rank0() and select0() are also supported
asserteq!(bv.rank0(0), 1); // [0]1001; Range [0, 0] has no '0'
asserteq!(bv.rank0(3), 3); // [0100]1; Range [0, 3] has 3 '0's
assert_eq!(bv.rank0(4), 3); // [01001]; Range [0, 4] has 3 '0's
asserteq!(bv.select0(0), Some(0)); // []01001; Minimum i where range [0, i] has 0 '0's is i=0 asserteq!(bv.select0(1), Some(0)); // [0]1001; Minimum i where range [0, i] has 1 '0's is i=0 asserteq!(bv.select0(2), Some(2)); // 01[0]01; Minimum i where range [0, i] has 2 '0's is i=2 asserteq!(bv.select0(4), None); // There is no i where range [0, i] has 4 '0's ```
```rust extern crate succinct_rs;
use succinct_rs::{BitString, LoudsBuilder, LoudsIndex, LoudsNodeNum};
// Construct from LBS. let bs = BitString::new("10111010011100010110000"); let louds = LoudsBuilder::frombit_string(bs).build();
// LoudsNodeNum <-> LoudsIndex let node8 = LoudsNodeNum::new(8); let index11 = louds.nodenumtoindex(&node8); asserteq!(louds.indextonode_num(&index11), node8);
// Search for children. asserteq!(louds.parentto_children(&node8), vec!(LoudsIndex::new(17), LoudsIndex::new(18)));
// Search for parent. asserteq!(louds.childto_parent(&index11), LoudsNodeNum::new(4)); ```
succinct::BitVector, for example, has only access(), rank(), and select().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).
When the number of nodes in the tree represented as LOUDS is N:
| | build() | nodenumtoindex() | indextonodenum() | childtoparent() | parenttochildren() | |------------------|--------------------------------------------------------|------------|----------|------------|----| | Time-complexity | O(N) | O(log N) | O(1) | O(1) | O( max(log N, max num of children a node has) ) | | Space-complexity | N + o(N) | O(log N) | O(log N) | O(log N) | O( max(log N, max num of children a node has) ) |
(node_num_to_index() and child_to_parent() use rank(). index_to_node_num() and parent_to_children() use select()).
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).
Succinct.rs is continuously tested with these Rust versions in Travis CI:
So it expectedly works with Rust 1.33.0 and any newer versions.
Older versions may also work, but are not tested or guaranteed.
Succinct.rs has plan to provide these succinct data structures.
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.
Succinct.rs is dual licensed under the Apache 2.0 license and the MIT license.