Fuzzy string matching algorithms compare text by similarity rather than exact equality, and the choice of algorithm changes which pairs are accepted as matches. The main families are character-based edit distance, comparator-based name matching, token-based word comparison, phonetic encoding, and n-gram chunk overlap. Each answers a different question about what “close” means.

The table below surveys the major algorithm families with their operation model, best use, and main limitation.

Algorithm	Operation model	Best for	Weakness
Levenshtein distance	Insert, delete, substitute	General spelling errors, local typos	Treats transpositions as two edits; equal weight on all character positions
Damerau-Levenshtein	Insert, delete, substitute, adjacent transposition	Manual typing errors where swapped letters are common	Still character-level; ignores word order and token-level differences
Jaro / Jaro-Winkler	Matching characters within a window, prefix bonus	Short names, personal record linkage	Can over-reward shared prefixes when the discriminating information is later
Token-based (token sort, token set, partial)	Compare word sets with set overlap, sorting, or subset matching	Product titles, addresses, free-form labels with word reordering	Loses character-level spelling nuance inside individual words
Phonetic (Soundex, Metaphone, Double Metaphone)	Encode by pronunciation rules	Name matching by sound across spelling variants	Language-dependent; many distinct names collapse to the same code
N-gram / trigram (e.g. pg_trgm)	Overlap of character-level chunks (n characters at a time)	Candidate generation, indexed approximate search	Not a standalone final score; chunk overlap can miss structural edit differences

These algorithm families are not mutually exclusive. A production pipeline often combines them: phonetic blocking to reduce the candidate set, token scoring for multi-word fields, and character-level distance for final ranking on fields where local spelling matters. For a deeper walkthrough of how edit distance, comparator choice, and thresholds work with interactive visualizations, see the full fuzzy matching tutorial.

Levenshtein Distance

Levenshtein distance is the most widely taught fuzzy matching algorithm because it gives similarity a precise, explainable meaning: the minimum number of single-character insertions, deletions, and substitutions needed to turn one string into another.

For kitten and sitting, the cheapest path is substitute k→s, substitute e→i, and insert g, for a distance of 3. The algorithm uses dynamic programming over a matrix of string prefixes, which means every cell represents the cheapest repair cost between the source prefix and target prefix up to that point.

A common normalized similarity score converts distance into a 0-to-1 value:

$$\text{similarity} = 1 - \frac{\text{edit distance}}{\max(\text{source length}, \text{target length})}$$

Levenshtein is a strong baseline when errors are local character mistakes such as misspellings. It is less informative when whole words are reordered, when abbreviations shorten or expand the string substantially, or when the beginning of the string deserves different weight from the end.

Damerau-Levenshtein

Damerau-Levenshtein extends Levenshtein by adding one operation: adjacent transposition. When someone types recieve instead of receive, only two characters have swapped places. Plain Levenshtein counts this as two edits (two substitutions). Damerau-Levenshtein counts it as one operation, which often better matches the intuition that a single slip of the fingers is a minor error.

This makes Damerau-Levenshtein a practical upgrade when the text comes from keyboard entry rather than scanned or generated output. The tradeoff is the same as with Levenshtein: it still compares character by character, so word reordering, token-level abbreviations, and phonetic variants are outside its model.

Jaro and Jaro-Winkler

Jaro measures similarity by counting matching characters that appear within a limited window of their original positions and penalizing transpositions when matched characters are out of order. The window is roughly half the length of the longer string, which means Jaro does not require every character to line up in an edit script. This makes it naturally suited to short strings where a single character change is a large fraction of the total length.

Jaro-Winkler starts from the Jaro score and adds a controlled boost when the strings share a common prefix, typically up to the first four characters. For personal names, this prefix bonus often helps: Christa and Christy clearly share a root, and changing only the suffix should not produce the same penalty as changing the first letter. The risk is that the prefix bonus can reward the least discriminating part of the string when many records share a common start, such as brand names, legal prefixes, or family names in a small community.

The Jaro similarity formula:

$$\text{sim}_j = \begin{cases} 0 & \text{if } m = 0 \[6pt] \frac{1}{3}\left(\frac{m}{|s_1|} + \frac{m}{|s_2|} + \frac{m - t}{m}\right) & \text{otherwise} \end{cases}$$

where $m$ is the number of matching characters within the window and $t$ is half the number of transpositions. Jaro-Winkler then adds $p \cdot \ell \cdot (1 - \text{sim}_j)$ where $\ell$ is the length of the common prefix (up to 4) and $p$ is a scaling factor (commonly 0.1).

