Levenshtein distance
The Levenshtein distance (also editing distance ) between two character strings is the minimum number of insert, delete and replace operations to convert the first character string into the second. The distance is named after the Russian scientist Vladimir Lewenstein (Levenshtein), who introduced it in 1965. Mathematically, the Levenshtein distance is a metric in the space of symbol sequences .
For example, the Levenshtein distance between "Tier" and "Tor" is 2. A possible consequence of two operations is:
 animal
 Toer (replace i with o)
 Goal (delete e)
In practice, the Levenshtein distance is used to determine the similarity of character strings, for example to check spelling or to detect duplicates .
algorithm
The Levenshtein article of 1965 defines the Levenshtein distance, but no algorithm is given for calculating the distance. In the literature, an algorithm for calculating the Levenshtein distance using the dynamic programming method is called the Levenshtein algorithm.
The algorithm is the following matrix  recurrences specified, where and denote the two input strings:

,
After the matrix is calculated, the Levenshtein distance, i.e. H. the minimum number of edit operations in the matrix cell . In each cell there is the Levenshtein distance of the prefixes and . In the event of a further deletion or insertion, only one more character from or is used. Ie the result is saved in or . Thus, the costs for a deletion or insertion in the cell can be recurrently calculated or calculated. The case of replacement can be explained in the same way.
If not only the Levenshtein distance is to be calculated, but also the sequence of operations that led to the result, a "backtrace" must be carried out on the calculated matrix. That is, starting with , the optimization decisions are traced back recursively. In the pseudocode the backtrace algorithm is:
string backtrace(i, j):
if i>0 && D[i1,j] + 1 == D[i,j]
return backtrace(i1, j) + " Löschung "
if j>0 && D[i,j1] + 1 == D[i,j]
return backtrace(i, j1) + " Einfügung "
if i>0 && j>0 && D[i1, j1] + 1 == D[i,j]
return backtrace(i1, j1) + " Ersetzung "
if i>0 && j>0 && D[i1, j1] == D[i,j]
return backtrace(i1, j1) + " Gleichheit "
return ""
To simplify the pseudocode, only one possible backtrace is calculated.
example
The procedure can now easily be carried out in a table. Here is an example with the two strings “animal” and “gate”.
ε T o r
ε 0 1 2 3
T 1 0 1 2
i 2 1 1 2
e 3 2 2 2
r 4 3 3 2
The distance between the two strings is 2. ε stands for the empty string "".
complexity
The running time of the algorithm is in O , since all cells of the matrix are calculated and the computational effort per cell is constant.
The memory requirement is in because the matrix has rows and columns. If, however, no backtracing is carried out, then only the last row or column is required to calculate the next row or column for the row or column calculation of the matrix. The memory requirement in this case is in .
The Hirschberg algorithm enables the calculation of the Levenshtein distance and a "backtrace" in quadratic time and with linear memory consumption.
Barriers
There are some upper and lower bounds for the Levenshtein distance :
 it is at least the difference between the lengths of the two strings
 it is at most the length of the longer character string
 it is 0 if and only if both strings are identical (definition of metric)
 it is not greater than the Hamming distance plus the difference in length between the character strings
Demarcation
The Levenshtein distance can be viewed as an extension of the Hamming distance , which is limited to replacements and can therefore only measure strings of the same length. A phonetic search can use the Levenshtein distance to allow errors. Words to be compared can be converted into a sound symbol string before a distance calculation, for example using the Cologne phonetics or the Soundex algorithm.
The DP algorithm for calculating the Levenshtein distance is related to the NeedlemanWunsch algorithm for calculating the sequence alignment of two character strings. The Needleman Wunsch algorithm is in and allows any cost functions for inserting and deleting operations of length . In the Levenshtein algorithm, an insert or delete operation consists of a maximum of one character. Variants of the NeedlemanWunsch algorithm limit the choice of the cost function so that its running time is in .
The SmithWaterman algorithm optimizes the costs of the edit operations according to the same DP scheme as the Needleman Wunsch or Levenshtein algorithm, but insert and delete operations are included at the beginning and end of a sequence evaluated and ignored in the backtrace. In other words, the SmithWaterman algorithm calculates the local "sequence alignment". Its duration is in .
The Levenshtein distance can be viewed as a special form of the dynamic time warping distance (DTW).
variants
Weighted Levenshtein distance
The costs of the individual insert, delete and replace operations can also be weighted differently or even depending on the characters involved. The method generalized in this way is referred to as the weighted Levenshtein distance, weighted Levenshtein distance or the WLD algorithm for short.
An example of weighted costs for distance operations that can be minimized with the WLD algorithm is the cost of typewriter distance .
DamerauLevenshtein distance
DamerauLevenshtein extends the functionality of Levenshtein by the ability to identify two exchanged characters, for example "Raisch" ↔ "Rasich". In order to convert one character string into the other, two operations would be necessary with Levenshtein. DamerauLevenshtein only needs one.
The following matrix recurrences specify the algorithm variant.
 ,
 ,
Where denotes the cost of swapping two characters.
See also
literature
 Fred J. Damerau: A technique for computer detection and correction of spelling errors . In: Communications of the ACM . tape 7 , no. 3 , March 1964, p. 171176 .
 Vladimir I. Levenshtein: Binary codes capable of correcting deletions, insertions, and reversals . In: Doklady Akademii Nauk SSSR . tape 163 , no. 4 , 1965, pp. 845848 (Russian, English translation in: Soviet Physics Doklady, 10 (8) pp. 707710, 1966).