Skip to content

[DEPRECATED] Succinct Data Structures library for Rust

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT
Notifications You must be signed in to change notification settings

laysakura/succinct.rs

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

58 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

DEPRECATION WARNING

This library is deprecated. This library has succinct bit vector (FID) and LOUDS implementation.

These implementations are split into distinct libraries.

Use fid-rs and louds-rs instead.

Succinct.rs

Succinct Data Structures library for Rust.

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

Build Status Crates.io Minimum rustc version License: MIT License: Apache 2.0

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.

Table of Contents

Quickstart

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

[dependencies]
succinct_rs = "0.6"
extern crate succinct_rs;

use succinct_rs::{BitString, SuccinctBitVectorBuilder};

// Construction -------------------------
// `01001` built by `from_bit_string()`
let bv = SuccinctBitVectorBuilder::from_bit_string(BitString::new("0100_1")).build();  // Tips: BitString::new() ignores '_'.

// `01001` built by `from_length()` and `add_bit()`
let bv = SuccinctBitVectorBuilder::from_length(0)
    .add_bit(false)
    .add_bit(true)
    .add_bit(false)
    .add_bit(false)
    .add_bit(true)
    .build();

// Basic operations ---------------------
assert_eq!(bv.access(0), false);  // [0]1001; 0th bit is '0' (false)
assert_eq!(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)

assert_eq!(bv.rank(0), 0);  // [0]1001; Range [0, 0] has no '1'
assert_eq!(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

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

// rank0, select0 -----------------------
assert_eq!(bv.rank0(0), 1);  // [0]1001; Range [0, 0] has no '0'
assert_eq!(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

assert_eq!(bv.select0(0), Some(0)); // []01001; Minimum i where range [0, i] has 0 '0's is i=0
assert_eq!(bv.select0(1), Some(0)); // [0]1001; Minimum i where range [0, i] has 1 '0's is i=0
assert_eq!(bv.select0(2), Some(2)); // 01[0]01; Minimum i where range [0, i] has 2 '0's is i=2
assert_eq!(bv.select0(4), None);    // There is no i where range [0, i] has 4 '0's

LOUDS Usage

extern crate succinct_rs;

use succinct_rs::{BitString, LoudsBuilder, LoudsIndex, LoudsNodeNum};

// Construct from LBS.
let bs = BitString::new("10_1110_10_0_1110_0_0_10_110_0_0_0");
let louds = LoudsBuilder::from_bit_string(bs).build();

// LoudsNodeNum <-> LoudsIndex
let node8 = LoudsNodeNum::new(8);
let index11 = louds.node_num_to_index(&node8);
assert_eq!(louds.index_to_node_num(&index11), node8);

// Search for children.
assert_eq!(louds.parent_to_children(&node8), vec!(LoudsIndex::new(17), LoudsIndex::new(18)));

// Search for parent.
assert_eq!(louds.child_to_parent(&index11), LoudsNodeNum::new(4));

Features

  • Arbitrary length support with minimum working memory: Succinct.rs provides virtually arbitrary size 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::SuccinctBitVector, 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.

When the length of a SuccinctBitVector 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).

LOUDS Complexity

When the number of nodes in the tree represented as LOUDS is N:

build() node_num_to_index() index_to_node_num() child_to_parent() parent_to_children()
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()).

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 (doing)
    • Find out efficient API sets by applying LOUDS to Trie implementation.
  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.

About

[DEPRECATED] Succinct Data Structures library for Rust

Topics

Resources

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT

Stars

Watchers

Forks

Packages

No packages published