Fuzzt

Rust 实现的 字符串相似度度量

• Hamming
• Levenshtein (距离 & 标准化)
• 最优字符串对齐
• Damerau-Levenshtein (距离 & 标准化)
• Jaro 和 Jaro-Winkler
• Sørensen-Dice
• 格式塔模式匹配

标准化的版本返回值在 0.0 和 1.0 之间，其中 1.0 表示完全匹配。

还有适用于非字符串输入的函数的泛型版本。

新增功能？

这个 crate 主要基于 strsim-rs crate，并增加了一些不错的功能

• 格式塔模式匹配，Python difflib SequenceMatcher 使用的算法
• Top-N 匹配，从一组选择中检索最佳 N 个匹配的方法。
• 特征选择，允许您只选择要使用的特征（度量），减少应用程序的内存占用。

Top-N 匹配

get_top_n 方法从一组选择中获取最佳匹配列表。此功能受到 Python fuzzywuzzy 包（现在 thefuzz）中的 extractBests 方法的启发。

get_top_n 方法接受一个查询字符串、一个选择字符串数组、一个截止相似度分数、一个可选的返回匹配项数量、一个可选的字符串处理器和一个可选的相似度度量。它使用提供的或默认的字符串处理器处理每个选择和查询，使用提供的或默认的相似度度量计算处理后的查询和处理后的每个选择之间的相似度，并返回相似度分数大于或等于截止值的 top-N 匹配项。

以下是 get_top_n 方法的签名

extern crate fuzzt;
use fuzzt::{algorithms::NormalizedLevenshtein, get_top_n, processors::NullStringProcessor};

fn main() {
    let matches = get_top_n(
        "apple",
        &["apply", "apples", "ape", "applet", "applesauce"],
        Some(0.8),
        Some(3),
        Some(&NullStringProcessor),
        Some(&NormalizedLevenshtein),
    );
    assert_eq!(matches, ["apples", "applet", "apply"]);
}

特征选择

fuzzt 设计时考虑了灵活性，允许您根据特定用例选择所需的特征。这有助于减少应用程序的占用空间并优化性能。

该软件包包括以下功能

• damerau_levenshtein
• gestalt
• hamming
• jaro
• levenshtein
• optimal_string_alignment
• sorensen_dice

默认情况下，当将 fuzzt 作为依赖项添加时，将包括所有功能。但是，您可以选择仅包括特定的功能，在 Cargo.toml 文件的 features 键下列出它们。例如

[dependencies]
fuzzt = { version = "*", default-features = false, features = ["levenshtein", "jaro"] }

安装

Fuzzt 可在 crates.io 上找到。将其添加到您的项目中

cargo add fuzzt

使用

前往 Docs.rs 查看完整文档。您还可以克隆存储库，并运行 $ cargo doc --open。

示例

extern crate fuzzt;

use fuzzt::{
    damerau_levenshtein, hamming, jaro, jaro_winkler, levenshtein, normalized_damerau_levenshtein,
    normalized_levenshtein, osa_distance, sequence_matcher, sorensen_dice,
};

fn main() {
    match hamming("hamming", "hammers") {
        Ok(distance) => assert_eq!(3, distance),
        Err(why) => panic!("{:?}", why),
    }

    assert_eq!(levenshtein("kitten", "sitting"), 3);
    assert!((normalized_levenshtein("kitten", "sitting") - 0.571).abs() < 0.001);
    assert_eq!(osa_distance("ac", "cba"), 3);
    assert_eq!(damerau_levenshtein("ac", "cba"), 2);
    assert!((normalized_damerau_levenshtein("levenshtein", "löwenbräu") - 0.272).abs() < 0.001);
    assert_eq!(jaro("Friedrich Nietzsche", "Jean-Paul Sartre"), 0.3918859649122807);
    assert_eq!(
        jaro_winkler("cheeseburger", "cheese fries"),
        0.8666666666666666
    );
    assert_eq!(
        sorensen_dice("web applications", "applications of the web"),
        0.7878787878787878
    );
    assert_eq!(
        sequence_matcher("this is a test", "this is a test!"),
        0.9655172413793104
    );
}

使用函数的泛型版本

extern crate fuzzt;

use fuzzt::generic_levenshtein;

fn main() {
    assert_eq!(2, generic_levenshtein(&[1, 2, 3], &[0, 2, 5]));
}

算法

Hamming

两个等长字符串之间的 Hamming 距离是相应符号不同的位置数。它衡量将一个字符串转换为另一个字符串所需的最小替换次数。

Levenshtein

Levenshtein 距离是一种字符串度量，用于衡量两个序列之间的差异。它量化了将一个字符串转换为另一个字符串所需进行的编辑（插入、删除或替换）的数量。此度量的归一化版本提供了一个介于 0 和 1 之间的比例，其中 1 表示字符串完全相同。

最优字符串对齐

最优字符串对齐（OSA），也称为受限制的 Damerau-Levenshtein 距离，只考虑相邻的置换来计算最短距离。这意味着它不允许子字符串作为一个块移动，与 Damerau-Levenshtein 距离不同。

Damerau-Levenshtein

Damerau-Levenshtein 距离是 Levenshtein 距离的扩展，允许进行相邻字符的置换以及插入、删除和替换。归一化版本给出一个介于 0 和 1 之间的比例，其中 1 表示字符串完全相同。

Jaro 和 Jaro-Winkler

Jaro 距离允许置换，并考虑两个字符串之间的公共字符的数量和顺序。Jaro-Winkler 距离是 Jaro 距离的修改版，对从开头开始匹配的字符串给予更有利的评分。

Sørensen-Dice

此系数是一种用于评估两个样本相似性的统计量。它被计算为两个集合交集大小的两倍，除以两个集合大小之和。

格式塔模式匹配

这是Python的difflib.SequenceMatcher使用的算法。它使用一种称为“Ratcliff/Obershelp”的启发式方法，计算匹配字符数的两倍除以两个字符串中字符总数。它特别擅长检测接近匹配和一些类型的错误。

贡献

如果您不想安装Rust本身，如果您已安装Docker，可以运行$ ./dev以获取开发CLI。

基准测试需要Nightly工具链。运行$ cargo +nightly bench。

许可证

MIT