textdistance.rs

[ github.com ] [ docs.rs ] [ crates.io ]

Rust 库，包含大量不同算法来比较两个序列的相似度。

功能

• 💪 基于流行的、经过实战考验的 textdistance Python 库（并由同一作者编写）。
• 📚 包含 20+ 种适用于所有目的的算法。
• 🔬 包含最先进的算法，如 EntropyNCD 和 Sift4。
• 🪶 零依赖。
• 🔨 与任何迭代器一起工作，包括字节、代码点、Unicode 表意文字群、单词和数字。
• ❤️ 为所有算法提供友好且一致的 API。
• 📏 可选地在 0.0-1.0 区间对结果进行归一化。
• 🛡 无不安全代码。
• 🦀 纯 Rust。

可用的算法

基于编辑的

1. DamerauLevenshtein，包括最佳字符串对齐和限制性。
2. Hamming
3. Jaro
4. JaroWinkler
5. Levenshtein
6. Sift4Common
7. Sift4Simple
8. SmithWaterman

基于标记的

1. Bag
2. Cosine（又称 Orchini、Tucker、Otsuka–Ochiai）
3. EntropyNCD（基于熵的标准化压缩距离）
4. Jaccard（又称 Tanimoto、关键成功指数）
5. Overlap（又称 Szymkiewicz–Simpson）
6. Roberts
7. SorensenDice（又称 F1、Czekanowski、Zijdenbos）
8. Tversky

基于序列的

1. LCSSeq（最长公共子序列）
2. LCSStr（最长公共子字符串）
3. RatcliffObershelp（又称 Gestalt 模式匹配）

朴素

1. 前缀
2. 后缀
3. 长度

其他指标归一化

1. LIG3 对 Hamming 的归一化由 Levenshtein 实现
2. MLIPNS 对 Hamming 的归一化
3. YujianBo 对 Levenshtein 的归一化

安装

cargo add textdistance

使用方法

textdistance::str 模块为每个算法提供计算两个字符串之间距离/相似度的快捷函数

use textdistance::str::damerau_levenshtein;
assert!(damerau_levenshtein("abc", "acbd") == 2);

《textdistance::nstr》模块与之前相同，但所有算法都返回归一化值（介于0.0和1.0之间）

use textdistance::nstr::damerau_levenshtein;
assert!(damerau_levenshtein("abc", "acbd") == 2./4.);

对于更高级的使用，每个算法都作为实现《Algorithm》特质的《struct》提供

use textdistance::{Algorithm, DamerauLevenshtein};

let a = DamerauLevenshtein::default();
let r = a.for_str("abc", "acbd");
assert!(r.val() == 2);
assert!(r.nval() == 2./4.);

1. 《Algorithm》特质提供了《for_str》、《for_vec》和《for_iter》方法，分别用于计算两个字符串、向量（切片）或迭代器的结果。此外，还有《for_words》和《for_bigrams》方法，在计算距离之前分别将文本拆分为单词或双词。
2. 每个方法返回一个《textdistance::Result》，它提供了获取度量、距离或相似度（绝对值和归一化值）的方法。

Unicode支持

《for_str》方法（以及《str》和《nstr》模块中的所有函数）使用《String.chars》来拆分字符串，然后通过《for_iter》方法运行。因此，《é》将被视为两个不同的字符（“拉丁小写字母e”和“组合重音符号”）。通常，这是可以的，这也是Python的工作方式。您可以在官方Rust文档中了解更多信息。

如果您希望《é》被视为一个单独的符号，请使用unicode-segmentation包

use textdistance::{Algorithm, DamerauLevenshtein};
use unicode_segmentation::UnicodeSegmentation;

let s1 = "a̐éö̲\r\n";
let s2 = "éa̐ö̲\r\n";
let g1 = s1.graphemes(true);
let g2 = s2.graphemes(true);
let a = DamerauLevenshtein::default();
let r = a.for_iter(g1, g2);
assert!(r.val() == 1);

