The core problem: exact matching won't catch near-duplicates. You need a similarity metric that:

Catches minor variations (typos, abbreviations, punctuation).
Doesn't overmatch (treating 'John Doe' and 'Jane Doe' as the same).
Scales to millions of records.

The algorithms:

Levenshtein distance (edit distance). Minimum edits (inserts/deletes/substitutes) to transform one string into another. Good for typos. 'Jon' → 'John' = 1. Simple but computationally expensive at scale.
Jaro-Winkler. Similarity score (0-1) that weights prefix matching heavily. Good for names where first letters are usually right. Works better than Levenshtein for person-name matching.
Trigram (N-gram) similarity. Break strings into overlapping 3-character chunks; measure Jaccard overlap. 'john doe' → {'joh', 'ohn', 'hn ', 'n d', ...}. Scales better than edit distance; built into Postgres (pg_trgm).
Phonetic encoding (Soundex, Metaphone, NYSIIS). Encode names by sound, not spelling. 'Smith' and 'Smyth' both encode to 'S530'. Good for imprecise transcription but crude for modern datasets.
Embeddings / BERT-based. For serious production: encode each name as a vector using a language model, measure cosine similarity. Handles semantic variants ('Bob' vs. 'Robert'). Expensive.

The practical pipeline:

Pre-process. Lowercase, strip punctuation, remove suffixes ('Jr.', 'III'), handle common substitutions ('J.' → 'John' where clear).
Block / bucket. Don't compare every record to every other record (N² is expensive). Block by something cheap — first letter of last name, last 4 digits of phone, zip code. Only compute similarity within blocks.
Compute similarity within blocks. Jaro-Winkler or trigram per pair.
Threshold. Pairs above some similarity (say, 0.90) are candidates for merge. Pairs in the 0.75-0.90 range flag for human review.
Use auxiliary fields. Two records with same name but different emails are likely different people. Use secondary features to confirm/reject matches.

Example SQL with pg_trgm (PostgreSQL):

SELECT a.id, b.id, similarity(a.name, b.name)
FROM customers a
JOIN customers b ON a.id < b.id
  AND a.last_name_initial = b.last_name_initial  -- blocking
WHERE similarity(a.name, b.name) > 0.85
ORDER BY similarity DESC;

Pitfalls:

Over-matching. 'John Doe' and 'Jane Doe' are 0.75 similar; you might merge them if your threshold is 0.70.
Under-matching. 'John Doe' and 'Doe, John' are 0.30 similar by Levenshtein. Pre-process to unify order.
Missing matches with typos in low-entropy prefixes. 'Jane' and 'Jean' are 1 edit apart but probably different people.
Performance. At 1M records, pairwise comparison is 10^12 ops. Blocking is essential.

When to use what:

Small datasets (<10K): Levenshtein, simple thresholds.
Medium (10K-10M): trigram + blocking, operationalized with Postgres.
Large (>10M): phonetic pre-filter + trigram, or ML-based embeddings.

What senior candidates add:

Entity resolution frameworks: Dedupe.io, Splink, Zingg. Production-grade, probabilistic matching.
Privacy implications. Aggressive matching can link data across systems that legally shouldn't be linked. Check compliance.
Human-in-the-loop. For high-stakes merges (customer service, legal), flag ambiguous matches for human review rather than auto-merge.

When do you need fuzzy string matching, and what's the approach?

Draft your answer

Stuck? Peek at a hint

More data cleaning questions