Definition
Damerau-Levenshtein distance
Damerau-Levenshtein distance measures the minimum number of character insertions, deletions, substitutions and adjacent swaps needed to turn one string into another. With standard unit edit costs, identical strings have a distance of 0, and each edit costs 1.
Key Takeaways
- Damerau-Levenshtein supports insertion, deletion, substitution and adjacent character swaps.
- A neighbouring letter swap counts as one edit, compared with two in standard Levenshtein.
- Full Damerau-Levenshtein and Optimal String Alignment (OSA) can produce different results.
- Raw distance is an edit count; a similarity percentage requires a separate conversion.
- Use the score alongside other identifying fields when assessing potential record matches.
Damerau-Levenshtein Distance Calculator
Compare two values using insertions, deletions, substitutions and adjacent character transpositions.
These values differ by 1 edit.
Damerau-Damerau-Levenshtein distance counts the minimum number of insertions, deletions, substitutions and adjacent transpositions required to transform one value into the other.
WinPure AdaptiveMatch™ can combine Damerau-Levenshtein with other algorithms, thresholds and field-level logic to improve matching accuracy across real-world datasets.
What Is Damerau-Levenshtein Distance?
Damerau-Levenshtein distance measures the minimum number of edits needed to turn one string into another. With the standard cost of one per edit, it supports four operations: insertion, deletion, substitution and swapping two adjacent characters, known as a transposition.
That fourth operation distinguishes it from standard Levenshtein distance. For example, changing MARTHA to MARHTA requires one adjacent swap. Damerau-Levenshtein therefore returns a distance of 1, while standard Levenshtein returns 2.
A distance of 0 means the strings are identical. Lower distances indicate fewer edits, although the significance of an edit also depends on string length.
In data matching, the algorithm can help identify names and other text values affected by typing errors. It measures differences between strings; other fields should also contribute when deciding whether two records describe the same person or organisation.
How Does Damerau-Levenshtein Distance Work?
Damerau-Levenshtein compares two strings and finds the lowest-cost sequence of edits needed to transform one into the other. With standard unit costs, each insertion, deletion, substitution or adjacent transposition counts as one edit.
The algorithm typically uses dynamic programming, storing the results of smaller comparisons rather than repeatedly calculating them. It builds a matrix that tracks the minimum edit cost between portions of the two strings. Full Damerau-Levenshtein also keeps track of earlier character occurrences to account for transpositions correctly.
For example, changing FORM to FROM requires swapping the adjacent letters O and R. Damerau-Levenshtein counts this as one edit. Standard Levenshtein requires two edits because it does not include transposition as a separate operation.
The final result is an edit distance: 0 means identical strings, while larger values mean more edits are required. It is not a similarity percentage unless a separate normalisation formula is applied.
The full algorithm and the restricted Optimal String Alignment (OSA) variant can return different results when edits interact. We explain that distinction later in this guide.
The Four Edit Operations
Damerau-Levenshtein distance allows four types of edit. With standard unit costs, each operation adds 1 to the total distance.
| Operation | What it does | Example | Distance |
|---|---|---|---|
| Insertion | Adds one character. | JON → JOHN | 1 |
| Deletion | Removes one character. | JOHNN → JOHN | 1 |
| Substitution | Replaces one character with another. | SMITH → SMYTH | 1 |
| Adjacent transposition | Swaps two neighbouring characters. | FORM → FROM | 1 |
The first three operations are also supported by standard Levenshtein distance. Damerau-Levenshtein adds adjacent transposition, allowing a reversed pair of neighbouring letters to count as a single edit.
This does not mean that any rearrangement counts as one edit. Moving a character across several positions or reversing the order of whole words may require multiple operations.
Damerau-Levenshtein Examples
The examples below show how Damerau-Levenshtein handles individual typing errors and combinations of edits. All comparisons use a cost of 1 per operation.
| Original value | Compared value | Changes required | Distance |
|---|---|---|---|
| SMITH | SMITH | No changes | 0 |
| JON | JOHN | Insert H | 1 |
| SMITH | SMYTH | Replace I with Y | 1 |
| MARTHA | MARHTA | Swap the adjacent letters T and H | 1 |
| SMIHT | SMYTH | Swap H and T, then replace I with Y | 2 |
Worked Example: SMIHT → SMYTH
Two edits transform the first value into the second:
- SMIHT → SMITH: swap the adjacent letters H and T.
- SMITH → SMYTH: replace I with Y.
The Damerau-Levenshtein distance is therefore 2. Standard Levenshtein returns 3 because the adjacent swap requires two edits, followed by the substitution.
An edit distance describes the difference between the text values. For example, JOHN and JON are one edit apart, but they could still belong to different people. Other identifying fields are needed to assess a record match.
Damerau-Levenshtein vs Levenshtein
The main difference is how the algorithms handle adjacent transpositions. Standard Levenshtein distance allows insertions, deletions and substitutions. Damerau-Levenshtein also allows two neighbouring characters to be swapped as one operation.
Swapping the adjacent letters T and H requires two edits with standard Levenshtein, but only one with Damerau-Levenshtein.
| Feature | Levenshtein | Damerau-Levenshtein |
|---|---|---|
| Insertion, deletion and substitution | Supported | Supported |
| Adjacent transposition | Requires two edits | Counts as one edit |
| MARTHA → MARHTA | 2 | 1 |
| SMITH → SMYTH | 1 | 1 |
| Standard output | Minimum edit count | Minimum edit count |
Damerau-Levenshtein is useful when neighbouring letters are frequently entered in the wrong order. Levenshtein remains useful when missing, additional or substituted characters are the main source of variation.
Recognising transpositions can bring genuine spelling errors closer together, but it can also bring distinct values closer together. Neither algorithm is universally better for record matching: test both against representative data and assess the results alongside other identifying fields.
Full Damerau-Levenshtein vs Optimal String Alignment (OSA)
Two algorithms are often described as “Damerau-Levenshtein”: the full, unrestricted algorithm and the restricted Optimal String Alignment (OSA) variant. Both support insertion, deletion, substitution and adjacent transposition, but they differ when edits interact.
OSA restricts a substring from being edited more than once. Full Damerau-Levenshtein allows interacting edit sequences, such as transposing two characters and then inserting another character between them. As a result, the full algorithm can return a lower distance.
| Feature | Full Damerau-Levenshtein | OSA |
|---|---|---|
| Four edit operations | Supported | Supported |
| Restrictions on repeated edits to a substring | No OSA restriction | A substring cannot be edited more than once |
| CA → ABC, with unit edit costs | 2 | 3 |
| Triangle inequality | Satisfied with standard unit costs | Not always satisfied |
Why CA → ABC Produces Different Results
Full Damerau-Levenshtein transforms CA into ABC in two edits. OSA’s restrictions make its minimum distance three.
Full Damerau-Levenshtein can transform CA into ABC in two operations:
- CA → AC: transpose the adjacent characters.
- AC → ABC: insert B between them.
OSA does not allow this interacting edit sequence, so its minimum cost is 3. For a simple transposition such as MARTHA → MARHTA, both variants return 1.
When comparing calculators, libraries or matching tools, check which variant they implement. With unit costs and no input transformation, CA → ABC provides a useful diagnostic: a result of 2 is consistent with the full algorithm, while 3 is consistent with OSA. Different results may reflect the algorithm’s restrictions rather than an error in the calculation.
When Is Damerau-Levenshtein Distance Useful?
Damerau-Levenshtein is useful when text contains typing errors, especially neighbouring letters entered in the wrong order. It also handles missing, additional and substituted characters.
Common applications include:
- Name matching: identifying spelling variations such as MARTHA and MARHTA.
- Customer deduplication: finding candidate duplicate records when names contain small typing errors.
- Record linkage: comparing text fields across systems where values have been entered inconsistently.
- Search and spelling suggestions: finding values close to a mistyped query.
It is most helpful when character edits explain the differences between values. It does not directly recognise nicknames, pronunciation, abbreviations or the meaning of words. Phonetic algorithms can help with pronunciation-related variations, while token-based methods can help with reordered words. Nicknames and semantic relationships may require reference data or other matching methods.
For record matching, combine the text comparison with evidence from other fields. A similar name supported by an exact email address or consistent address details provides more context than an edit distance alone.
Limitations and False Matches
Damerau-Levenshtein measures character edits, so a low distance does not prove that two values identify the same person or organisation. JOHN and JOAN are only one edit apart, but they are distinct names.
- String length matters: one edit changes a larger proportion of a short name than a long value. A fixed distance threshold can therefore behave differently across fields.
- Meaning and pronunciation are not considered: nicknames, abbreviations and names that sound alike may remain several edits apart.
- Word order can inflate the distance: JOHN SMITH and SMITH JOHN require multiple character edits, even though they contain the same words.
- Data preparation affects results: capitalisation, punctuation, spaces and Unicode normalisation can change the distance unless handled consistently before comparison.
- Implementation choices matter: full Damerau-Levenshtein and OSA can return different distances when edits interact. Edit costs and normalisation methods can also vary.
Allowing transpositions may recover genuine typing errors, but it can also bring unrelated values within a matching threshold. Test known matches and non-matches, then use other fields to assess whether similar text represents the same entity.
Choosing a Matching Threshold
A matching threshold determines how much variation a comparison allows. For raw Damerau-Levenshtein distance, lower values are stricter: a maximum distance of 1 accepts fewer pairs than a maximum distance of 2.
Some tools convert edit distance into a similarity score. One common normalisation, for standard unit edit costs, is:
Similarity = 1 − (distance ÷ length of the longer string)
For two empty strings, define similarity as 1 rather than dividing by zero.
For example, MARTHA and MARHTA have a distance of 1 and a maximum length of 6. Under this formula, their similarity is approximately 0.8333, or 83.33%. This is a normalised string score, not an 83.33% probability that the records describe the same person. Other tools may use a different conversion.
Choose a threshold using representative data:
- Confirm the measure: check the algorithm variant, edit costs and whether the tool reports distance or similarity.
- Test known matches and non-matches: include short names, common names and realistic typing errors.
- Compare the trade-offs: review which genuine matches are missed and which unrelated records are accepted as the threshold changes.
- Consider other fields: decide how the name comparison contributes alongside address, email or other identifying evidence.
There is no universal threshold. A distance of 1 may be useful for generating candidates, but its significance depends on the string length, the data and the consequences of a false match.
Using Damerau-Levenshtein in AdaptiveMatch™
AdaptiveMatch™ lets you apply different matching algorithms to individual columns in WinPure Clean & Match Enterprise. Damerau-Levenshtein can contribute where typing errors, including adjacent letter swaps, are a common source of variation.
A matching rule could combine:
- Name: Damerau-Levenshtein to compare spelling differences and transposed characters.
- Address: WinPureFuzzy™ to assess textual similarity.
- Email: exact matching to check agreement on the email value.
AdaptiveMatch™ recommends configurations based on the type and characteristics of each column, while allowing users to review and adjust the algorithms, weights and thresholds. This places the name comparison within a wider matching rule, where evidence from other fields helps distinguish potential duplicates from unrelated records.
Turn spelling variations into potential matches
Compare names alongside addresses, emails and other identifying fields in WinPure Clean & Match Enterprise. Try it free for 30 days—no credit card required.
Frequently Asked Questions
Damerau-Levenshtein distance is the minimum number of insertions, deletions, substitutions and adjacent character transpositions needed to transform one string into another. With standard unit costs, each operation counts as one edit.
Damerau-Levenshtein treats swapping two neighbouring characters as one edit. Standard Levenshtein does not support transposition as a separate operation, so that swap requires two edits.
Optimal String Alignment (OSA) restricts a substring from being edited more than once. Full Damerau-Levenshtein allows interacting edit sequences. For example, CA to ABC has a full Damerau-Levenshtein distance of 2, but an OSA distance of 3.
It means the compared strings are identical. If a tool standardises the values first, the result refers to those prepared values rather than necessarily to the original text.
No. Its standard output is an edit count. A tool may convert that distance into a normalised similarity score, but the formula should be stated because conversions can differ.
There is no universal threshold. Test known matches and non-matches from your data, consider string length, and assess the results alongside other identifying fields. Confirm whether your tool reports distance or similarity before setting a threshold.
It compares characters rather than pronunciation. Phonetic algorithms such as Soundex or Double Metaphone may be more appropriate for names with different spellings but similar sounds.
No. A low edit distance indicates similar text, not shared identity. Address, email, date of birth or other relevant fields should contribute to the record-matching decision.
Share this article
