LevenshteinAutomaton

Namespace

Rowles.LeanCorpus.Codecs.Fst

Assembly

Rowles.LeanCorpus.dll

Levenshtein DFA accepting strings within edit distance maxEdits of a reference term. Built via NFA-to-DFA subset construction at construction time to correctly handle deletions (ε-transitions that advance position without consuming input). Operates on UTF-8 bytes.

public sealed class LevenshteinAutomaton : IAutomaton

Inheritance

object

LevenshteinAutomaton

Implements

IAutomaton

LevenshteinAutomaton(ReadOnlySpan<byte>, int)

Initialises a new LevenshteinAutomaton from a raw UTF-8 byte representation of the term.

LevenshteinAutomaton(string, int)

Initialises a new LevenshteinAutomaton for the given term and maximum edit distance.

MaxEdits

Maximum edit distance the automaton was constructed with.

Start

Initial state of the automaton.

CanMatch(int)

Returns true if the automaton could potentially accept any string starting from the given state. Used for early pruning during intersection. Returns false only if the state is dead (no path to any accept state).

IsAccept(int)

Returns true if the given state is an accepting state.

MinDistance(int)

Returns the minimum edit distance achievable when this state is accepting, or MaxValue when no NFA state in the set reaches an accept. Used by fuzzy queries to recover the distance from an FST traversal that ended on this state.

Step(int, byte)

Transition function: returns next state given current state and input byte, or -1 if no transition.