Is this the same as Levenshtein distance?

No. The additional adjacent-swap operation can reduce the minimum edit count.

Does it understand synonyms?

No. It compares symbol sequences rather than meanings; semantic retrieval addresses a different problem.

Can I turn the score into a percentage?

A documented normalization can create a bounded similarity score, but that percentage is not automatically a calibrated probability.

AI Glossary / Mathematics and optimization / Intermediate

Damerau - Levenshtein distance

Definition

Damerau - Levenshtein distance measures the smallest number of edits needed to transform one string into another when the permitted unit-cost operations are inserting a symbol, deleting a symbol, replacing a symbol, and swapping two adjacent symbols. It extends ordinary Levenshtein distance by recognizing an adjacent transposition as one edit.

What it means

The distance answers a precise spelling-level question: how cheaply can one sequence be changed into the other under these rules? A value of zero means identical sequences, while a small positive value indicates a short edit path.

This is useful when typing mistakes include reversed neighboring letters. It does not establish that two names identify the same person, or that two sentences mean the same thing. The symbols might be characters or other explicitly defined sequence units; that choice changes what an edit means.

How it works

A calculation considers competing edit paths and selects the least costly one. Efficient implementations use dynamic programming and additional bookkeeping for transpositions, rather than explicitly listing every possible edited string.

The full distance permits further edits involving a previously edited substring. Optimal string alignment, often called restricted Damerau - Levenshtein distance, imposes a restriction on repeated substring editing. The names can be confused in software, so the exact function matters.

With the standard unit costs, the full distance is symmetric and satisfies the triangle inequality. Arbitrary custom penalties require separate analysis. Preprocessing also deserves an explicit specification: changing case, removing punctuation, normalizing Unicode, or comparing bytes instead of characters can change the resulting score before the distance algorithm even begins.

Three practical examples

1. Search suggestions: a catalog can recognize that a query containing two reversed neighboring letters is close to a correctly spelled product word.

2. Data-cleaning review: candidate organization names can be ranked by spelling distance, then checked against addresses or identifiers before any records are merged.

3. Input assistance: a form can offer possible corrections for an unfamiliar location name while preserving the user's original entry and allowing intentional spellings.

Think of it this way

Think of rearranging a row of letter tiles using four priced moves. You may add, remove, replace, or exchange neighboring tiles. The distance is the cheapest bill for reaching the target row.

The analogy captures the edit rules, but the tiles have no understanding of meaning. Two different people's names can require only one move, while two equivalent descriptions may need many moves.

Worked example

Consider the original teaching comparison “flwo” and “flow”. Swapping the adjacent “w” and “o” transforms the first into the second in one operation. Because the strings differ, zero edits cannot work. Their unit-cost Damerau - Levenshtein distance is therefore exactly 1.

Ordinary Levenshtein distance is 2 here: replace the third letter and then the fourth, or delete and reinsert a letter. One ordinary operation cannot suffice. An insertion or deletion changes the length, and one substitution cannot repair both differing positions.

Now compare “flwo” with “flows”. Swap the last two letters to obtain “flow”, then insert “s”: two edits. A single edit is impossible because the only single operation producing the required extra character is insertion, and “flwo” is not a subsequence of “flows”. The distance is exactly 2.

A length-normalized distance defined as d divided by the longer length would be 2/5=0.4 for the second comparison. Its complementary similarity is 0.6 under that convention. Neither number means a 60% probability of a correct match. These results are hand-derived examples, not a reported software benchmark.

Illustrative case study

Fictional case: Willow Parts receives searches for “flwo valve”. Its search team uses adjacent-transposition distance to generate the candidate “flow valve”, then ranks candidates using catalog availability and the rest of the query.

For customer records, the team applies a different policy. A close spelling only creates a review candidate, because merging two accounts is more consequential than suggesting a search term. Reviewers inspect other fields and retain the original text. The case illustrates how one mathematical score can support different decision policies; it does not claim measured commercial results.

Common misconceptions and mistakes

Do not assume every function labeled “Damerau” implements the unrestricted distance. Restricted optimal string alignment can return different results and need not satisfy the triangle inequality.

A transposition exchanges adjacent symbols; it is not a free move of any letter to any position. Also, equal edit distances do not imply equal likelihoods of real typing errors.

Avoid applying one absolute threshold without considering string length and task. One edit in a two-character identifier can be more consequential than one edit in a long description. Preserve meaningful distinctions when choosing normalization rules.

Business use

Business value usually comes from generating plausible candidates cheaply enough for a later decision stage. Evaluate the whole matching workflow against labeled examples, including legitimate near-duplicate names and unusual spellings.

Track unwanted matches as well as missed matches. For large catalogs, candidate generation or indexing may be necessary before detailed pairwise scoring. Record the library, operation costs, preprocessing, and tie-breaking policy so a future implementation change does not silently alter decisions.

Check your understanding

Why is the distance between “flwo” and “flow” one rather than zero or two?

Answer: The strings are not identical, so zero is impossible. A single permitted adjacent transposition produces the target, establishing a minimum of one. Two is the ordinary Levenshtein result when transpositions are unavailable.

Related terms

Levenshtein Distance
Edit distance
Dynamic programming
Record linkage
Semantic similarity
optimal string alignment
approximate string matching
Unicode normalisation

Learn next

Compare ordinary Levenshtein, unrestricted Damerau - Levenshtein, and optimal string alignment on the same short strings. Include repeated letters, an adjacent swap followed by insertion, empty strings, and accented text. Write down the permitted operations and preprocessing before inspecting the software result. Then study precision and recall for evaluating candidate matches.

Sources

Primary sources: RapidFuzz's Damerau–Levenshtein documentation, https://rapidfuzz.github.io/RapidFuzz/Usage/distance/DamerauLevenshtein.html ; Mark P. J. van der Loo, “The stringdist Package for Approximate String Matching”, https://journal.r-project.org/articles/RJ-2014-011/ . Documentation and the paper's edit-distance discussion were read to check the full-versus-restricted distinction. Teaching examples and operational scenarios are original; library execution is not claimed.

Previous: Daitch-Mokotoff Soundex Next: DAMSL