QWT：Rust 四元小波树

小波树 [1] 是一种紧凑的数据结构，对于一个长度为 $n$ 的序列 $S$ 和大小为 $\sigma$ 的字母表，它只需要 $n\lceil\log \sigma \rceil (1+o(1))$ 比特的空间，并且可以在 $\Theta(\log \sigma)$ 时间内回答 rank 和 select 查询。

rank 查询计算序列中某个符号在给定位置之前出现的次数。select 查询找到序列中具有给定 rank 的符号的位置。这些查询在，例如，压缩、计算几何和模式匹配（如反向搜索——许多压缩全文索引的核心）中都有应用。

此存储库提供了 Rust 中小波树的非常快速的实现。一个配套的 C++ 实现可在 此处 获取。更确切地说，我们在此实现了一个称为小波矩阵 [2] 的变体，它提供了更优雅的实现。

四元小波树 (QWT) 通过使用 4-叉树而不是二叉树作为小波树的基础来提高查询性能。小波树的 4-叉树布局有助于在查询期间将缓存未命中次数减半，从而降低查询延迟。

实验评估表明，与其它小波树实现（例如广泛使用的 C++ Succinct Data Structure Library（SDSL）中的实现）相比，四元小波树将访问、rank 和 select 查询的延迟提高了约 2 倍。有关更多详细信息，请参阅 基准测试 和论文 [3]。

更快的 rank 查询

如前所述，四元小波树 (QWT) 通过用 4-叉树代替小波树中的传统二叉树结构来增强查询性能。

在处理中等大小的序列时，影响查询性能的主要因素是缓存未命中成本，这些成本在每个小波树级别都会发生。然而，通过使用4叉树结构，我们有效地将树的高度减少了半。因此，这种高度减少导致缓存未命中数量成比例减少，从而实现了查询时间约2倍的性能提升。

可以使用一个专门设计用于预测和预取rank查询所需缓存行的小预测模型来进一步改进rank查询。这可以使rank查询的性能提升至1.6倍。

基准测试

在此，我们报告了一些实验，以比较我们的实现与其他最先进的实现。实验使用一台服务器机器的单线程，该机器具有8个3.60 GHz基频的Intel i9-9900KF核心，运行Ubuntu 23.04 LTS内核版本6.2.0-36。代码是用Rust 1.73.0编译的。每个核心都有一个32 KiB的专用L1缓存，一个256 KiB的专用L2缓存，一个16 MiB的共享L3缓存，以及64 GiB的RAM。更详细的实验评估（在不同机器上）可以在[3]中找到。

数据集，命名为Big English，是来自古腾堡计划的所有35,750个ASCII编码的英文文本文件的串联。去除了与项目相关的标题，只留下实际文本。使用了4 GiB大小的前缀。文本有168个不同的符号。以下报告了下载数据集的详细信息。

请注意，rank查询的结果取决于我们在查询集中生成排名符号的方式。在这里，对于每个rank查询，我们通过遵循文本中符号的分布随机选择一个符号，即更频繁的符号被更频繁地选择。所有数据结构在排名稀有符号时都有或多或少相同的性能。原因在于那些稀有符号的最后几层的部分可能适合放入缓存中。

我们提出了四种小波树实例，分别是QWT256和QWT512，它们分别是具有256和512个符号块大小的四叉小波树。在QWT256Pfs和QWT512Pfs中的后缀Pfs表示它们使用额外的空间来存储预测模型，这可以进一步加速'rank'查询。更多详细信息请参阅我们的完整论文[3]。

要运行实验，我们需要用以下方式编译二进制可执行文件：

RUSTFLAGS="-C target-cpu=native" cargo build --release

这将在\target\release\中生成两个可执行文件perf_rs_quat_vector和perf_wavelet_tree。

前者用于测量QuadVectors的性能，它们是我们小波树实现的基本构建块。您可以安全地忽略它。

后者测量在给定输入文本上构建的四叉小波树的性能。

现在我们可以在当前目录中下载和解压缩Big English。然后，我们取它的4 GiB长度的前缀。

wget http://pages.di.unipi.it/rossano/big_english.gz
gunzip big_english.gz
head -c 4294967296 big_english > big_english.4GiB

以下命令在此输入文本上构建小波树（带有或没有预取支持的QWT 256和512），并运行1000万个随机的访问、排名和选择查询。

