Damerau–Levenshtein distance calculator

Damerau–Levenshtein distance is a classic edit metric that counts how many single-character operations turn one string into another when the allowed operations are insertion, deletion, substitution, and transposition of two adjacent characters. That last operation is what separates it from plain Levenshtein distance and makes it especially useful for real-world typos: people often swap two neighbouring keys (form versus from, teh versus the) and those should cost one step, not two substitutions. This capability implements the Optimal String Alignment form of the distance with a pure dynamic-programming table, so every pair of inputs yields the same integer on every runtime.

What Damerau–Levenshtein measures and how it differs from plain Levenshtein

Edit distance asks how many unit changes are needed to rewrite a source string as a target string. Classical Levenshtein allows three unit operations: insert one character, delete one character, or substitute one character for another. Each costs one.

Damerau’s extension adds a fourth operation: swap two adjacent characters for a single unit cost. That extension matches how people actually mistype words on a keyboard. For example, the strings ab and ba differ by one adjacent transposition under Damerau–Levenshtein and by two substitutions under plain Levenshtein.

Kitten versus sitting still costs three (as in the textbook Levenshtein example) because the cheapest path uses substitutions and an insertion rather than a single swap. OSA is the form most libraries label Damerau–Levenshtein for typo correction; it forbids applying two overlapping transpositions on the same substring, which keeps the metric simple and O(n·m) in time and space. Empty strings are valid: the distance from the empty string to any string is that string’s length, and the distance between two empty strings is zero.

Identical strings always yield distance zero and similarity one, including after optional case folding.

Where this distance proves useful

Product search and inventory tools use edit distance with transpositions to rank near-miss SKUs and brand names before falling back to slower semantic models. CRM and deduplication pipelines flag candidate duplicate rows when distance is at most one or two and similarity is above a fixed threshold, catching swapped letters that plain equality or even plain Levenshtein would under-score. Spell-check demos and classroom exercises need a deterministic oracle that marks form versus from as distance one and charges a transparent fixed fee rather than token cost.

Invalid input does not consume balance. Pair the integer distance with your own threshold policy—accept distance zero only for exact keys, distance one for aggressive typo fix, similarity above zero point eight for soft merge hints—and you get a small, auditable building block for fuzzy matching without standing up a full search engine or NLP stack of your own.