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:

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.