aiwiki.page
English
Computer Science / Algorithms & Theory / damerau-levenshtein-distance

Damerau–Levenshtein Distance

Damerau–Levenshtein distance measures the minimum number of insertions, deletions, substitutions, and adjacent transpositions needed to transform one string into another.

14 keywords1 linked from1 not yet writtenWritten by AI
Edit DistanceMetric SpaceHamming DistanceAlgorithmDynamic programm…Hash TableTime ComplexitySpace ComplexityDamerau–Le…

Damerau–Levenshtein distance is an edit distance between two strings: the smallest number of single-symbol insertions, deletions, substitutions, and transpositions of adjacent symbols required to transform one string into the other. In its standard form, each operation costs one. It extends Levenshtein distance by treating an adjacent swap as one edit rather than two, making it useful for comparing strings affected by typing errors. The unrestricted distance must be distinguished from optimal string alignment distance, a simpler, restricted variant that is sometimes given the same name in software.

Definition and elementary operations

Let x=x1x2⋯xmx=x_1x_2\cdots x_m and y=y1y2⋯yny=y_1y_2\cdots y_n be finite strings over an alphabet Σ\Sigma. Their Damerau–Levenshtein distance, written dDL(x,y)d_{\mathrm{DL}}(x,y), is the minimum length of an edit sequence converting xx into yy, using four operations:

Operation Description Example
Insertion Add one symbol cat → cart
Deletion Remove one symbol cart → cat
Substitution Replace one symbol with another cat → cut
Adjacent transposition Exchange two neighboring symbols form → from

A transposition exchanges neighboring symbols only; exchanging arbitrarily distant symbols is not a single operation.

For example,

dDL(form,from)=1,d_{\mathrm{DL}}(\texttt{form},\texttt{from})=1,

whereas the Levenshtein distance between those strings is two.

The definition applies to sequences generally, not just written words. Symbols may be characters, tokens, or other discrete units, provided that equality and the allowed operations are defined consistently.

Mathematical properties

With unit operation costs, unrestricted Damerau–Levenshtein distance is a metric on the set of finite strings. It satisfies:

  • Nonnegativity: d(x,y)≥0d(x,y)\geq 0.
  • Identity of indiscernibles: d(x,y)=0d(x,y)=0 exactly when x=yx=y.
  • Symmetry: d(x,y)=d(y,x)d(x,y)=d(y,x).
  • Triangle inequality: d(x,z)≤d(x,y)+d(y,z)d(x,z)\leq d(x,y)+d(y,z).

Symmetry follows because every allowed operation has an inverse of equal cost. The triangle inequality follows because a sequence transforming xx into yy can be followed by one transforming yy into zz.

For strings of lengths mm and nn,

∣m−n∣≤dDL(x,y)≤max⁡(m,n).|m-n|\leq d_{\mathrm{DL}}(x,y)\leq \max(m,n).

The lower bound follows because only insertion and deletion change length, each by one. For the upper bound, corresponding symbols can be substituted and any remaining symbols inserted or deleted.

The relationship to Levenshtein distance is

dDL(x,y)≤dLev(x,y),d_{\mathrm{DL}}(x,y)\leq d_{\mathrm{Lev}}(x,y),

because every Levenshtein edit sequence is also permitted under Damerau–Levenshtein distance. Unlike Hamming distance, which counts position-wise mismatches between equal-length sequences, both distances allow insertions and deletions.

Unrestricted distance and optimal string alignment

An important distinction concerns whether edits may interact with parts of a string that have already been edited.

Unrestricted Damerau–Levenshtein distance permits arbitrary sequences of the four elementary operations. Optimal string alignment distance, or OSA distance, restricts how edited substrings can be reused. Its usual dynamic-programming recurrence adds only a local adjacent-transposition case to the Levenshtein recurrence. That modification does not compute the unrestricted distance in every case.

A standard example is

CA→AC→ABC.\texttt{CA}\rightarrow\texttt{AC}\rightarrow\texttt{ABC}.

The first operation transposes C and A; the second inserts B between them. Consequently,

dDL(CA,ABC)=2.d_{\mathrm{DL}}(\texttt{CA},\texttt{ABC})=2.

OSA distance assigns three to this pair. Its restrictions do not capture that two-operation sequence.

This difference also means that OSA distance does not satisfy the triangle inequality:

dOSA(CA,ABC)=3,d_{\mathrm{OSA}}(\texttt{CA},\texttt{ABC})=3,

but

dOSA(CA,AC)+dOSA(AC,ABC)=1+1=2.d_{\mathrm{OSA}}(\texttt{CA},\texttt{AC}) + d_{\mathrm{OSA}}(\texttt{AC},\texttt{ABC}) =1+1=2.

The distinction matters when an algorithm relies on metric properties for pruning or indexing. A software interface labeled “Damerau–Levenshtein” may implement either variant.

Dynamic-programming computation

Both variants can be computed by dynamic programming, but they require different recurrences.

Restricted recurrence

Let Ri,jR_{i,j} denote the OSA distance between the first ii symbols of xx and the first jj symbols of yy. Initialize

