Levenshtein Automata

Stop asking about two known strings. Build a recognizer for every string within N edits.

The question

Which strings are within N edits of my query?

The structure responsible

Levenshtein automaton (NFA determinized to a DFA)

In this lab: Build the automaton, feed it terms character by character, and watch dead states kill candidates early.

building the index…