Spell Correction and Fuzzy Matching

Comparing two strings for approximate equality is a solved problem with a dynamic program from 1974. Finding the closest match to a string among ten million candidates is a completely different problem, and confusing the two is why fuzzy matching projects stall.

Two different jobs

Scoring a pair. Given two strings, how similar are they? Cheap, exact, well understood. Every algorithm below answers this.

Searching a set. Given one string and a dictionary, which entries are within distance k? This is where the engineering lives, because the naive approach — score the query against every entry — is linear in the dictionary and the scoring function is itself expensive. A million-entry dictionary at 10 microseconds per comparison is ten seconds per lookup, which is not a system.

The consequence is that every practical fuzzy matcher has two stages: generate a small candidate set cheaply, then score those candidates precisely. Choosing a distance function without choosing an indexing strategy is choosing half a design.

The algorithms and their complexity

Candidate generation is the whole game

Deletion neighbourhoods

Norvig’s well-known spelling corrector generates every string within edit distance one or two of the query and looks each up in a dictionary. For distance 1 over a 26-letter alphabet that is roughly 54n + 25 candidates for a length-n word — fine. For distance 2 it is hundreds of thousands, which is why it slows sharply.

SymSpell’s symmetric delete algorithm is the fix, and it is elegant: precompute, for every dictionary word, all strings obtained by deleting up to k characters, and index them. At query time generate the deletions of the query only — no insertions, substitutions or transpositions — and intersect. Because a substitution is a deletion on both sides and a transposition is two, deletions alone are sufficient to find every candidate within distance k. The cost moves from query time into index size, which is usually the right trade.

Indexes

A BK-tree (Burkhard and Keller, 1973) exploits the triangle inequality: since edit distance is a metric, comparing the query to one node lets you prune whole subtrees whose distance to that node makes a match impossible. Good for moderate dictionaries and in-memory use; it degrades as k grows because the pruning weakens.

An n-gram inverted index is the approach that scales and the one most production systems use. Index each dictionary entry under its character trigrams; at query time, retrieve entries sharing enough trigrams with the query, then score only those with a real edit distance. This is exactly the two-stage pattern from the similarity page, and it is why Elasticsearch’s fuzzy matching is affordable.

One prerequisite that is easy to forget: normalise both sides identically before any of this. Matching café against cafe should be handled by the folding key, not spent as one of your two edit operations.

Time it on your own strings

Published complexity tells you how each scales; only your own data tells you the constants, because they depend heavily on string length and alphabet. This harness takes a minute to run:

import random, timeit
from rapidfuzz.distance import Levenshtein, DamerauLevenshtein, JaroWinkler

pairs = [(a, b) for a, b in random.sample(list(zip(left, right)), 2000)]

for name, fn in [("levenshtein", Levenshtein.distance),
                 ("damerau",     DamerauLevenshtein.distance),
                 ("jaro_winkler", JaroWinkler.similarity)]:
    t = timeit.timeit(lambda: [fn(a, b) for a, b in pairs], number=5) / 5
    print(f"{name:14s} {t / len(pairs) * 1e6:7.2f} us/pair")

# and the number that actually decides the design:
print("naive scan of a 1M dictionary:",
      1_000_000 * (t / len(pairs)), "seconds per lookup")

The last line is the point. Whatever the per-pair time turns out to be, multiply it by your dictionary size and you will find out immediately whether you need an index or whether a linear scan is fine. For a 10,000-entry dictionary it usually is; at a million it never is.

Names are a special case

Personal and company names break the assumptions edit distance makes, and record linkage has its own literature for that reason.

• Component reordering. Smith, John against John Smith is a large edit distance and a perfect match. Tokenise and compare as a set of components before comparing as strings.
• Nicknames and initials. Bob and Robert, J. Smith and John Smith. No distance function derives these; they need a lookup table.
• Transliteration. The same Arabic, Chinese, Russian or Greek name has several accepted Latin spellings that are not close in edit distance.
• Phonetic keys. Soundex (1918) and Metaphone / Double Metaphone (Philips, 1990 and 2000) map names to codes by how they sound, so Smith and Smyth collide. Useful for candidate generation, but built around English phonology and correspondingly weak on names from elsewhere — which makes them a fairness problem as well as an accuracy one if the output affects people.

The workable design is a weighted combination — phonetic key or trigram index for candidates, then a score blending Jaro-Winkler on the surname, a nickname table on the given name, and exact agreement on any structured field you have such as a date of birth or postcode. And for anything consequential, a threshold band in the middle that goes to a human, because merging two different people is a much more expensive error than failing to merge one.