triple_accel

使用SIMD加速的Rust编辑距离例程。支持快速汉明、Levenshtein、限制性Damerau-Levenshtein等距离计算和字符串搜索。

尽管矢量化SIMD代码允许比标量代码快20-30倍，但处理平台相关SIMD代码的难度使得SIMD例程不那么吸引人。该库的目标是提供SIMD编辑距离例程的易于使用的抽象，如果目标CPU架构不受支持，则回退到标量例程。此外，应提前提供所有编辑距离例程的限制和权衡，以便用户确切了解期望的内容。最后，该库应使短字符串和长字符串的性能都得到提升，因此它可以用于各种任务，从生物信息学到自然语言处理。 triple_accel非常轻量级：它仅依赖于其他crate进行基准测试。它可以在具有AVX2或SSE4.1支持的CPU上构建。它还可以在没有SIMD支持的机器上运行，通过自动使用标量替代方案。

安装

添加

triple_accel = "*"

到你的[dependencies]部分。该库在这里可从crates.io获取。

或者，你可以克隆此仓库并运行

cargo build --release

通常，为了获得最大效率，如果不需要便携性，可以使用RUSTFLAGS="-C target-cpu=native"。

测试

你可以通过

cargo test

在克隆仓库后运行测试。

持续集成用于确保代码在最新的Linux、Windows和Mac平台上通过所有测试。此外，使用如jewel-sse、jewel-avx、jewel-8bit、jewel-16bit和jewel-32bit这样的crate功能标志来覆盖默认的CPU功能自动检测，以便在持续集成中对所有功能进行彻底测试。指定了debug功能标志，因此将打印出使用的确切底层向量类型。

基准测试

可以使用以下方式运行基准测试：

cargo bench

文档

文档可在此处找到。要在您的机器上构建它们，请运行：

cargo doc

功能

此库提供了在草垛字符串中搜索某些针字符串和在两个字符串之间计算编辑距离的例程。支持汉明距离（仅错位）、莱文斯坦距离（错位+间隙）和限制性Damerau-Levenshtein距离（交换+错位+间隙），以及任意编辑成本。除了提供简单的接口外，此库还提供了对编辑距离计算的强大底层控制。

在运行时，根据CPU支持情况选择特定算法的实现，以下列顺序进行：

1. 如果支持AVX2，则使用256位AVX向量的矢量化实现。
2. 如果支持SSE4.1，则使用128位SSE向量的矢量化实现。
3. 标量实现。

目前，矢量化SIMD实现仅适用于x86或x86-64 CPU。然而，在支持这些SIMD内建的机器上编译此库后，该库可以在其他机器上使用。此外，根据输入字符串的长度，在运行时选择用于存储向量的内部数据结构和向量中值的位宽，以实现最大效率和精度。

限制

由于使用SIMD内建，仅支持用u8字节表示的二进制字符串。目前不支持Unicode字符串。

示例

triple_accel提供了一个非常简单且易于使用的框架，用于常见的编辑距离操作。计算两个字符串之间的汉明距离（错位数）非常简单

use triple_accel::*;

let a = b"abcd";
let b = b"abcc";

let dist = hamming(a, b);
assert!(dist == 1);

默认情况下，如果可能，将使用SIMD。同样，我们可以使用以下代码轻松计算两个字符串之间的莱文斯坦距离（字符错位和间隙的成本均为1）

use triple_accel::*;

let a = b"abc";
let b = b"abcd";

let dist = levenshtein_exp(a, b);
assert!(dist == 1);

这使用指数搜索来估计a和b之间的编辑次数，这使得当a和b之间的编辑次数较低时，比替代的levenshtein函数更有效。

除了编辑距离例程外，triple_accel还提供了搜索例程。这些例程返回一个迭代器，指示needle字符串在何处与haystack字符串匹配。triple_accel将尝试最大化结束于相同位置的匹配长度，并在某些匹配完全重叠时删除较短的匹配。

use triple_accel::*;

let needle = b"helllo";
let haystack = b"hello world";

let matches: Vec<Match> = levenshtein_search(needle, haystack).collect();
// note: start index is inclusive, end index is exclusive!
assert!(matches == vec![Match{start: 0, end: 5, k: 1}]);

有时，有必要使用triple_accel提供的略微低级但功能更强大的例程。例如，可以允许1成本的字符交换（除了错位和间隙）

use triple_accel::levenshtein::*;

let a = b"abcd";
let b = b"abdc";
let k = 2; // upper bound on allowed cost
let trace_on = false; // return edit traceback?

let dist = levenshtein_simd_k_with_opts(a, b, k, trace_on, RDAMERAU_COSTS);
// note: dist may be None if a and b do not match within a cost of k
assert!(dist.unwrap().0 == 1);

不要被函数名称所误导！levenshtein_simd_k_with_opts将回退到标量实现，如果不可用AVX2或SSE4.1支持。它只是更喜欢尽可能使用SIMD。

对于大多数常见情况，重新导出的函数就足够了，不需要直接使用底层函数。

许可

MIT

贡献

阅读贡献指南 这里。

行为准则

阅读行为准则 这里。

为什么叫“triple_accel”？

因为“时之礼赞 - 三倍加速”是《Fate/Zero》中Kiritsugu Emiya使用的一种魔法能力，可以提升他的速度和反应时间。还有一些其他对Fate系列的引用...