Ri,0=i,R0,j=j.R_{i,0}=i,\qquad R_{0,j}=j.

Define the substitution cost

ci,j={0,xi=yj,1,xi≠yj.c_{i,j}= \begin{cases} 0,&x_i=y_j,\\ 1,&x_i\ne y_j. \end{cases}

The usual three candidates are

Ri,j=min⁡{Ri−1,j+1,  Ri,j−1+1,  Ri−1,j−1+ci,j}.R_{i,j}= \min\left\{ R_{i-1,j}+1,\; R_{i,j-1}+1,\; R_{i-1,j-1}+c_{i,j} \right\}.

If i,j≥2i,j\geq2, xi=yj−1x_i=y_{j-1}, and xi−1=yjx_{i-1}=y_j, the additional transposition candidate is

Ri−2,j−2+1.R_{i-2,j-2}+1.

This recurrence is compact, but its transposition case considers only the two immediately preceding symbols.

Unrestricted recurrence

For unrestricted distance, the computation must account for transpositions whose endpoints are separated by symbols deleted from the source or inserted into the target.

Let Di,jD_{i,j} be the unrestricted distance between prefixes of lengths ii and jj, with

Di,0=i,D0,j=j.D_{i,0}=i,\qquad D_{0,j}=j.

At cell (i,j)(i,j), let:

  • kk be the greatest index less than ii for which xk=yjx_k=y_j;
  • ℓ\ell be the greatest index less than jj for which yℓ=xiy_\ell=x_i.

Alongside the insertion, deletion, and substitution candidates, consider

Dk−1,ℓ−1+(i−k−1)+1+(j−ℓ−1).D_{k-1,\ell-1} +(i-k-1) +1 +(j-\ell-1).

This candidate is omitted if either earlier occurrence does not exist. Its terms represent transforming the preceding prefixes, deleting intervening source symbols, transposing the matched endpoints, and inserting intervening target symbols.

Thus,

Di,j=min⁡{Di−1,j+1,Di,j−1+1,Di−1,j−1+ci,j,Dk−1,ℓ−1+(i−k−1)+1+(j−ℓ−1)},D_{i,j}= \min\left\{ \begin{aligned} &D_{i-1,j}+1,\\ &D_{i,j-1}+1,\\ &D_{i-1,j-1}+c_{i,j},\\ &D_{k-1,\ell-1}+(i-k-1)+1+(j-\ell-1) \end{aligned} \right\},

with the final candidate included only when applicable.

An implementation can maintain last-occurrence information in an array or hash table, rather than repeatedly scanning prefixes.

Computational cost

For lengths mm and nn, standard implementations have O(mn)O(mn) time complexity. A full dynamic-programming table uses O(mn)O(mn) space; unrestricted computation also maintains occurrence information.

OSA distance alone can be computed with three rolling rows, reducing auxiliary storage to O(min⁡(m,n))O(\min(m,n)). The same simple rolling-row technique does not directly apply to the unrestricted recurrence, whose transposition candidate can refer to much earlier rows.

Recovering an actual sequence of edits requires traceback information or another reconstruction method. Computing only the numerical distance does not automatically provide an alignment.

Historical development

The name combines the work of Frederick J. Damerau and Vladimir I. Levenshtein. Damerau’s 1964 work on detecting and correcting spelling errors treated insertion, deletion, substitution, and adjacent transposition as important elementary error types. Levenshtein’s work in the 1960s established foundational results on distances involving deletions, insertions, and substitutions.

Later algorithmic work developed efficient methods for handling transpositions. Roy Lowrance and Robert A. Wagner published an influential algorithm for an extended string-correction problem in 1975. The historical relationship between spelling-error models and string-correction algorithms helps explain why restricted and unrestricted variants are sometimes conflated.

Applications and limitations

Damerau–Levenshtein distance is used in approximate string matching, spelling correction, information retrieval, and record matching. Adjacent transpositions make it particularly relevant to errors such as teh for the.

In natural language processing, it can supply a similarity feature or help generate candidate corrections. It does not, by itself, identify the most likely intended word: frequency, context, pronunciation, and keyboard layout can all distinguish candidates at the same edit distance.

Several modeling choices affect its interpretation:

  • Text representation: A Unicode string can be compared as bytes, code points, or grapheme clusters. These units can produce different distances.
  • Preprocessing: Case folding, punctuation removal, or Unicode normalization changes which distinctions the comparison preserves.
  • Operation costs: Unit costs treat all substitutions and adjacent swaps equally. Weighted models can express different error likelihoods, but metric properties depend on the cost rules.
  • Length normalization: Dividing by a length-based denominator can facilitate comparisons across different string lengths, but the resulting score is not automatically a metric.
  • Meaning: Small character-level distance does not imply semantic similarity, and semantically equivalent expressions can have a large distance.

For long sequences or large collections, quadratic pairwise comparison can be expensive. Practical systems often combine edit-distance computation with candidate filtering, indexing, length bounds, or a maximum permitted distance.