Struct levenshtein_automata::LevenshteinAutomatonBuilder [−][src]
pub struct LevenshteinAutomatonBuilder { /* fields omitted */ }
Expand description
Builder for Levenshtein Automata.
It wraps a precomputed datastructure that allows to produce small (but not minimal) DFA.
Implementations
impl LevenshteinAutomatonBuilder
[src]
impl LevenshteinAutomatonBuilder
[src]pub fn new(
max_distance: u8,
transposition_cost_one: bool
) -> LevenshteinAutomatonBuilder
[src]
pub fn new(
max_distance: u8,
transposition_cost_one: bool
) -> LevenshteinAutomatonBuilder
[src]Creates a Levenshtein automaton builder. The builder
max_distance
- maximum distance considered by the automaton.transposition_cost_one
- assign a distance of 1 for transposition
Building this automaton builder is computationally intensive.
While it takes only a few milliseconds for d=2
, it grows exponentially with
d
. It is only reasonable to d <= 5
.
pub fn build_dfa(&self, query: &str) -> DFA
[src]
pub fn build_dfa(&self, query: &str) -> DFA
[src]Builds a Finite Determinstic Automaton to compute
the levenshtein distance to a fixed given query
.
There is no guarantee that the resulting DFA is minimal
but its number of states is guaranteed to be smaller
than C * (query.len() + 1)
in which C is a constant that depends
on the distance as well as whether transposition are supported
or not.
For instance for d=2
and with transposition, C=68
.
pub fn build_prefix_dfa(&self, query: &str) -> DFA
[src]
pub fn build_prefix_dfa(&self, query: &str) -> DFA
[src]Builds a Finite Determinstic Automaton that computes
the prefix levenshtein distance to a given query
.
Given a test string, the resulting distance is defined as
min( levenshtein(&test_string[..i], query } for i in 0..test_string.len() )
Which translates as the minimum distance of the prefixes of test_strings
.
See also .build_dfa(…).