Levenshtein Distance

Levenshtein distance, often referred to simply as edit distance, is a string metric in computation and algorithms, coding theory, and computational linguistics introduced by Soviet mathematician Vladimir I. Levenshtein in 1965. Given two finite strings A = a₁a₂⋯a_m and B = b₁b₂⋯b_n over an alphabet Σ, the Levenshtein distance d_L(A, B) is defined as the minimum number of elementary single-character edit operations—insertions, deletions, and substitutions—needed to transform A into B.

Unlike Hamming distance, which is defined only for strings of equal length (m = n) and counts only character mismatches, Levenshtein distance compares sequences of arbitrary lengths by accommodating gaps via insertions and deletions ("indels"). This makes it a foundational building block for biological sequence alignment, approximate dictionary search alongside the Aho–Corasick algorithm and the Knuth–Morris–Pratt algorithm, optical character recognition error correction, and DNA sequencing read mapping.

For any strings A, B, C ∈ Σ, Levenshtein distance satisfies all four axioms of a true mathematical metric on Σ:

1. Non-negativity and identity of indiscernibles: d_L(A, B) ≥ 0, with d_L(A, B) = 0 if and only if A = B.
2. Symmetry: d_L(A, B) = d_L(B, A), because every insertion in transforming A → B corresponds to a deletion in transforming B → A, and every substitution is reversible.
3. Triangle inequality: d_L(A, C) ≤ d_L(A, B) + d_L(B, C).
4. Length bounds: |m − n| ≤ d_L(A, B) ≤ max(m, n).

The Wagner–Fischer Dynamic Programming Algorithm

Published independently across speech recognition, bioinformatics, and computer science between 1968 and 1974 (and formalized by Robert A. Wagner and Michael J. Fischer in 1974), the standard algorithm computes d_L(A, B) via bottom-up dynamic programming over an (m + 1) × (n + 1) matrix D. Here, D_i,j stores the edit distance between the length-i prefix A_1..i and the length-j prefix B_1..j.

The boundary conditions initialize the first column and first row as pure deletions and pure insertions:

D_i,0 = i (for 0 ≤ i ≤ m), D_0,j = j (for 0 ≤ j ≤ n).

For 1 ≤ i ≤ m and 1 ≤ j ≤ n, each interior cell satisfies the Bellman optimality recurrence:

D_i,j = min { D_i−1,j + 1 (deletion), D_i,j−1 + 1 (insertion), D_i−1,j−1 + δ(a_i, b_j) (match or substitution) },

where the indicator cost is δ(a_i, b_j) = 0 if a_i = b_j and 1 if a_i ≠ b_j. Evaluating all (m + 1)(n + 1) cells requires O(mn) time. When only the scalar distance D_m,n is needed, storing just the previous and current rows reduces memory from O(mn) to O(min(m, n)); when the full optimal edit transcript is also needed in linear space, Hirschberg's divide-and-conquer algorithm (1975) recovers the alignment path in O(mn) time and O(min(m, n)) space.

Different error models assign distinct weights or operations to the edit recurrence:

Ukkonen's Banded K-Diagonal Algorithm and Myers' Bit-Parallelism

In high-throughput bioinformatics and database search, one rarely needs the exact edit distance when two strings differ by more than a small threshold k. Because each diagonal offset |i − j| in the dynamic programming table requires at least |i − j| insertions or deletions, Ukkonen's banded algorithm (1985) restricts computation to a band of width 2k + 1 around the main diagonal, reducing runtime from O(mn) to O(k · min(m, n)).

Furthermore, adjacent cells in the Levenshtein matrix differ by at most ±1: D_i,j − D_i−1,j ∈ {−1, 0, +1} and D_i,j − D_i,j−1 ∈ {−1, 0, +1}. Exploiting this property, Gene Myers' bit-parallel algorithm (1999) encodes vertical and horizontal difference vectors as Boolean bitmasks inside 64-bit CPU registers (or 256/512-bit SIMD vectors), updating w = 64 cells in a small constant number of bitwise logic operations and achieving O(⌈m/w⌉ n) runtime. On the theoretical front, Andoni, Krauthgamer, and Onak (2010) and Backurs and Indyk (2015) proved that under the Strong Exponential Time Hypothesis (SETH)—which posits that boolean satisfiability requires O(exp(cn)) time—no worst-case O(n^2−ε) algorithm exists for computing Levenshtein distance on arbitrary strings.

In genomics, next-generation sequencing aligners use Myers' bit-parallel Levenshtein automaton and banded dynamic programming to verify candidate seed hits identified by suffix arrays or FM-indexes, distinguishing true single-nucleotide polymorphisms (SNPs) and short indels from sequencing errors. In computational linguistics and speech recognition, word-level Levenshtein distance defines the Word Error Rate (WER)—computed as (S + D + I)/N where S, D, and I are word substitutions, deletions, and insertions against a reference transcript of N words. In search engines and database indexing, Levenshtein automata and BK-trees (Burkhard–Keller metric trees exploiting the triangle inequality) retrieve all dictionary entries within edit distance k ≤ 2 without scanning the entire lexicon.

What is the difference between restricted and unrestricted Damerau–Levenshtein distance?

Over 80% of human typing errors involve either a single-character edit or swapping two adjacent characters (such as typing teh for the). Restricted Damerau–Levenshtein distance (optimal string alignment) allows transposing adjacent characters provided no substring is edited more than once, which violates the triangle inequality on certain strings; true Damerau–Levenshtein distance allows insertions or deletions inside transposed substrings and remains a valid metric.

How is Levenshtein distance related to the longest common subsequence (LCS)?

If substitutions are disallowed (or assigned cost 2, equivalent to one deletion plus one insertion), the edit distance reduces to d_LCS(A, B) = m + n − 2 · |LCS(A, B)|, where |LCS(A, B)| is the length of the longest common subsequence.

1. Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10(8), 707–710. https://doi.org/10.1007/978-1-4757-2931-3_1
2. Wagner, R. A., & Fischer, M. J. (1974). The string-to-string correction problem. Journal of the ACM, 21(1), 168–173. https://doi.org/10.1145/321796.321811
3. Myers, G. (1999). A fast bit-vector algorithm for approximate string matching based on dynamic programming. Journal of the ACM, 46(3), 395–415. https://doi.org/10.1145/316542.316550
4. Backurs, A., & Indyk, P. (2015). Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, 51–58. https://doi.org/10.1145/2746539.2746612