Lib.rs

›
#integer #structure #fork #data-structures #sbwt

bin+lib simple-sds-sbwt

sbwt crate 中的简单-sds 衍生版本

所有者为 Jarno N. Alanko.

1 个不稳定版本

0.3.1 2024 年 4 月 26 日

#42 在 #fork


用于 sbwt

MIT 许可证

445KB
7.5K SLoC

Simple-sds-sbwt

这是 sbwt crate 中使用的 simple-sds 衍生版本。

简单的简洁数据结构

这些结构与 SDSL 中的结构在性能和可扩展性方面相当。由于关注的是（相对）简单，因此通常避免低级优化。

实现的功能

整数向量

  • RawVector：支持一次读取、写入和追加 1-64 位的位数组。在 Vec<u64> 之上实现。
    • RawVectorWriter：是 RawVector 的只写版本，直接将结构写入文件。
    • RawVectorMapper：是不可变内存映射的 RawVector。
  • IntVector：在 RawVector 之上实现的固定宽度整数位打包向量。类似于 sdsl::int_vector，但也支持栈功能。
    • IntVectorWriter：是 IntVector 的只写版本，直接将结构写入文件。类似于 sdsl::int_vector_buffer 的一个子集。
    • IntVectorMapper：是不可变内存映射的 IntVector。
  • WaveletMatrix：固定宽度整数的不可变向量。类似于 sdsl::wm_int。
    • 支持 rank()、inverse_select()、select()、predecessor() 和 successor() 等每个项值。
    • 遍历所有项以及具有指定值的项。
    • 使用每个级别的 BitVector 实现。

位向量

  • BitVector：一个普通的不可变位向量。
    • 支持使用可选支持结构的 rank()、rank_zero()、select()、select_zero()、predecessor() 和 successor() 查询。
    • 支持对集合位、未设置位和所有位的迭代器。
    • 在 RawVector 上实现。
  • RLVector：一种运行长度编码的位向量。
    • 支持 rank()、rank_zero()、select()、select_zero()、predecessor() 和 successor() 查询。
    • 支持集合位和所有位的迭代器。
    • 使用 RLBuilder 进行空间高效的构建。
  • SparseVector：一种 Elias-Fano 编码的位向量。
    • 支持 rank()、rank_zero()、select()、select_zero()、predecessor() 和 successor() 查询。
    • 支持集合位和所有位的迭代器。
    • 使用 SparseBuilder 进行空间高效的构建。

计划的功能

整数向量

  • 可变内存映射向量。

位向量

  • predecessor() 和 successor() 的版本，返回值而不是迭代器？
  • 基于迭代器的类似切片的功能？

备注

  • 包含的 .cargo/config.toml 将目标 CPU 设置为 native。
  • 此 crate 是为具有 BMI2 指令集的 x86_64 架构设计的（Intel Haswell / AMD Excavator 或更高版本）。某些操作可能在没有 POPCNT、LZCNT、TZCNT 和 PDEP 指令的情况下较慢。
  • 也支持 64 位 ARM。
  • 需要类 Unix 操作系统才能使用 mmap()。
  • 如果系统不是小端字节序或者如果 usize 不是 64 位，则可能无法正常工作。

依赖项

~0.4–340KB