Levenshtein distance

Summarize Timeline Top Qs Fact Check

Let ${\displaystyle a=a_{1}a_{2}\dots a_{m}}$ and ${\displaystyle b=b_{1}b_{2}\dots b_{n}}$ be two strings. Define ${\displaystyle D(i,j)}$ as the Levenshtein distance between the prefixes ${\displaystyle a_{1}\dots a_{i}}$ and ${\displaystyle b_{1}\dots b_{j}}$.

The boundary conditions are

${\displaystyle D(i,0)=i,\qquad D(0,j)=j.}$

For ${\displaystyle i>0}$ and ${\displaystyle j>0}$,

${\displaystyle 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

${\displaystyle \delta (a_{i},b_{j})={\begin{cases}0,&a_{i}=b_{j},\\1,&a_{i}\neq b_{j}.\end{cases}}}$

The three alternatives correspond, respectively, to deleting ${\displaystyle a_{i}}$, inserting ${\displaystyle b_{j}}$, and either matching or substituting the final symbols of the two prefixes.^[3]

The Levenshtein distance between the full strings is ${\displaystyle D(m,n)}$.

Example

The Levenshtein distance between kitten and sitting is 3. One optimal edit script is:

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

A simple deletion example is uninformed → uniformed, which has distance 1.

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.^[2]

For strings of lengths ${\displaystyle m}$ and ${\displaystyle n}$,

${\displaystyle |m-n|\leq \operatorname {lev} (a,b)\leq \max(m,n).}$

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:

${\displaystyle \operatorname {lev} (a,b)\leq d_{H}(a,b).}$

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 ${\displaystyle m}$ and ${\displaystyle n}$ is

${\displaystyle m+n-2L,}$

where ${\displaystyle L}$ 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.^[3]

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.^[2]

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.^[2]

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.^[4]

Weighted versions can assign lower or higher costs to phoneme substitutions according to phonological features, for example in speech-identification studies.^[5]

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.^[6]

Levenshtein distance is one member of a broader family of edit-distance models.^[2]

• 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.^[2]

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.^[7]

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.^[6]

Summarize Timeline Top Qs Fact Check

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.^[3]

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 ${\displaystyle \Theta (mn)}$ time and ${\displaystyle \Theta (mn)}$ space.^[3]

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 ${\displaystyle O(\min(m,n))}$.^[8]

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.^[9]

Distance-sensitive and threshold algorithms

When the true edit distance ${\displaystyle s}$ 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 ${\displaystyle s}$. One of the algorithms in his 1985 paper runs in ${\displaystyle O(s\min(m,n))}$ time; for the unit-cost case, the distance alone can be obtained with space ${\displaystyle O(\min(s,m,n))}$.^[8]

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.^[10]

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.^[11]

Automata

A Levenshtein automaton for a fixed pattern and threshold ${\displaystyle k}$ recognizes exactly the strings whose Levenshtein distance from the pattern is at most ${\displaystyle k}$.^[12]

Approximation

For two strings of length ${\displaystyle n}$, Andoni, Krauthgamer, and Onak gave an algorithm running in ${\displaystyle n^{1+\varepsilon }}$ time with approximation factor ${\displaystyle (\log n)^{O(1/\varepsilon )}}$, for every fixed ${\displaystyle \varepsilon >0}$.^[13] In 2020, Andoni and Nosatzki obtained a constant-factor approximation in ${\displaystyle n^{1+\varepsilon }}$ time for every fixed ${\displaystyle \varepsilon >0}$.^[14]

Computational complexity

For equal-length strings of length ${\displaystyle n}$, Backurs and Indyk showed in 2015 that an exact algorithm running in ${\displaystyle O(n^{2-\varepsilon })}$ time for any constant ${\displaystyle \varepsilon >0}$ 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.^[15]

An older unconditional lower bound of ${\displaystyle \Omega (mn)}$ applies in a comparison model in which the only queries allowed on input symbols are equality comparisons.^[16]

The mathematical definition of Levenshtein distance is over sequences of symbols; it does not itself specify what a “character” in software must be. For Unicode text, an implementation may operate on encoded bytes, code units, Unicode code points, or user-perceived characters represented by extended grapheme clusters. Different choices can produce different distance values.

Unicode Standard Annex #29 defines extended grapheme clusters as an algorithmic approximation to user-perceived characters.^[17]

In addition, canonically equivalent Unicode text can be represented by different sequences of code points. Unicode Standard Annex #15 defines normalization forms such as NFC and NFD for canonical equivalence.^[18] Consequently, implementations that compare Unicode text should specify both the sequence unit being compared and any normalization performed before the distance is calculated.

Levenshtein's 1965 paper introduced the edit metric in coding theory but did not present the matrix algorithm now commonly used to compute it.^[1] Dynamic-programming methods for sequence comparison were developed independently in several areas in the late 1960s and 1970s; Wagner and Fischer's 1974 string-to-string correction formulation became a standard presentation of the quadratic dynamic program.^[3][6]

Later work developed linear-space reconstruction, distance-sensitive algorithms, bit-parallel methods, Levenshtein automata, approximation algorithms, and conditional lower bounds on exact computation.^[8][10][15]

• agrep
• Approximate string matching
• diff
• Dynamic time warping
• Hamming distance
• Jaro–Winkler distance
• Needleman–Wunsch algorithm
• Smith–Waterman algorithm
• String metric