When you type a query with a typo (such as recieve instead of receive, or calender instead of calendar), the search engine still returns relevant results. It does this by finding indexed terms that are close enough to your query under edit distance (insertions, deletions, substitutions). The naive approach would compare your query against every word in the dictionary, but that would be far too slow for a dictionary of any real size.

Typo-tolerant search solves this with a clever indexing trick: it builds a trie (a prefix tree) of all dictionary terms, then walks that trie with a pruning automaton that tracks how many edits have been used so far at each node. As soon as a branch of the trie is guaranteed to exceed the allowed edit budget, the automaton stops exploring it, skipping entire subtrees of words in a single decision. This is the same core mechanism used by Lucene, Elasticsearch, and many spell checkers to deliver fast fuzzy results.

The interactive walk below shows this in action. Type a word, choose the maximum number of edits the search should tolerate, and step through the trie to watch the automaton decide which branches to explore and which to prune.

This automaton walk is one technique inside a full typo-tolerant search system. Other approaches include n-gram indexes, SymSpell candidate generation, and ranking strategies for fuzzy results.

What the Walk Shows

The trie on the left contains about twenty common English words. Each circle is a character, and each path from the root to a diamond marker is a complete word. As the automaton walks through the trie:

• Blue nodes: the automaton’s current position as it checks each prefix.
• Green nodes: dictionary words that the automaton accepted (they are within the edit budget).
• Red nodes: words the automaton checked but rejected (too many edits away from the query).
• Gray, faded branches: subtrees that were pruned because continuing would exceed the edit budget no matter what characters came next.

The sidebar on the right lists every accepted word with its exact edit distance. Click any accepted word to see the full Levenshtein distance matrix for that query–word pair. Hover any active node to inspect the distance computation at that position.

Why Pruning Makes Typo Tolerant Search Fast

The key performance insight is visible in the walk: the automaton doesn’t visit every node. At each step it computes a lower bound: the minimum edit distance between the query and any word that passes through this node. When that lower bound exceeds the edit budget, the automaton stops and never visits the children. For short edit distances (1 or 2 edits), this prunes the vast majority of the trie.

Compare the walk at max edits = 1 versus max edits = 2. At distance 1, most branches are grayed out immediately: only words that start with a letter close to the query’s first character survive past the first level. At distance 2, more branches become reachable, but the automaton still skips wide regions. A dictionary of 100,000 words needs only a few hundred node visits for most queries, instead of 100,000 pairwise comparisons.

Where This Mechanism Is Used

The trie-with-automaton approach is the standard implementation for fast fuzzy search in production systems:

• Elasticsearch and Lucene build a Levenshtein DFA at query time and walk the indexed term dictionary in one pass. The fuzziness parameter controls the edit budget.
• Spell checkers (including operating system and browser spell check) use the same technique to find correction candidates without scanning the full dictionary.
• “Did you mean?” suggestions rely on the automaton to generate candidate corrections ranked by distance and frequency.

Because the automaton size grows exponentially with the edit distance, production systems typically limit fuzziness to 1 or 2 edits, or use an auto setting that adjusts the budget based on the word length.

Going Deeper

This automaton walk fits alongside other approaches like n-gram indexing and SymSpell, each with different tradeoffs for speed, memory, and accuracy in production search.