Levenshtein Edit Distance

Levenshtein Edit Distance

Mathematical Definition

Let source s have length m and target t have length n. D(i,j) is the minimum cost of transforming the first i source letters into the first j target letters. Rows therefore represent source prefixes, while columns represent target prefixes. The indices i and j are prefix lengths; the corresponding final characters have zero-based indices i−1 and j−1.

The first candidate deletes the final source letter. The second inserts the final target letter. The diagonal candidate keeps equal letters or substitutes one letter for another. Base cases are explicit: an empty source requires j insertions, and an empty target requires i deletions.

Key Concepts

Why the recurrence finds a minimum

Consider the last column of an optimal alignment. It pairs a source letter with a gap, a gap with a target letter, or one letter from each string. Removing that column leaves exactly one of the three smaller prefix problems. If that prefix alignment were not optimal, replacing it with a cheaper one would improve the full alignment. Conversely, each candidate extends a valid prefix alignment, so the least candidate cost is attainable.

Tabulation and cell inspection

The row and column for empty prefixes are initialized first. Interior cells can then be computed from left to right in each row. The inspected cell highlights its three predecessors and every minimum candidate, including ties. Revealing cells changes the visible computation without approximating their integer values. The final distance and alignment appear when the table is complete; a base-only table is complete immediately.

Traceback and ambiguity

Start at D(m,n) and follow a predecessor that realizes the current value. A diagonal contributes a Keep or Substitute column, an upward move contributes Delete, and a leftward move contributes Insert. Reverse these columns to read the forward transformation. Several alignments can have the same cost. This explorer makes the displayed choice reproducible by preferring an optimal diagonal, then deletion, then insertion during backward traversal. Toggling traceback changes the matrix highlights, while the chosen alignment remains available.

Checked examples

• kitten → sitting: replace k with s, replace e with i, and insert g. The alignment kitten- / sitting costs 3; four equal-letter columns cost zero.
• flaw → lawn: delete f, keep l/a/w, then insert n. The alignment flaw- / -lawn costs 2.
• abc → yabd: insert y and replace c with d. At D(3,4), the diagonal, deletion and insertion candidates are 2, 3 and 3. In particular, deleting c costs D(2,4)+1=2+1=3: ab → yabd requires inserting y and d.
• ab → ba: all final candidates cost 2. Diagonal-first traceback displays two substitutions. A deletion followed by an insertion is another optimum; an adjacent swap is not a single allowed edit.

Complexity and bounded inputs

There are (m+1)(n+1) cells, with constant work per interior cell. Building and storing the full visualization costs O((m+1)(n+1)) time and space, including empty-input initialization; for positive lengths this is O(mn). Traceback has at most m+n moves. A distance-only implementation can retain two rows, while reconstructing the displayed alignment here uses the full table. The user controls accept 0–8 lowercase ASCII letters per string. This is a readable demonstration limit, not a restriction of the general algorithm. Invalid characters and excess length are rejected without trimming or truncation.

Properties and other edit models

With these unit costs, distance is a metric: it is nonnegative, is zero exactly for identical strings, is symmetric, and satisfies the triangle inequality because two edit sequences can be concatenated. The length difference gives a lower bound, and replacing the overlapping letters then inserting or deleting the remainder gives an upper bound max(m,n). Unequal-letter substitution has cost one here. Weighted alignment, local alignment, affine gap penalties and models allowing transposition solve different problems.

Historical Context

Vladimir Levenshtein studied distances associated with insertion, deletion and related coding errors in the 1960s. Robert Wagner and Michael Fischer published the string-to-string correction algorithm in 1974, showing how prefix subproblems produce an algorithm whose running time is proportional to the product of the string lengths. The term Wagner–Fischer commonly refers to this dynamic-programming computation.

Real-world Applications

• Spelling suggestions: compare a typed word with dictionary candidates by edit cost. Context and word frequency can also affect which suggestion is useful.
• Data cleanup: find near-duplicate short identifiers or names. Text normalization and the chosen alphabet must be defined separately from the distance calculation.
• Sequence comparison: align symbolic sequences and expose mismatches or gaps. Biological applications often require richer scoring systems than the unit costs in this explorer.
• Evaluation: count insertions, deletions and substitutions in predicted sequences. Character-level distance and word-level distance use different units.

Related Concepts

• Dynamic Programming: reuses overlapping subproblem values; edit distance has two prefix dimensions instead of the Fibonacci example's single index.
• Knapsack Problem: another table-based optimization, with item and capacity states instead of two string prefixes.
• KMP and Aho-Corasick: report exact substring matches; Levenshtein distance allows edits and compares the complete strings.
• Hamming distance: counts unequal positions in equal-length strings, without insertion or deletion. Allowing those operations can make Levenshtein distance smaller.

References

• NIST Dictionary of Algorithms and Data Structures: Levenshtein distance.
• Cornell CS4820: Edit Distance, recurrence, tabulation and alignment.
• Cornell CS4820: Edit Distance Analysis.
• Wagner and Fischer (1974), The String-to-String Correction Problem.