Levenshtein distance for names and where it misleads on short surnames

Somebody sets the matcher to accept any pair of surnames within two edits, runs it over a registration file for an Asian manufacturing show, and produces a merge queue with forty thousand pairs in it. Nothing is broken. Levenshtein distance for names is behaving exactly as defined, and the definition does not know that Chan and Chen are two people.

The measure is worth having and it is worth understanding where it stops being evidence. That boundary sits almost entirely at the short end of your surname distribution, which in most international attendee files is a large and growing share of the rows.

What edit distance counts

Levenshtein defined the measure in Soviet Physics Doklady in 1966, in a paper about codes that can correct deletions, insertions and reversals in transmitted binary strings. Applied to text, it is the smallest number of single character operations that turn one string into another, where the permitted operations are inserting a character, deleting a character and substituting one character for another.

Smith to Smyth is one substitution, so the distance is 1.

Smith to Smithson is three insertions, so the distance is 3.

Smith to Jones is five substitutions, so the distance is 5, which happens to be the length of the word, and that is the ceiling: the distance between two strings can never exceed the length of the longer one.

Computing it is a table. For strings of length m and n you fill an m by n grid, each cell taking the cheapest of three neighbours, so comparing two twelve character surnames costs 144 cell evaluations. Across 2.4 million candidate pairs that is about 346 million cell evaluations, which is seconds of work and not a reason to avoid the measure.

Why does a threshold of 2 misfire on short surnames?

Because a fixed number of edits is a different proportion of a short name than of a long one, and surnames are not evenly distributed across lengths.

Take nine surnames that appear together on the badge list of any large manufacturing show: Chan, Chen, Chin, Chun, Chao, Chow, Shan, Khan and Chang.

Measure each against Chan. Chen, Chin and Chun are one substitution away. Chao is one substitution away, at the last character instead of the third. Shan and Khan are one substitution away at the first character. Chang is one insertion away. That is seven names at distance 1. Chow needs two substitutions, so it joins at distance 2.

Eight distinct surnames, belonging to eight sets of unrelated people, all inside a threshold of 2. A rule that merges at distance 2 merges the lot.

Now run the same threshold on a long name. Wojciechowski against Wojcechowski is one deletion, so distance 1, and those two rows are the same person with something close to certainty. Blomqvist against Blomkvist is one substitution, and Andersson against Anderson is one deletion. In each case a single edit on a nine or thirteen character surname is strong evidence of a match, and the identical single edit on a four character surname is worth nothing at all.

One threshold cannot serve both. The measure is fine. The threshold is the mistake.

Normalising by length, and what it fixes

Convert the distance into a similarity before you threshold it. The usual form is 1 minus the distance divided by the length of the longer string.

Chan against Chen becomes 1 minus 1 over 4, which is 0.75.

Wojciechowski against Wojcechowski becomes 1 minus 1 over 13, which is 0.923.

Smith against Smithson becomes 1 minus 3 over 8, which is 0.625.

Blomqvist against Blomkvist becomes 1 minus 1 over 9, which is 0.889.

Now a single cut at 0.85 keeps the two pairs you want and rejects the two you do not, which no integer threshold could do. The normalisation has not added information, it has stopped the measure from throwing information away, and the information it was throwing away was length.

This is the same behaviour that makes the prefix weighted comparator in J12 easier to threshold: it returns a bounded similarity rather than a count, so pairs of different lengths land on a comparable scale. What edit distance still lacks after normalising is any sense of where in the string the difference sits, and that is the gap the prefix bonus was built to fill.

Even normalised, the short end stays hard. Chan against Chen at 0.75 is close to Chan against Chun at 0.75, and both are close to genuine variant spellings of the same name. At four characters there is not enough string to carry a decision, and the honest response is to stop asking the surname to carry it. Route short surnames to a rule that requires a second field to agree, and let the length of the name decide which rule applies.

The fourth operation Levenshtein left out

Damerau published a note on detecting and correcting spelling errors in Communications of the ACM in 1964, two years earlier, and identified four kinds of single character mistake: a wrong letter, a missing letter, an extra letter and a transposition of two adjacent letters.

Plain Levenshtein handles the first three and charges double for the fourth. Bergstrom against Bergsrtom, where the typist hit t and r in the wrong order, comes out at distance 2, priced identically to a name with two unrelated wrong letters. Damerau-Levenshtein adds transposition as its own operation and prices it at 1.

On data typed by a person into a form on a phone at a registration desk, transposition is common enough that the difference changes queue sizes. It costs nothing to switch: the algorithm is the same table with one extra comparison per cell, and every serious library implements both. Use the transposition aware version on name fields and the plain version on codes where a swapped pair genuinely is two errors.

What is edit distance actually good for?

Two jobs, and neither of them is scoring a name pair on its own.

The first is a cheap filter during candidate pair generation. A hard cap, such as refusing to compare any pair whose surnames differ in length by more than three characters, throws out an enormous number of pairs for almost no computation and loses very few true matches. Filtering is where an integer distance behaves well, because you are asking a yes or no question about an obvious limit and not asking the number to express confidence.

That particular filter is exact rather than approximate, which is worth knowing before you rely on it. Turning a five character string into a nine character one requires at least four insertions, so the difference in length is a floor on the distance and no pair below the floor can be a match under your threshold. You can discard those pairs without computing anything, and you have lost nothing, because the arithmetic guarantees the answer. Filters with that property are the only ones safe to apply before a comparison instead of after it.

The second is comparison inside a token. Company names differ by whole words, which is why token overlap suits them, but the individual tokens still get mistyped. Running an edit based comparison within a token and a set based measure across tokens is the hybrid shape that Cohen, Ravikumar and Fienberg found strongest on name matching tasks at the IJCAI workshop on Information Integration on the Web in 2003.

Both uses share a property. The distance is doing a bounded, mechanical job with a clear failure mode, and something else is carrying the decision.

Where this stops

Edit distance measures keystrokes. Names carry meaning that keystrokes do not.

The clearest case is names written in different scripts or transliterated by different conventions. Zhang and Chang are the same surname romanised under two systems, and their edit distance is 1, exactly the same as Chan to Chen. Nothing in the measure knows that one pair is a transliteration and the other is two families. That work belongs to phonetic encoding in J15, which is built for exactly this and has its own costs.

The second limit is order. Edit distance on a full name field punishes reordering severely, so Anna Maria Kowalski against Kowalski Anna Maria scores badly despite being the same string of tokens in a different sequence, and eastern European and east Asian registration forms produce that reordering constantly. Parse the field into components first and compare component to component, or use a measure that ignores order.

The third is the one that catches teams by surprise. Edit distance is symmetric and context free, so it gives the same answer whether the pair came from a file of 500 rows or 500,000. In a large file, thousands of distinct people sit within one edit of each other, and the number of false pairs at any fixed similarity grows with the square of the file while the number of true pairs grows roughly linearly. A threshold that was correct last year on one show is too loose this year across the portfolio, and nobody gets told. Deciding which measure belongs on which field, which is J16, includes deciding how often to re-test the thresholds against a labelled sample.

Take 200 surnames from your largest registration file, group them by character length, and count how many pairs within each length group sit at distance 1. If the four and five character group has a hit rate several times the ten character group, which it will, you have the size of the problem in your own data, and the fix is a length aware threshold in the unified data pipeline rather than a better string function.