# Fast Levenshtein Distance Using a Trie

Steve Hanov's classic 2009 post on efficient fuzzy dictionary search. The problem: given a misspelled word, find all dictionary words within N edits. The naive approach is too slow for large dictionaries. The trie-based approach is 300× faster.

## The naive approach

Compare the query against every word in the dictionary using the standard Levenshtein dynamic programming algorithm. For each word pair, fill an N×M table where each cell is the minimum of:
- Cell above + 1 (deletion)
- Cell to the left + 1 (insertion)
- Cell diagonally above-left + 0 or 1 (match or substitution)

Complexity: O(words × max_length²). For a 98,568-word dictionary: 4.5 seconds.

## The insight

When comparing "food" against "care" and then "cars", the naive approach rebuilds the entire table. But "care" and "cars" share a prefix. The Levenshtein table rows for "c", "ca", "car" are identical — only the final row differs.

A trie stores words with shared prefixes collapsed into single paths. If you traverse the trie depth-first, you process words in exactly the order that maximizes row reuse.

## The algorithm

Recursive DFS through the trie. Each call receives:
- The current trie node
- The letter at this node
- The target word
- The previous row (from the parent node)
- Results accumulator
- Maximum allowed edit distance

Each node computes one row:

```python
def searchRecursive(node, letter, word, previousRow, results, maxCost):
    currentRow = [previousRow[0] + 1]
    
    for column in range(1, len(word) + 1):
        insertCost = currentRow[column - 1] + 1
        deleteCost = previousRow[column] + 1
        replaceCost = previousRow[column - 1]
        if word[column - 1] != letter:
            replaceCost += 1
        currentRow.append(min(insertCost, deleteCost, replaceCost))
    
    # If this node completes a word and cost is acceptable
    if node.word and currentRow[-1] <= maxCost:
        results.append((node.word, currentRow[-1]))
    
    # Early termination: if min(row) > maxCost, no word below can match
    if min(currentRow) <= maxCost:
        for letter, child in node.children.items():
            searchRecursive(child, letter, word, currentRow, results, maxCost)
```

The early termination is key. If the minimum value in the current row exceeds `maxCost`, every word in this subtree is too far away. Prune the entire branch.

## Performance

Same 98,568-word dictionary: 0.014 seconds. Over 300× faster.

New complexity bound: O(max_length × trie_nodes). The trie has fewer nodes than the dictionary has total characters because prefixes are shared.

## Real-world application

The author used this for RhymeBrain. After importing Google's N-grams dataset (2.6 million words), queries still took only 19-50ms on a 1GHz netbook. No caching, no precomputation — just the trie and the algorithm.

## Alternatives

**Peter Norvig's spelling corrector** — Generate all possible 1-edit mutations of the query and check dictionary membership. Fast for edit distance 1, but "breaks down quickly" for larger distances because mutations grow exponentially.

**Levenshtein automata** — Construct a regex/NFA matching all strings within N edits, then intersect with the dictionary. More complex to implement ("big honking gobs of code") but can be faster for very large dictionaries.

## Memory

Tries are memory-hungry. The article references follow-up work on DAWG (Directed Acyclic Word Graph) structures that share suffixes as well as prefixes, dramatically reducing node count.

See also [[inverted-index]] for a different approach to search indexing, [[full-text-search-indexeddb]] for another fuzzy search implementation.