Crate levenshtein_automata [−] [src]
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 |