Edit distance

Example

The Levenshtein distance between "kitten" and "sitting" is 3. A minimal edit script that transforms the former into the latter is:

1. kitten → sitten (substitute "s" for "k")
2. sitten → sittin (substitute "i" for "e")
3. sittin → sitting (insert "g" at the end)

LCS distance (insertions and deletions only) gives a different distance and minimal edit script:

1. kitten → itten (delete "k" at 0)
2. itten → sitten (insert "s" at 0)
3. sitten → sittn (delete "e" at 4)
4. sittn → sittin (insert "i" at 4)
5. sittin → sitting (insert "g" at 6)

for a total cost/distance of 5 operations.

Properties

Edit distance with non-negative cost satisfies the axioms of a metric, giving rise to a metric space of strings, when the following conditions are met:^[1]: 37

• Every edit operation has positive cost;
• for every operation, there is an inverse operation with equal cost.

With these properties, the metric axioms are satisfied as follows:

d(a, b) = 0 if and only if a=b, since each string can be trivially transformed to itself using exactly zero operations.

d(a, b) > 0 when a ≠ b, since this would require at least one operation at non-zero cost.

d(a, b) = d(b, a) by equality of the cost of each operation and its inverse.

Triangle inequality: d(a, c) ≤ d(a, b) + d(b, c).^[5]

Levenshtein distance and LCS distance with unit cost satisfy the above conditions, and therefore the metric axioms. Variants of edit distance that are not proper metrics have also been considered in the literature.^[1]

Other useful properties of unit-cost edit distances include:

• LCS distance is bounded above by the sum of lengths of a pair of strings.^[1]: 37
• LCS distance is an upper bound on Levenshtein distance.
• For strings of the same length, Hamming distance is an upper bound on Levenshtein distance.^[1]

Regardless of cost/weights, the following property holds of all edit distances:

• When a and b share a common prefix, this prefix has no effect on the distance. Formally, when a = uv and b = uw, then d(a, b) = d(v, w).^[4] This allows speeding up many computations involving edit distance and edit scripts, since common prefixes and suffixes can be skipped in linear time.

Common algorithm

Using Levenshtein's original operations, the (nonsymmetric) edit distance from ${\displaystyle a=a_{1}\ldots a_{m}}$ to ${\displaystyle b=b_{1}\ldots b_{n}}$ is given by ${\displaystyle d_{mn}}$, defined by the recurrence^[2]

${\displaystyle {\begin{aligned}d_{i0}&=\sum _{k=1}^{i}w_{\mathrm {del} }(a_{k}),&&\quad {\text{for}}\;1\leq i\leq m\\d_{0j}&=\sum _{k=1}^{j}w_{\mathrm {ins} }(b_{k}),&&\quad {\text{for}}\;1\leq j\leq n\\d_{ij}&={\begin{cases}d_{i-1,j-1}&{\text{for}}\;a_{i}=b_{j}\\\min {\begin{cases}d_{i-1,j}+w_{\mathrm {del} }(a_{i})\\d_{i,j-1}+w_{\mathrm {ins} }(b_{j})\\d_{i-1,j-1}+w_{\mathrm {sub} }(a_{i},b_{j})\end{cases}}&{\text{for}}\;a_{i}\neq b_{j}\end{cases}}&&\quad {\text{for}}\;1\leq i\leq m,1\leq j\leq n.\end{aligned}}}$

This algorithm can be generalized to handle transpositions by adding another term in the recursive clause's minimization.^[3]

The straightforward, recursive way of evaluating this recurrence takes exponential time. Therefore, it is usually computed using a dynamic programming algorithm that is commonly credited to Wagner and Fischer,^[7] although it has a history of multiple invention.^[2][3] After completion of the Wagner–Fischer algorithm, a minimal sequence of edit operations can be read off as a backtrace of the operations used during the dynamic programming algorithm starting at ${\displaystyle d_{mn}}$.

This algorithm has a time complexity of Θ(mn) where m and n are the lengths of the strings. When the full dynamic programming table is constructed, its space complexity is also Θ(mn); this can be improved to Θ(min(m,n)) by observing that at any instant, the algorithm only requires two rows (or two columns) in memory. However, this optimization makes it impossible to read off the minimal series of edit operations.^[3] A linear-space solution to this problem is offered by Hirschberg's algorithm.^[8]: 634 A general recursive divide-and-conquer framework for solving such recurrences and extracting an optimal sequence of operations cache-efficiently in space linear in the size of the input is given by Chowdhury, Le, and Ramachandran.^[9]

Improved algorithms

Improving on the Wagner–Fisher algorithm described above, Ukkonen describes several variants,^[10] one of which takes two strings and a maximum edit distance s, and returns min(s, d). It achieves this by only computing and storing a part of the dynamic programming table around its diagonal. This algorithm takes time O(s×min(m,n)), where m and n are the lengths of the strings. Space complexity is O(s²) or O(s), depending on whether the edit sequence needs to be read off.^[3]

Further improvements by Landau, Myers, and Schmidt give an O(s² + max(m,n)) time algorithm.^[11]

For a finite alphabet and edit costs which are multiples of each other, the fastest known exact algorithm is of Masek and Paterson^[12] having worst case runtime of O(nm/logn).