Levenshtein-automaton

此 crate 使构建一个计算给定字符串 Levenshtein 距离的有限确定性自动机变得快速简单。

示例

use levenshtein_automata::{LevenshteinAutomatonBuilder, Distance};

fn main() {

    // Building this factory is not free.
    let lev_automaton_builder = LevenshteinAutomatonBuilder::new(2, true);

    // We can now build an entire dfa.
    let dfa = lev_automaton_builder.build_dfa("Levenshtein");

    let mut state = dfa.initial_state();
    for &b in "Levenshtain".as_bytes() {
        state = dfa.transition(state, b);
    }

    assert_eq!(dfa.distance(state), Distance::Exact(1));
}

实现基于以下论文 使用 Levenshtein 自动机的快速字符串校正 (2002)，由 Klaus Schulz 和 Stoyan Mihov 撰写。我还在以下 博客文章 中尝试解释它。

基准测试

构建 Levenshtein DFA 所需的时间强烈取决于其可以测量的最大距离和输入字符串的长度。

以下是构建字符串 "Levenshtein" 的 Levenshtein DFA 所花费的时间

dfa dist1 no transposition        35,627 ns/iter (+/- 3,237)
dfa dist1 with transposition      36,493 ns/iter (+/- 12,680)
dfa dist2 no transposition        97,137 ns/iter (+/- 14,556)
dfa dist2 with transposition     100,958 ns/iter (+/- 4,231)
dfa dist3 no transposition       834,412 ns/iter (+/- 158,329)
dfa dist3 with transposition   1,414,523 ns/iter (+/- 396,278)
dfa dist4 no transposition     4,716,365 ns/iter (+/- 869,024)
dfa dist4 with transposition   8,044,162 ns/iter (+/- 594,523)