sux

纯Rust实现的简洁和压缩数据结构。

该crate是Sux项目的一部分；它还包含从DSI Utilities移植的代码和新结构。

目前，它提供以下功能：

• 位向量位字段向量;
• 多个用于排名和选择的结构，具有不同的权衡；
• 索引字典，包括单调序列的Elias–Fano表示和通过前缀省略压缩的字符串列表的实现。

重点是效率（特别是，所有方法都有未检查的版本）和灵活的可组合性（例如，您可以通过选择不同的内部索引类型以及是否索引零或一来微调您的Elias–Fano实例）。

ε-serde支持

该crate中的所有结构都设计得与ε-serde兼容：特别是，一旦您创建并序列化了它们，就可以轻松地将它们映射到内存中，或者使用特定的mmap()属性将它们加载到内存区域中。

MemDbg/MemSize支持

本仓库中的所有结构都支持来自 MemDbg 和 MemSize 的特性，这些特性来自 mem_dbg 库，提供了方便的内存使用检查和内存相关问题的调试功能。例如，这是在大型 EliasFano 实例上执行 mem_dbg() 的输出。

  117_041_232 B 100.00% ⏺: sux::dict::elias_fano::EliasFano<sux::rank_sel::select_zero_adapt_const::SelectZeroAdaptConst<sux::rank_sel::select_adapt_const::SelectAdaptConst>>
           8 B   0.00% ├╴u: usize
           8 B   0.00% ├╴n: usize
           8 B   0.00% ├╴l: usize
  75_000_048 B  64.08% ├╴low_bits: sux::bits::bit_field_vec::BitFieldVec
  75_000_024 B  64.08% │ ├╴data: alloc::vec::Vec<usize>
           8 B   0.00% │ ├╴bit_width: usize
           8 B   0.00% │ ├╴mask: usize
           8 B   0.00% │ ╰╴len: usize
  42_041_160 B  35.92% ╰╴high_bits: sux::rank_sel::select_zero_adapt_const::SelectZeroAdaptConst<sux::rank_sel::select_adapt_const::SelectAdaptConst>
  35_937_608 B  30.71%   ├╴bits: sux::rank_sel::select_adapt_const::SelectAdaptConst
  32_031_296 B  27.37%   │ ├╴bits: sux::bits::bit_vec::CountBitVec
  32_031_280 B  27.37%   │ │ ├╴data: alloc::vec::Vec<usize>
           8 B   0.00%   │ │ ├╴len: usize
           8 B   0.00%   │ │ ╰╴number_of_ones: usize
   3_906_312 B   3.34%   │ ╰╴inventory: alloc::vec::Vec<u64>
   6_103_552 B   5.21%   ╰╴inventory: alloc::vec::Vec<u64>

可组合性、函数性和性能

本仓库的设计旨在满足以下原则：

• 高性能：所有实现都尽量做到尽可能快（我们试图最小化缓存未命中、测试和指令）。
• 可组合性：所有结构都设计成易于相互组合；结构建立在其他结构之上，可以使用常见的 into_inner 习惯用法提取。
• 零成本抽象：所有结构都向底层结构转发所有未实现的条件排名/选择方法。
• 函数性：在可能的情况下，存在映射方法，可以替换底层结构为另一个结构，前提是它兼容。

本仓库不提供的内容

• 高泛化：所有位向量都基于相对具体的特性组合 AsRef<[usize]> + BitLength。

致谢

本软件部分由欧盟 - NGEU 资助的 NRRP MUR 项目 SERICS（PE00000014）和法国国家研究署 ANR 的项目 ANR COREGRAPHIE（资助编号 ANR-20-CE23-0002）支持。然而，所表达的观点和意见仅代表作者，不一定反映欧盟或意大利 MUR 的观点。欧盟和意大利 MUR 对此不承担责任。