Crate levenshtein_automata

Build a deterministic finite automaton (DFA) that computes the levenshtein distance from a given string.

Example

use levenshtein_automata::{LevenshteinAutomatonBuilder, Distance};

// 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));

The implementation is based on the following paper Fast String Correction with Levenshtein-Automata (2002) by by Klaus Schulz and Stoyan Mihov. I also tried to explain it in the following blog post.

Structs

DFA	Implementation of a Deterministic Finite Automaton for a Levenshtein Automaton targeting UTF-8 encoded strings.
LevenshteinAutomatonBuilder	Builder for Levenshtein Automata.

Enums

Distance

Levenshtein Distance computed by a Levenshtein Automaton.

Constants

SINK_STATE

Sink state. See DFA