In computational linguistics and computer science, edit distance is a string metric, i.e. a way of quantifying how dissimilar two strings (e.g., words) are to one another, that is measured by counting the minimum number of operations required to transform one string into the other. Edit distances find applications in natural language processing, where automatic spelling correction can determine candidate corrections for a misspelled word by selecting words from a dictionary that have a low distance to the word in question. In bioinformatics, it can be used to quantify the similarity of DNA sequences, which can be viewed as strings of the letters A, C, G and T.
Different definitions of an edit distance use different sets of like operations. Levenshtein distance operations are the removal, insertion, or substitution of a character in the string. Being the most common metric, the term Levenshtein distance is often used interchangeably with edit distance.[1]
Different types of edit distance allow different sets of string operations. For instance:
| Insertions | Deletions | Substitutions | Transposition | ||
|---|---|---|---|---|---|
| ✓ | ✓ | ✓ | |||
| Longest Common Subsequence (LCS) | ✓ | ✓ | |||
| Hamming Distance | ✓ | ||||
| Damerau–Levenshtein Distance | ✓ | ✓ | ✓ | ✓ | |
| ✓ |
Given two strings and on an alphabet (e.g. the set of ASCII characters, the set of bytes [0..255], etc.), the edit distance is the minimum-weight series of edit operations that transforms into . One of the simplest sets of edit operations is that defined by Levenshtein in 1966:
Insertion of a single symbol. If =, then inserting the symbol produces . This can also be denoted ε→, using ε to denote the empty string.
Deletion of a single symbol changes to (→ε).
Substitution of a single symbol for a symbol ≠ changes to (→).
In Levenshtein's original definition, each of these operations has unit cost (except that substitution of a character by itself has zero cost), so the Levenshtein distance is equal to the minimum number of operations required to transform to . A more general definition associates non-negative weight functions ins, del and sub( ) with the operations.[2]
Additional primitive operations have been suggested. Damerau–Levenshtein distance counts as a single edit a common mistake: transposition of two adjacent characters, formally characterized by an operation that changes into .[3] For the task of correcting OCR output, merge and split operations have been used which replace a single character into a pair of them or vice versa.[4]
Other variants of edit distance are obtained by restricting the set of operations. Longest common subsequence (LCS) distance is edit distance with insertion and deletion as the only two edit operations, both at unit cost. Similarly, by only allowing substitutions (again at unit cost), Hamming distance is obtained; this must be restricted to equal-length strings.Jaro–Winkler distance can be obtained from an edit distance where only transpositions are allowed.
The Levenshtein distance between "kitten" and "sitting" is 3. A minimal edit script that transforms the former into the latter is:
LCS distance (insertions and deletions only) gives a different distance and minimal edit script:
for a total cost/distance of 5 operations.
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:
With these properties, the metric axioms are satisfied as follows:
= 0 if and only if a=b, since each string can be trivially transformed to itself using exactly zero operations.
> 0 when ≠, since this would require at least one operation at non-zero cost.
= by equality of the cost of each operation and its inverse.
Triangle inequality: ≤ + .[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.
Other useful properties of unit-cost edit distances include:
Regardless of cost/weights, the following property holds of all edit distances:
The first algorithm for computing minimum edit distance between a pair of strings was published by Damerau in 1964.[6]
See main article: Wagner–Fischer algorithm. Using Levenshtein's original operations, the (nonsymmetric) edit distance from
a=a1\ldotsam
b=b1\ldotsbn
dmn
\begin{align}di0&=
| i | |
| \sum | |
| k=1 |
wdel(ak),&& for 1\leqi\leqm\\ d0j&=
| j | |
| \sum | |
| k=1 |
wins(bk),&& for 1\leqj\leqn\\ dij&=\begin{cases}di-1,&for ai=bj\ min\begin{cases}di-1,+wdel(ai)\ di,j-1+wins(bj)\ di-1,j-1+wsub(ai,bj)\end{cases}&for ai ≠ bj\end{cases}&& for 1\leqi\leqm,1\leqj\leqn.\end{align}
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
dmn
This algorithm has a time complexity of Θ where and are the lengths of the strings. When the full dynamic programming table is constructed, its space complexity is also ; this can be improved to 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] 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]
Improving on the Wagner–Fisher algorithm described above, Ukkonen describes several variants,[10] one of which takes two strings and a maximum edit distance, and returns . It achieves this by only computing and storing a part of the dynamic programming table around its diagonal. This algorithm takes time, where and are the lengths of the strings. Space complexity is or, depending on whether the edit sequence needs to be read off.[3]
Further improvements by Landau, Myers, and Schmidt https://dblp.org/pers/hd/s/Schmidt:Jeanette_P= give an 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).
Edit distance finds applications in computational biology and natural language processing, e.g. the correction of spelling mistakes or OCR errors, and approximate string matching, where the objective is to find matches for short strings in many longer texts, in situations where a small number of differences is to be expected.
Various algorithms exist that solve problems beside the computation of distance between a pair of strings, to solve related types of problems.
A generalization of the edit distance between strings is the language edit distance between a string and a language, usually a formal language. Instead of considering the edit distance between one string and another, the language edit distance is the minimum edit distance that can be attained between a fixed string and any string taken from a set of strings. More formally, for any language L and string x over an alphabet, the language edit distance d(L, x) is given by[14]
d(L,x)=minyd(x,y)
d(x,y)
Language edit distance has found many diverse applications, such as RNA folding, error correction, and solutions to the Optimum Stack Generation problem.[17]