./target/release/perf_wavelet_tree --input-file big_english.4GiB --access --rank --select

可以使用标志--test-correctness来执行额外的测试，以检查索引的正确性。我们还可以使用n_queries指定查询数（默认为1000万个查询）。

代码通过强制每个查询的输入依赖于上一个查询的输出，来衡量查询的延迟。这与实际设置中查询的使用是一致的。例如，压缩文本索引（例如CSA或FM索引）支持的更高级查询分解为底层小波树上的几个相关查询。

要与其他Rust库进行比较，请查看分支benchmark。然后，使用以下命令运行基准测试perf_wt_bench

/target/release/perf_wt_bench --input-file big_english.4GiB --rank --select --access

示例

在项目目录中运行以下Cargo命令

cargo add qwt

以添加库。

一旦添加了crate，我们就可以使用以下代码轻松构建四波小波树。

use qwt::QWT256;

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];

let qwt = QWT256::from(data);

assert_eq!(qwt.len(), 8);

我们可以使用以下命令打印小波树的空间使用情况

use qwt::QWT256;
use qwt::SpaceUsage;

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];

let qwt = QWT256::from(data);

println!("{}", qwt.space_usage_byte() );

小波树实现FromIterator，因此我们可以使用.collect()。

use qwt::QWT256;

let qwt: QWT256<_> = (0..10_u8).into_iter().cycle().take(1000).collect();

assert_eq!(qwt.len(), 1000);

该数据结构支持三种操作

• get(i)访问索引序列的第i个符号；
• rank(c, i)计算符号c在位置i之前出现的次数（不包括位置i）;
• select(c, i)返回符号c的第(i+1)次出现的位置。

use qwt::{QWT256, AccessUnsigned, RankUnsigned, SelectUnsigned};

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];

let qwt = QWT256::from(data);

assert_eq!(qwt.get(2), Some(1));
assert_eq!(qwt.get(3), Some(0));
assert_eq!(qwt.get(8), None);

assert_eq!(qwt.rank(1, 2), Some(1));
assert_eq!(qwt.rank(1, 0), Some(0));
assert_eq!(qwt.rank(3, 8), Some(1));
assert_eq!(qwt.rank(1, 9), None);

assert_eq!(qwt.select(1, 0), Some(0));
assert_eq!(qwt.select(0, 1), Some(3));
assert_eq!(qwt.select(4, 0), Some(5));
assert_eq!(qwt.select(1, 3), None);

use qwt::{QWT256, AccessUnsigned, RankUnsigned, SelectUnsigned};

let data = vec![1u32, 0, 1, 0, 2, 1000000, 5, 3];
let qwt = QWT256::from(data);

assert_eq!(qwt.get(2), Some(1));
assert_eq!(qwt.get(5), Some(1000000));
assert_eq!(qwt.get(8), None);

use qwt::QWT256Pfs;

let data = vec![1u32, 0, 1, 0, 2, 1000000, 5, 3];
let qwt = QWT256Pfs::from(data);

assert_eq!(qwt.rank_prefetch(1, 2), Some(1));
assert_eq!(qwt.rank_prefetch(1, 0), Some(0));
assert_eq!(qwt.rank_prefetch(3, 8), Some(1));
assert_eq!(qwt.rank_prefetch(1, 9), None);

use std::fs;
use std::path::Path;

use qwt::{QWT256, AccessUnsigned};

let data = vec![1u8, 0, 1, 0, 2, 4, 5, 3];
let qwt = QWT256::from(data);

assert_eq!(qwt.get(2), Some(1));

// serialize
let serialized = bincode::serialize(&qwt).unwrap();

// write on file, if needed
let output_filename = "example.qwt256".to_string();
fs::write(Path::new(&output_filename), serialized).unwrap();

// read from file 
let serialized = fs::read(Path::new(&output_filename)).unwrap();

// deserialize
let qwt = bincode::deserialize::<QWT256<u8>>(&serialized).unwrap();

assert_eq!(qwt.get(2), Some(1));

@inproceedings{QWT,
  author = {Matteo Ceregini, Florian Kurpicz, Rossano Venturini},
  title = {Faster Wavelet Trees with Quad Vectors},
  booktitle = {Data Compression Conference ({DCC})}
  publisher = {IEEE},
  year = {2024},
  doi = {10.48550/ARXIV.2302.09239},
  url = {http://arxiv.org/abs/2302.09239}
}