弃用警告

此库已弃用。此库包含 succinct 位向量 (FID) 和 LOUDS 实现。

这些实现被分割成独立的库。

请使用 fid-rs 和 louds-rs 代替。

Succinct.rs

Succinct Data Structures for Rust 的库。

主 API 文档 | 发布 API 文档 | 基准测试结果 | 变更日志

Succinct.rs 是一个库，提供具有 简单 API 和 高性能 的 succinct 数据结构。

目前，支持 Succinct Bit Vector 和 LOUDS (Level-Order Unary Degree Sequence)。

目录

• 目录
  • 快速入门
  • 功能
  • 版本
  • 路线图
  • 贡献
  • 许可证

快速入门

要使用 Succinct.rs，请将以下内容添加到您的 Cargo.toml 文件中

[dependencies]
succinct_rs = "0.6"

Succinct Bit Vector 使用方法

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 使用方法

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));

功能

• 支持任意长度，具有最小的工作内存：Succinct.rs 提供几乎 任意大小 的数据结构。它们被精心设计，以尽可能使用最小的内存空间。
• 简单的公共 API：每个数据结构几乎只有数据结构的基本操作。例如，succinct::SuccinctBitVector 只具有 access()、rank() 和 select()。
• 最新的基准测试结果始终可访问：Succinct.rs 在 Travis CI 中持续进行基准测试，使用 Criterion.rs。图形化的基准测试结果发布在此处 这里。

Succinct 位向量 的复杂性

当 SuccinctBitVector 的长度为 N 时

（实际上，select() 的时间复杂度可以通过复杂实现达到 O(1)，但 Succinct.rs，像许多其他库一样，使用 rank() 的结果进行二分查找）。

LOUDS 的复杂性

当以 LOUDS 表示的树中的节点数为 N 时

（node_num_to_index() 和 child_to_parent() 使用 rank()。 index_to_node_num() 和 parent_to_children() 使用 select()）。