Use Jaro-Winkler for name fields where short strings and prefix agreement carry strong identifying signal. Avoid it for fields where common prefixes are not informative, such as product codes, addresses with repeated street-type suffixes, or categorical labels that all begin with the same classifier.

Token-Based Methods

Token-based methods shift the comparison up from characters to whole words. Instead of asking how many character edits separate two strings, they ask how much vocabulary the strings share.

Token sort splits both strings into words, sorts each list alphabetically, and compares the sorted result. This makes Jon Smith and Smith, Jon identical regardless of word order, which Levenshtein distance would treat as many edits because the characters are arranged differently.

Token set treats the strings as bags of words and measures overlap between the two sets. Extra words or duplicate tokens in one string do not necessarily break the match as long as the shared vocabulary is high enough. This is useful when one record contains extra middle names, titles, or unit suffixes that the other record omits.

Partial token matching checks whether the words from a shorter string appear inside the longer string as a consecutive or near-consecutive subset. This helps when matching a short query against a longer value such as a product title or a company name with legal suffixes.

Token methods handle word reordering and missing words well, but they can miss character-level typos inside individual words. A pipeline that first tokenizes and then applies a character-level comparator within matched tokens can capture both word-level structure and spelling detail.

Phonetic Encoding

Phonetic algorithms encode strings by how they sound rather than how they are spelled. The output is a short code that should be identical for strings that are pronounced similarly even when their written forms differ.

Soundex produces a letter followed by three digits, grouping consonants by phonetic similarity. Metaphone improves on Soundex with more detailed pronunciation rules and variable-length output. Double Metaphone produces two encodings to handle alternate pronunciations.

Phonetic methods are useful for name matching when spelling variation comes from transliteration, historical spelling changes, or inconsistent record-keeping. Smyth, Smith, and Smithe may all encode to the same Soundex code S530, which makes them retrievable as candidates even though their character sequences differ.

The main limitation is collisions. Many distinct names produce the same code, especially with the coarse grouping of Soundex. Phonetic rules are also language-specific, so a Soundex implementation tuned for English surnames will perform differently on names from other language backgrounds. Treat phonetic encoding as a candidate generation or blocking step rather than a final matching decision.

N-Gram and Trigram Methods

N-gram methods break strings into overlapping character chunks and compare chunk overlap. A trigram method, for example, splits martha into mar, art, rth, and tha, then checks how many of those chunks also appear in a candidate string.

The main practical advantage is indexability. Databases such as PostgreSQL with the pg_trgm extension can build indexes over trigrams and use them to find candidate strings quickly without comparing every pair. This makes n-gram methods the usual choice when the dataset is large enough that pairwise distance computation is too slow.

The main limitation is that trigram overlap does not measure edit structure. Two strings can share many trigrams while having a large edit distance, and very short strings produce so few trigrams that the overlap score is unreliable. N-gram similarity is therefore most useful as a retrieval step: narrow the candidate set with tri-gram overlap, then apply an edit-distance or token comparator for final scoring.

Preprocessing Comes First

No fuzzy matching algorithm performs well on raw text. Before any comparator runs, normalize the text. Common preprocessing steps include lowercasing, stripping extra whitespace, removing or normalizing punctuation, expanding known abbreviations (St. → Street), and handling accents.

Preprocessing choices can help or hurt depending on the data. Case-insensitive matching is almost always right for names and product titles but wrong for case-sensitive codes. Accent stripping may help when source systems store text inconsistently, but it erases information in languages where accents distinguish different words or names. Treat preprocessing as a deliberate step in the matching design, not as automatic cleanup.

Choosing an Algorithm

The right algorithm depends on the field being matched and the kind of error you expect.

• General spelling errors on single-word fields → start with Levenshtein or Damerau-Levenshtein.
• Manual typing that commonly swaps adjacent letters → prefer Damerau-Levenshtein.
• Short personal names → Jaro-Winkler, with attention to whether the prefix bonus helps or hurts your data.
• Multi-word values with possible reordering → token sort or token set.
• Short query inside a longer value → partial token matching or n-gram candidate search.
• Names with spelling variation from sound → phonetic encoding as a blocking step, followed by a more discriminating comparator.
• Large datasets that need candidate retrieval → trigram or n-gram indexes before pairwise scoring.

No single algorithm covers every use case well, which is why practical tools expose multiple scoring functions. The interactive fuzzy matching tutorial walks through edit distance with a visual repair matrix, compares Levenshtein, Jaro, and Jaro-Winkler on the same name pairs, and explains how thresholds, candidate generation, and preprocessing fit into a complete matching pipeline.

For an introduction to what fuzzy matching is and where it is used, see What Is Fuzzy Matching?.