Levenshtein distance

In information theory, linguistics, and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences.

Uses your system voice; voice and rate in settings.

≈ 3 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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. It is closely related to sequence alignment.

Let a=a_1a_2\dots a_m and b=b_1b_2\dots b_n be two strings. Define D(i,j) as the Levenshtein distance between the prefixes a_1\dots a_i and b_1\dots b_j .

The boundary conditions are D(i,0)=i,\qquad D(0,j)=j. For i>0 and j>0 , D(i,j)=\min \begin{cases} D(i-1,j)+1,\\ D(i,j-1)+1,\\ D(i-1,j-1)+\delta(a_i,b_j), \end{cases} where \delta(a_i,b_j)= \begin{cases} 0,& a_i=b_j,\\ 1,& a_i\ne b_j. \end{cases} The three alternatives correspond, respectively, to deleting a_i , inserting b_j , and either matching or substituting the final symbols of the two prefixes. The Levenshtein distance between the full strings is D(m,n) . 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 \Theta(mn) time and \Theta(mn) space.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375547008 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001375547008 · captured 2026-09-18 · ledger · version history

Cite this page as: encyclopegia.org, “Levenshtein distance”, snapshot enwiki-001375547008. https://encyclopegia.org/a/levenshtein-distance

Sources cited in this revision

18 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.