Comparing strings honestly

Ask a room to say whether "Katherine" and "Catherine" are the same name and most people say yes instantly. Ask them to say by how much and the room goes quiet, because similarity is not one thing. An edit-distance measure, a phonetic code and a token-overlap measure all answer a different question, and each was built to catch a different kind of typing mistake.

• Positional measures care where in the string the difference sits, and how many character-level operations it takes to fix it.
• Phonetic measures throw the spelling away entirely and compare how the word would sound if read aloud.
• Token measures throw the order away and compare which words appear, which is exactly wrong for edit distance and exactly right for a name typed in the wrong order.

Every number quoted from here on is read off the live widget lower in this page, not typed in by hand. Type any two strings into it and all seven measures recompute immediately, with the Soundex code for each printed underneath. Six presets are loaded to get you started - Katherine/Catherine, Mary Ann/Mray Ann, Robert Chen/Chen Robert, Thomas Muller/Thomas Mueller, Smith/Smyth, and Priya Nair/Priya Nayar - but the free-text boxes are the point. If a claim in this session sounds surprising, retype the pair yourself before you believe it.

Levenshtein distance (1965/66, published in Soviet Physics Doklady) is the minimum number of single-character insertions, deletions and substitutions needed to turn one string into the other. It is the oldest of tonight's measures and still the default most people reach for, because it needs no assumptions about language or pronunciation, only characters.

Its blind spot is exactly the mistake humans make most: swapping two adjacent letters. Levenshtein has no operation called "swap", so a transposition has to be expressed as a substitution plus an insertion or deletion, which prices it at 2 instead of the single slip it actually is. "Mary Ann" against "Mray Ann" is over-penalised for precisely this reason, and the lab below will show you the number.

Damerau-Levenshtein (Damerau, 1964, Communications of the ACM) adds a fourth operation, transposing two adjacent characters, at a cost of 1. It is built directly from an empirical observation Damerau made about real typing errors: the overwhelming majority of single mistakes are one of insertion, deletion, substitution or an adjacent transposition, so a distance that prices all four correctly should track real typos far better than one that only has three.

It still has two limits worth naming. It is still positional - it does not know that "ph" and "f" can sound the same, or that "Muller" and "Mueller" are the same transliterated name spread across more than one adjacent swap. And it is still blind to phonetics entirely: nothing in either edit distance knows what a word sounds like, which is what Part 3 exists to fix.

Jaro similarity (1989) was built for short strings like personal names. It finds characters that match within a small window of each other's position, counts how many matched characters are out of order (transpositions), and combines match count and transposition count into a score between 0 and 1. Because matches only count within a window, it copes reasonably with characters shifting position by a little, and it copes badly with long strings where whole tokens have been reordered - a job token measures do far better, in Part 3.

Jaro-Winkler (Winkler, 1990) adds a bonus for agreement at the very start of the string: JW = Jaro + L × P × (1 - Jaro), where L is the common prefix length, capped at 4 characters, and P is the prefix scale, 0.1 by default. The cap exists because Winkler found the earliest characters of a name are the most reliably typed ones in practice - a reasonable bet for Western given names, and the reason 0.1 is the default rather than something larger: push P above 0.25 and the formula can push the score above 1, which is not a valid similarity any more.

The prefix assumption is not arbitrary, it is tuned to Western given and family names, where data-entry errors cluster toward the end of a long word and the first few letters are usually typed carefully and read carefully. That is a real, useful bias for a lot of Meridian's data. It stops being useful the moment the variation lives at the front: transliterated names, prefixed titles, and any name where two cultures romanise the leading sound differently will all get zero help from L, no matter how similar the rest of the string is.

The practical rule that falls out of this: Jaro-Winkler is a good default for Western personal names typed by a careless human, and a poor default for anything transliterated, anything token-reordered, or anything where the difference is structurally at the start. Know which kind of dirt you are looking at before trusting the prefix bonus to catch it.

