小空间中的BWT构造

这是书中第11.8算法描述的小空间中BWT构造算法的Rust实现：《紧凑数据结构 - 实用方法》Gonzalo Navarro，2016。

给定一个典型文本，它以$O(n \log n \log \log n)$时间运行，并且需要$O(n)$额外的空间，其中$n$是输入字符串的长度，并且字母表的大小远小于$n$。更多详细信息请参阅书籍。

文档

https://docs.rs/small-bwt/

命令行工具

tools提供了一个命令行工具来构建文件的BWT。

$ cargo run --release -p tools -- -i input.txt -o output.bwt -t

使用桌面电脑（Intel i7，16 GB），将来自Pizza&Chili语料库的385 MiB大小的DNA文本转换为BWT，耗时6.8分钟，最大驻留集大小为727 MiB。

基准测试

benches提供了来自Pizza&Chili语料库提取的英文文本的时间性能基准。

$ cargo bench

许可

此库受以下任一许可协议的许可：

• Apache License，版本2.0 (LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0)
• MIT许可 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

任选其一。

benches/english.10MB.zst是从Pizza&Chili语料库提取的，并遵循LGPL许可。