Trait fst::Automaton [−] [src]

pub trait Automaton {
    type State;
    fn start(&self) -> Self::State;
    fn is_match(&self, state: &Self::State) -> bool;
    fn can_match(&self, state: &Self::State) -> bool;
    fn accept(&self, state: &Self::State, byte: u8) -> Self::State;
}

Automaton describes types that behave as a finite automaton.

All implementators of this trait are represented by byte based automata. Stated differently, all transitions in the automata correspond to a single byte in the input.

This implementation choice is important for a couple reasons:

  1. The set of possible transitions in each node is small, which may make efficient memory usage easier.
  2. The finite state transducers in this crate are all byte based, so any automata used on them must also be byte based.

In practice, this does present somewhat of a problem, for example, if you're storing UTF-8 encoded strings in a finite state transducer. Consider using a Levenshtein automaton, which accepts a query string and an edit distance. The edit distance should apply to some notion of character, which could be represented by at least 1-4 bytes in a UTF-8 encoding (for some definition of "character"). Therefore, the automaton must have UTF-8 decoding built into it. This can be tricky to implement, so you may find the utf8-ranges crate useful.

Associated Types

type State

The type of the state used in the automaton.

Required Methods

fn start(&self) -> Self::State

Returns a single start state for this automaton.

This method should always return the same value for each implementation.

fn is_match(&self, state: &Self::State) -> bool

Returns true if and only if state is a match state.

fn can_match(&self, state: &Self::State) -> bool

Returns true if and only if state can lead to a match in zero or more steps.

If this returns false, then no sequence of inputs from this state should ever produce a match. If this does not follow, then those match states may never be reached. In other words, behavior may be incorrect.

If this returns true even when no match is possible, then behavior will be correct, but callers may be forced to do additional work.

fn accept(&self, state: &Self::State, byte: u8) -> Self::State

Return the next state given state and an input.

Implementors