Jaccard similarity on token sets (Jaccard, 1901) treats a string as a bag of words and scores the overlap: shared tokens divided by all tokens across both sides. It is completely order-independent, which is exactly what "Robert Chen" against "Chen Robert" needs - both sides are the set {robert, chen}, so Jaccard reports 1. Its failure sits one level down: it treats a token as atomic, so "Jon" and "John" are two entirely different tokens with zero overlap between them, even though a human reads them as the same name missing one letter. Jaccard cannot see inside a token at all.

Cosine similarity on TF-IDF vectors (the vector-space model, Salton) fixes a different problem: not every shared token is equally informative. "Ltd" and "Inc" appear in hundreds of company names and should barely move a similarity score, while a distinctive word like "Northwind" should move it a lot. TF-IDF weighting down-weights the common tokens automatically, which is exactly the property you want for company-name matching. Its failure is structural rather than conceptual: the "IDF" half of the name needs a corpus to estimate how rare a token actually is, and on a tiny corpus - Meridian's few dozen company names, or any young dataset - those rarity estimates are unstable and can swing the score around for reasons that have nothing to do with the two strings being compared.

Soundex (Robert Russell and Margaret Odell, US patents 1,261,167 of 1918 and 1,435,663 of 1922) is the oldest phonetic code in production use anywhere, predating every other measure in this session by decades. It keeps the first letter of a name as-is, converts the rest of the consonants into a small set of digit codes for similar-sounding groups, drops vowels entirely, and pads or truncates the result to four characters. "Smith" and "Smyth" collapse onto the same code because Soundex never looks at the vowel that differs.

The same mechanism is also its failure. A four-character code is a very small space, so genuinely different names collapse onto the same code far more often than seems safe, and the whole scheme was designed around English orthography and consonant sounds - it degrades on names built from other phonetic systems. Type two names that sound similar into the lab and read the codes it prints underneath; a match there is a hint worth checking, never a verdict on its own.

Metaphone (Lawrence Philips, 1990, published in Computer Language) improved on Soundex's rule set for English pronunciation but still returns one code, which means it still cannot represent a name with two legitimate pronunciations. Double Metaphone (Philips, 2000, C/C++ Users Journal 18, pages 38 to 43) fixes exactly that: it returns a primary and a secondary code, so a name that could plausibly be pronounced two ways - many Slavic, Germanic, Celtic, Greek and Hispanic surnames among them - carries both possibilities forward instead of forcing a single guess.

Every measure above runs on whatever text it is handed, and what it is handed is usually the product of a normalisation step that ran first: expanding nicknames, standardising transliteration, abbreviating or expanding street types, stripping company suffixes, or reducing a phone number to digits only. None of the seven measures know this happened. That is exactly the risk - normalisation destroys the original difference before any measure gets a chance to weigh it.

• Nickname lists. Folding "Bob" into "Robert" and "Mike" into "Michael" recovers real matches a string measure alone would score low. It also assumes a nickname always means the same underlying formal name, which is not universally true.
• Transliteration. "Muller" and "Mueller" are the same German surname written two ways after the umlaut is dropped or expanded. A transliteration table catches this reliably; a raw edit distance sees two substitutions and one insertion.
• Street abbreviation. "Street" and "St", "Court" and "Ct" need a lookup table, not a smarter string measure, because the shortening is a convention rather than a spelling error.
• Phone digits only. Stripping formatting down to digits turns "0412 336 908" and "+61 412 336 908" into comparable strings, though it also throws away the country-code information that would otherwise tell you the numbers are formatted for different markets.
• Company suffix stripping. Removing "Ltd", "Inc", "Limited" and similar tokens correctly joins "Northwind Ltd" and "Northwind Limited". It also correctly joins "Northwind Ltd" and "Northwind Pty Ltd" if those happen to be separate legal entities, which is the trade you are actually making.

Folding "Katherine" and "Catherine" together at the normalisation stage correctly joins the one pair in Meridian where that is the right call, and it risks wrongly joining two different people elsewhere in a larger dataset who happen to share that variant spelling by coincidence rather than by being the same person. There is no version of normalisation that avoids this trade - the honest move is to make the bet visible, not to pretend cleaning the data removed the judgement call.