选择算法

要使用的算法取决于您的用例。首先，您需要决定算法类别

1. 基于编辑的算法适用于短序列，用于检测错误和细微变化。
2. 基于标记的算法适用于长序列，用于比较有显著修改的长文本。
3. 基于序列的算法适用于计算序列原始版本和修改后版本之间的diff大小。

如果您选择基于编辑的算法，接下来需要决定您需要检测哪种类型的更改

• ✏️ 替换。一个字符被另一个字符替换。
• ➕ 添加。添加一个新字符。
• 🗑 删除。删除一个字符。
• 🔄 交换。交换两个连续的字符。

• 《Hamming》是最快的，但只检测替换。
• 《Sift4》非常快，但不如其他算法知名且经过实战考验。
• 《Jaro》比《Sift4》慢，但知名且经过实战考验。
• 《JaroWinkler》与《Jaro》类似，但给具有匹配前缀的字符串赋予更多权重。
• 《Levenshtein》检测所有内容，但不是交换，并且比《DamerauLevenshtein》快（但比其他算法慢）。
• 《DamerauLevenshtein》满足所有要求，但非常慢。

有一些用例

• 经过优化的《DamerauLevenshtein》在cargo中用于纠正命令名称中的错误。
• Jaro 包含在 Elixir 标准库中（String.jaro_distance）。编译器和 mix（Elixir 的 cargo）使用它来为模块或命令名中的错误提供“你是否想输入？”功能。
• RatcliffObershelp 变体包含在 Python 标准库中（difflib.SequenceMatcher）。

基准测试

图例

• 🐌 非常慢（> 5 ms）
• 🐢 慢（> 1 ms）
• 🐇 快（> 500 µs）
• 🐎 非常快（< 500 µs）

基于编辑（及其归一化）

基于标记的

基于序列的

朴素

基准测试由 criterion 提供，存放在 benches 目录。它们相当简单：抓取 10 个 开源许可证，从每个许可证中取 200 个字符的前缀，并进行交叉比较。对于不同类型的输入、输入长度、比较单词而不是字符或在不同的机器上运行基准测试，数字可能会有很大差异。这些基准测试的目的是提供基本的指导，而不是给出确定的答案。如果性能对您的应用程序至关重要，我鼓励您使用您拥有的真实数据来进行基准测试。

版本控制

我们坚持使用 SemVer

1. 补丁号 用于修复错误。如果我们发现之前的实现与原始论文中描述的算法不匹配，则算法的某些角落案例的结果可能会改变。
2. 次版本号 用于新算法和功能。
3. 主版本号 用于 API 的大幅更改。我们尽量不破坏现有功能，但我们更愿意提供一个友好且方便的 API 而不是保持向后兼容。

限制

• 在原始 textdistance 中，大多数算法都调整为适用于任何数量的输入序列。然而，Rust 不支持可变参数，因此所有算法目前都仅针对恰好两个输入实现。
• 该包中的所有算法都实现了相同的 Algorithm trait。因此，具有对输入序列元素的限制（如仅与 ASCII 字符一起工作的 Editex 和 MRA）的度量标准目前无法实现。
• 大多数实现的算法都有某些属性（如 交换性质），这使得它们的行为更像您所期望的，并使归一化变得简单。因此，我还没有实现 Needleman-Wunsch 和 Gotoh，主要是因为它们很难归一化，而且我仍然不是 100% 确信我在原始 textdistance 中是否正确地实现了它们。

致谢

以下是我用作参考实现和测试用例来源的库：

• 🐍 Python: textdistance, abydos, jellyfish.
• ☕️ JS: talisman.
• 🦀 Rust: strsim, distance, levenshtein-rs.

特别感谢 Trevor Gross 将 textdistance 在 crates.io 的名称转让给我。

本地测试

要本地运行所有内容，您只需要 Rust、Python 和 task。执行 task all 来运行所有代码格式化程序、检查器和测试。

谢谢 ❤️