Crate sucds 

Succinct data structures in Rust

Sucds is a collection of succinct data structures, powerful tools to store a variety of data structures in compressed space and quickly perform operations on the compressed data.

Design policy

Thus far, many succinct data structures and their implementation techniques have been developed for a wide range of applications. To handle them in a single crate, we set up several design policies:

• Curated collection: Rather than offering every possible succinct data structure, only those with competitive advantages are provided.
• Consistent interfaces: Data structures in the same category share traits such as Access, Rank, and Select, and are easily replaceable.
• Ensured safety: Unsafe instructions, typically reserved for extremely low-level programming, are avoided.
• Pure Rust: The implementation is written in pure Rust, with optional no_std support.

Data structures

The data structures provided in this crate are categorized as follows:

• Integer vectors
• Bit vectors
• Monotone-increasing integer sequences
• Character sequences

The descriptions for each category are available in the corresponding module.

Throughout this document, we write $\log_2$ with $\lg$.

Serialization/deserialization

All the data structures can be serialized or deserialized through the Serializable trait, which is defined on the Read and Write traits in the io module. With the std feature (enabled by default), those traits are re-exports of std::io, and any reader or writer of the standard library can be used as usual.

no_std support

This crate supports no_std environments by disabling the default std feature, although the alloc crate is always required. Two things differ from the default build:

• Readers and writers are limited to the byte containers available in alloc, i.e., Vec<u8> and &mut [u8] for writing and &[u8] for reading.
• SucdsError does not implement std::error::Error, and its Io variant holds io::Error defined in this crate instead of std::io::Error.

intrinsics feature

Primitive bit operations in the broadword module are implemented with broadword techniques by default. Enabling the intrinsics feature replaces them with the equivalent operations of the standard library, which can be compiled into dedicated CPU instructions. Building with RUSTFLAGS="-C target-cpu=native" is recommended in that case.

Limitation

This library is designed to run on 64-bit machines.

Re-exports

pub use errors::SucdsError;

pub use serial::Serializable;

Modules

bit_vectors

Top module for bit vectors.

broadword

Broadword tools.

char_sequences

Top module for character sequences.

errors

Error type for this crate.

int_vectors

Top module for integer vectors.

io

Minimal I/O abstraction for serialization.

mii_sequences

Top module for monotone-increasing integer sequences.

serial

Serializers.

utils

Utilities in Sucds.

Type Aliases

Result

Result type for this crate.