后缀数组

内存中二进制数据的后缀数组构建和搜索算法。

为了索引纯文本，burntsushi 的 suffix，支持 utf-8，是更好的选择。

本包使用 Amos Wenger 的 C 绑定 来调用 Yuta Mori 的 dissufsort 构建 后缀数组，这是已知的最快单线程后缀数组构建算法（SACA），仅使用 O(1) 的额外工作空间。

此外，我还在单独的 crate 中实现了空间高效的并行 SACA pSACAK。目前，它还没有经过彻底的基准测试和优化。

待办事项

• 使用 Pizza&Chili 语料库 进行基准测试。

• 重写基准测试。

• 通过 LCP 数组（也称为构建增强后缀数组（ESA））加速搜索。存在两种主要的 LCP 数组构建算法（LACA）：第一类从后缀数组生成 LCP 数组。据我所知，这些 LACAs 需要分配额外的辅助数组（如 ISA，PLCP，和 BWT）来构建 LCP 数组。第二类构建后缀数组和它的 LCP 数组。它们速度快，空间高效，但需要对基于诱导复制的 SACAs 进行复杂的修改（如 sais-lite，saca-k，和 divsufsort）。在本包提供 ESA 支持，直到我找到合适的实现方法之前，本包不会提供 ESA 支持。

• 通过桶指针加快搜索速度，受此论文启发：该论文（使用 trie 作为索引、交错数组和文本指纹来提高磁盘上 ESA 搜索的局部性）。请参见 SuffixArray::enable_buckets()。

• 添加压缩后缀数组（CSA）支持。 CSA 在牺牲一些速度的同时换取了一些空间效率，这并不是非常必要。

• 序列化和反序列化。启用可选的 pack 功能以使用这些 API。此功能基于 Paul Masurel 的 bitpacking。

• 重写后缀数组构造算法。目前，此 crate 使用 dissufsort 来构建所有后缀数组。

• 研究其他人对改进 libdivsufsort 和多键快速排序所做出的努力：[1](http://panthema.net/2013/parallel-string-sorting/)、[2](https://github.com/akamiru/sort/wiki/General-Description-of-DAware)、[3](https://github.com/jlabeit/parallel-divsufsort)。