sux-rs

A pure Rust implementation of succinct and compressed data structures.

This crate is a work in progress: part of it is a port from Sux and from the DSI Utilities; new data structures will be added over time. Presently, we provide:

• the BitFieldSlice trait---an alternative to Index returning values of fixed bit width;
• an implementation of bit vectors and of vectors of bit fields of fixed with;
• traits for building blocks and structures like Rank , Select, and IndexedDict;
• an implementation of the Elias--Fano representation of monotone sequences;
• an implementation of list of strings compressed by rear-coded prefix omission;
• an implementation of static functions.

The focus is on efficiency (in particular, there are unchecked version of all methods) and on flexible composability (e.g., you can fine tune your Elias–Fano instance choosing different types of internal indices, and whether to index zeros or ones).

ε-serde support

All structures in this crate are designed to work well with ε-serde: in particular, once you have created and serialized them, you can easily map them into memory or load them in memory regions with specific mmap() attributes.

Acknowledgments

This software has been partially supported by project SERICS (PE00000014) under the NRRP MUR program funded by the EU - NGEU, and by project ANR COREGRAPHIE, grant ANR-20-CE23-0002 of the French Agence Nationale de la Recherche.