In information theory, linguistics, and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. For two strings, it is the minimum number of single-symbol edits—insertions, deletions, or substitutions—required to transform one string into the other. Each edit has unit cost in the classical definition.V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals”, Doklady Akademii Nauk SSSR, vol. 163, no. 4, 1965, pp. 845–848. English translation in Soviet Physics Doklady, vol. 10, no. 8, 1966, pp. 707–710. Math-Net.
The distance is named after Soviet mathematician Vladimir Levenshtein, who introduced it in 1965 in the context of error-correcting codes. Levenshtein distance is a particular form of edit distance; the latter term is also used for broader models in which the set of allowed operations or their costs differ.Gonzalo Navarro, “A guided tour to approximate string matching”, ACM Computing Surveys, vol. 33, no. 1, 2001, pp. 31–88, doi:10.1145/375360.375365. It is closely related to sequence alignment.
Definition
Let and be two strings. Define as the Levenshtein distance between the prefixes and .
The boundary conditions are
For and ,
where
The three alternatives correspond, respectively, to deleting , inserting , and either matching or substituting the final symbols of the two prefixes.Robert A. Wagner and Michael J. Fischer, “The String-to-String Correction Problem”, Journal of the ACM, vol. 21, no. 1, 1974, pp. 168–173, doi:10.1145/321796.321811.
The Levenshtein distance between the full strings is .
Example
The Levenshtein distance between kitten and sitting is 3. One optimal edit script is:
kitten → sitten (substitute s for k); sitten → sittin (substitute i for e); sittin → sitting (insert g at the end).
A simple deletion example is uninformed → uniformed, which has distance 1.
Properties and bounds
With unit insertion, deletion, and substitution costs, Levenshtein distance is a metric: it is non-negative, is zero if and only if the two strings are equal, is symmetric, and satisfies the triangle inequality.
For strings of lengths and ,
The lower bound follows because a single insertion or deletion changes the string length by only one. The upper bound can be achieved by substituting symbols in the common-length prefix and then inserting or deleting the remainder.
If the two strings have the same length, their Hamming distance is an upper bound on their Levenshtein distance:
For example, flaw and lawn have Hamming distance 4 but Levenshtein distance 2: delete f from the beginning and insert n at the end.
If substitutions are disallowed and only insertions and deletions are permitted, the resulting edit distance between strings of lengths and is
where is the length of a longest common subsequence. This formula does not apply unchanged to classical Levenshtein distance because a substitution has cost 1 rather than the cost 2 of a deletion followed by an insertion.
Applications
Approximate string matching and spelling correction
Levenshtein distance is a basic model in approximate string matching, where strings are allowed to differ by a small number of edits. Applications include spell checkers, correction of optical character recognition output, and approximate lookup in textual databases.
For large collections, systems commonly combine edit-distance computation with filtering, indexing, q-grams, or automata so that the full distance need not be evaluated against every possible candidate.
Record linkage
In record linkage and deduplication, edit distances can be used as features for comparing names, addresses, and other text fields that may contain spelling variation or transcription errors. In practice, candidate-generation or blocking steps are usually used before detailed pairwise comparison.
Linguistics and speech
In quantitative linguistics, Levenshtein distance is often applied to phonetic or phonological transcriptions and then aggregated or normalized across comparable items, rather than treating a single raw word pair as a direct measure of the distance between entire languages. It has been used extensively in dialectometry to quantify pronunciation differences between language varieties.Wilbert J. Heeringa, Measuring Dialect Pronunciation Differences using Levenshtein Distance, PhD thesis, University of Groningen, 2004. University of Groningen.
Weighted versions can assign lower or higher costs to phoneme substitutions according to phonological features, for example in speech-identification studies.Lionel Fontan, Isabelle Ferrané, Jérôme Farinas, Julien Pinquier, and Xavier Aumont, “Using Phonologically Weighted Levenshtein Distances for the Prediction of Microscopic Intelligibility”, Interspeech 2016, pp. 650–654, doi:10.21437/Interspeech.2016-431.
Bioinformatics
Edit distance and sequence alignment are closely related in bioinformatics. Insertions, deletions, and substitutions provide a simple model of differences between biological sequences, although practical sequence-alignment methods generally use richer scoring systems and gap penalties than unit-cost Levenshtein distance.Bonnie Berger, Michael S. Waterman, and Yun William Yu, “Levenshtein Distance, Sequence Comparison and Biological Database Search”, IEEE Transactions on Information Theory, vol. 67, no. 6, 2021, pp. 3287–3294, doi:10.1109/TIT.2020.2996543.
Relationship to other string distances
Levenshtein distance is one member of a broader family of edit-distance models.
The Damerau–Levenshtein distance additionally allows a transposition of two adjacent symbols. The longest-common-subsequence distance allows only insertions and deletions. The Hamming distance allows only substitutions and therefore applies directly only to strings of equal length.
More general edit-distance models may assign different costs to different operations. Such a weighted edit distance is not automatically a metric for arbitrary cost functions; metric properties depend on the conditions imposed on those costs.
Other string-comparison measures, such as Jaro and Jaro–Winkler similarity, use different matching models rather than a minimum-cost script of insertions, deletions, and substitutions.Matthew A. Jaro, “Advances in Record-Linkage Methodology as Applied to Matching the 1985 Census of Tampa, Florida”, Journal of the American Statistical Association, vol. 84, no. 406, 1989, pp. 414–420, doi:10.1080/01621459.1989.10478785.
Sequence-alignment algorithms such as Needleman–Wunsch and Smith–Waterman solve closely related dynamic-programming problems, but typically optimize alignment scores with application-specific substitution scores and gap penalties rather than classical unit edit costs.
Computation
Dynamic programming
The standard dynamic-programming algorithm stores the distances between prefixes of the two input strings. It is commonly associated with Wagner and Fischer's 1974 formulation of the string-to-string correction problem.
function LevenshteinDistance(char s[1..m], char t[1..n]): declare int d[0..m, 0..n]
for i from 0 to m: d[i, 0] := i
for j from 0 to n: d[0, j] := j
for i from 1 to m: for j from 1 to n: if s[i] = t[j]: substitutionCost := 0 else: substitutionCost := 1
d[i, j] := minimum( d[i-1, j] + 1, // deletion of s[i] d[i, j-1] + 1, // insertion of t[j] d[i-1, j-1] + substitutionCost // match or substitution )
return d[m, n]
The invariant is that d[i,j] is the minimum number of edits needed to transform the first i symbols of s into the first j symbols of t.
The full matrix takes time and space.
Memory reduction and edit-script reconstruction
If only the numerical distance is required, each row depends only on the previous row and the current row. By storing the shorter dimension as the row width, the working memory can therefore be reduced to .Esko Ukkonen, “Algorithms for approximate string matching”, Information and Control, vol. 64, nos. 1–3, 1985, pp. 100–118, doi:10.1016/S0019-9958(85)80046-2.
If an optimal edit script is also required, it can be recovered by tracing predecessors through the full matrix. There may be several distinct optimal scripts with the same distance. Divide-and-conquer techniques based on Hirschberg's algorithm can recover an optimal alignment using linear space.Daniel S. Hirschberg, “A linear space algorithm for computing maximal common subsequences”, Communications of the ACM, vol. 18, no. 6, 1975, pp. 341–343, doi:10.1145/360825.360861.
Distance-sensitive and threshold algorithms
When the true edit distance is small compared with the input lengths, an exact algorithm need not evaluate the entire dynamic-programming matrix. Ukkonen developed exact threshold and distance-sensitive algorithms whose running time depends on . One of the algorithms in his 1985 paper runs in time; for the unit-cost case, the distance alone can be obtained with space .
These are exact algorithms: the word “approximate” in approximate string matching refers to allowing differences between strings, not to approximating the numerical edit distance.
Bit-parallel computation
For approximate pattern matching, Gene Myers proposed a bit-vector algorithm in 1999 that packs many dynamic-programming states into machine-word bits, allowing multiple state updates to be performed in parallel with bitwise operations.Gene Myers, “A fast bit-vector algorithm for approximate string matching based on dynamic programming”, Journal of the ACM, vol. 46, no. 3, 1999, pp. 395–415, doi:10.1145/316542.316550.
This should not be confused with Myers's 1986 O(ND) difference algorithm or the O(NP) sequence-comparison algorithm of Wu, Manber, Myers, and Miller. Those algorithms use shortest edit scripts consisting of insertions and deletions; under that model a substitution is equivalent to a deletion followed by an insertion and therefore costs 2, rather than the unit substitution cost of classical Levenshtein distance.Sun Wu, Udi Manber, Gene Myers, and Webb Miller, “An O(NP) sequence comparison algorithm”, Information Processing Letters, vol. 35, no. 6, 1990, pp. 317–323, doi:10.1016/0020-0190(90)90035-V.
Automata
A Levenshtein automaton for a fixed pattern and threshold recognizes exactly the strings whose Levenshtein distance from the pattern is at most .Klaus U. Schulz and Stoyan Mihov, “Fast String Correction with Levenshtein-Automata”, International Journal on Document Analysis and Recognition, vol. 5, no. 1, 2002, pp. 67–85, doi:10.1007/s10032-002-0082-8.
Approximation
For two strings of length , Andoni, Krauthgamer, and Onak gave an algorithm running in time with approximation factor , for every fixed .Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak, “Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity”, 51st IEEE Symposium on Foundations of Computer Science, 2010, pp. 377–386, doi:10.1109/FOCS.2010.43. In 2020, Andoni and Nosatzki obtained a constant-factor approximation in time for every fixed .Alexandr Andoni and Negev Shekel Nosatzki, “Edit Distance in Near-Linear Time: It's a Constant Factor”, IEEE Symposium on Foundations of Computer Science, 2020, pp. 990–1001, doi:10.1109/FOCS46700.2020.00096.
Computational complexity
For equal-length strings of length , Backurs and Indyk showed in 2015 that an exact algorithm running in time for any constant would falsify the strong exponential time hypothesis (SETH). This is a conditional lower bound rather than an unconditional proof that quadratic time is necessary in all computational models.Arturs Backurs and Piotr Indyk, “Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)”, Proceedings of the 47th Annual ACM Symposium on Theory of Computing, 2015, pp. 51–58, doi:10.1145/2746539.2746612.