Levenshtein 算法和更多

Levenshtein 算法是一种传统上用于计算两个字符串之间的 Levenshtein 距离（即编辑距离）的技术。然而，算法本身并不局限于字符串。该算法同样适用于寻找任何具有等价关系定义的序列元素之间的编辑距离（即在序列中的元素 a 和 b，你可以判断 a == b 和 a != b 是否为真或假）。

这个包实现了一个泛型 Levenshtein 算法，适用于任何可以比较和克隆的类型序列。

除此之外，它还允许你生成一个 Edit 值序列，表示将应用于源序列的转换，以将其转换为目标序列。还提供了一个将编辑应用于源序列并重新构建目标序列的函数。

特性

• Levenshtein 算法的三种实现：朴素递归、DP 表格和 DP 记忆化。如果你想要分析和比较性能，这将很有用。
• 生成编辑序列，当应用于源序列时，可以重新生成目标序列。当需要高效地与远程副本同步序列时，这很有用。
• 一个函数，可以将编辑应用于序列以生成目标序列。
• 泛型：适用于任何实现了 PartialEq（尽管如果你想要使用生成和应用的编辑相关的功能，序列还将需要实现 Clone）的类型序列。

用法

在你的 Cargo.toml

[dependencies]
levenshtein-diff = "0.2.4"

在你的项目中

    use levenshtein_diff as levenshtein;

    // This example uses strings
    let source = "SATURDAY";
    let target = "SUNDAY";

    let expected_leven = 3;

    // dist: usize is the Levenshtein distance, and the mat is the distance matrix
    let (dist, mat) = levenshtein::distance(source.as_bytes(), target.as_bytes());

    assert_eq!(expected_leven, dist);

    // Generate a sequence of edits (i.e. differences between source and target)
    let edits = levenshtein::generate_edits(source.as_bytes(), target.as_bytes(), &mat)
        .unwrap_or_else(|err| panic!(err));

    // Apply edits to source to regenerate target. This results in a Vec
    let generated_target_vec = levenshtein::apply_edits(source.as_bytes(), &edits);

    // Convert the vector from above into a string
    let generated_target = match std::str::from_utf8(&generated_target_vec) {
        Ok(v) => v,
        Err(e) => panic!("Invalid UTF-8 sequence: {}", e),
    };

    assert_eq!(target, generated_target);