Struct porigon::LevenshteinAutomatonBuilder

pub struct LevenshteinAutomatonBuilder { /* fields omitted */ }

Builder for Levenshtein Automata.

It wraps a precomputed datastructure that allows to produce small (but not minimal) DFA.

Methods

impl LevenshteinAutomatonBuilder

pub fn new(
    max_distance: u8,
    transposition_cost_one: bool
) -> LevenshteinAutomatonBuilder

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

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

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(...).