---
title: Minimum Edit Distance
module: Foundations
moduleNumber: 1
lessonNumber: 3
order: 103
summary: >
  Much of language processing needs to measure how similar two strings are — a
  speller ranking corrections, a diff tool, a coreference resolver. Minimum edit
  distance counts the insertions, deletions, and substitutions that turn one
  string into another, computed by a dynamic-programming table. We fill the table
  for intention to execution, backtrace to recover the alignment, and see how the
  same machinery generalizes to weighted edits, Viterbi, and biological sequence
  alignment.
topics: [Foundations]
sources:
  - book: Jurafsky & Martin
    ref: "Ch. 2 — Regular Expressions, Text Normalization, Edit Distance; §2.5 Minimum Edit Distance"
---

This builds on [Regular Expressions and Text Normalization](/natural-language-processing/foundations/regex-and-text-normalization),
which turned a raw character stream into clean tokens. That gave us strings to work
with; this lesson gives us a way to _compare_ two of them.

## Measuring string similarity

Much of language processing needs to measure how _similar_ two strings are. A speller
seeing `graffe` should rank `giraffe` (one insertion away) above `grail` (several
edits away). A coreference system, deciding whether "Stanford President Marc
Tessier-Lavigne" and "Stanford University President Marc Tessier-Lavigne" name the
same person, uses the fact that the strings differ by a single word. **Minimum edit distance** quantifies both intuitions: it counts the
smallest number of one-character edits that turn one string into the other, so a small
distance means the strings are close.

> **Definition (Minimum edit distance).** The minimum edit distance between two
> strings is the minimum number of editing operations — **insertion**, **deletion**,
> **substitution** — needed to transform one string into the other. Under **Levenshtein
> distance** each operation costs $1$; a common variant charges $2$ for a substitution,
> treating it as one deletion plus one insertion.

The clearest way to see a distance is as an **alignment** — a correspondence between
the characters of the two strings, with a symbol under each column recording the
operation. For `intention` → `execution`, one minimum alignment uses five operations
(one deletion, three substitutions, one insertion); under the substitution-cost-2
Levenshtein it costs $8$.

$$
% caption: An alignment of intention (top) with execution (bottom). Each column is
% one operation: d deletes, s substitutes, i inserts; a blank is a gap. The
% operation row spells out one minimum-cost edit sequence.
\begin{tikzpicture}[>=stealth, font=\ttfamily,
  cell/.style={minimum width=6mm, minimum height=6mm, align=center, font=\ttfamily\small}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \c/\x in {I/0, N/1, T/2, E/3, {}/4, N/5, T/6, I/7, O/8, N/9} \node[cell] at (\x,1.0) {\c};
  \foreach \c/\x in {{}/0, E/1, X/2, E/3, C/4, U/5, T/6, I/7, O/8, N/9} \node[cell] at (\x,0.2) {\c};
  \foreach \x in {0,...,9} \draw[black] (\x,0.9) -- (\x,0.3);
  \foreach \c/\x in {d/0, s/1, s/2, {}/3, i/4, {}/5, {}/6, {}/7, {}/8, {}/9} \node[cell, text=acc] at (\x,-0.6) {\c};
\end{tikzpicture}
$$

### The dynamic-programming algorithm

How do we _find_ the minimum? Naively, the space of edit sequences is enormous — but
most sequences pass through the same intermediate strings, so the work collapses.
That overlap is what **dynamic programming** exploits: solve the big problem by
combining stored solutions to overlapping sub-problems. Minimum edit distance is one
of the field's canonical DP algorithms, alongside Viterbi decoding and CKY parsing;
if you have met DP in a string-algorithms course, this is the same table-driven
method, applied to language.

Let $X$ be the source string of length $n$ and $Y$ the target of length $m$. Define
$D[i,j]$ as the edit distance between the first $i$ characters of $X$ and the first
$j$ characters of $Y$. The answer is $D[n,m]$. The base cases are the distances from
the empty string: turning $i$ characters into nothing takes $i$ deletions, so
$D[i,0]=i$; the reverse takes $j$ insertions, so $D[0,j]=j$. Each interior cell is
the cheapest of the three moves that reach it — a deletion from above, an insertion
from the left, or a substitution (or match) from the diagonal:

$$
D[i,j] = \min \begin{cases}
  D[i-1,\, j] + \text{del-cost}(X[i]) \\
  D[i,\, j-1] + \text{ins-cost}(Y[j]) \\
  D[i-1,\, j-1] + \text{sub-cost}(X[i], Y[j])
\end{cases}
$$

The three cases are the three ways the last characters can be handled:

- **Deletion**: align $X$'s first $i-1$ characters against all $j$ of $Y$'s, then delete $X[i]$
- **Insertion**: align all $i$ against the first $j-1$, then insert $Y[j]$
- **Substitution or match**: align the first $i-1$ against the first $j-1$, then substitute $X[i]$ for $Y[j]$, or pay nothing if they already match

The cell keeps the cheapest of the three.

Under the Levenshtein weighting — insertion and deletion cost $1$, a substitution
costs $2$ except that matching a letter to itself is free — this specializes to

$$
D[i,j] = \min \begin{cases}
  D[i-1,\, j] + 1 \\
  D[i,\, j-1] + 1 \\
  D[i-1,\, j-1] + \begin{cases} 2 & \text{if } X[i] \ne Y[j] \\ 0 & \text{if } X[i] = Y[j] \end{cases}
\end{cases}
$$

Fill the table row by row from the bottom-left corner: initialize the border, then
sweep every interior cell, taking the running minimum.

```algorithm
caption: $\textsc{Min-Edit-Distance}(X, Y)$ — edit distance by dynamic programming
input: source string $X$, target string $Y$
$n \gets$ length of $X$
$m \gets$ length of $Y$
create a distance matrix $D[0 \ldots n,\, 0 \ldots m]$
$D[0,0] \gets 0$
for $i = 1$ to $n$ do
  $D[i,0] \gets D[i-1,0] + \text{del-cost}(X[i])$ // an empty target: delete every source char
for $j = 1$ to $m$ do
  $D[0,j] \gets D[0,j-1] + \text{ins-cost}(Y[j])$ // an empty source: insert every target char
for $i = 1$ to $n$ do
  for $j = 1$ to $m$ do
    $D[i,j] \gets \min\bigl(D[i-1,j] + \text{del-cost}(X[i]),\ D[i-1,j-1] + \text{sub-cost}(X[i], Y[j]),\ D[i,j-1] + \text{ins-cost}(Y[j])\bigr)$
return $D[n,m]$
```

### A worked table

For $X = \texttt{intention}$ and $Y = \texttt{execution}$ under the substitution-cost-2
Levenshtein, the completed matrix reads $D[9,9] = 8$ in the top-right corner. The
source runs up the left edge, the target across the bottom; each cell holds the
minimum edit distance between the two prefixes meeting at it.

$$
% caption: The dynamic-programming matrix for the edit distance between intention
% (source, left edge, read bottom to top) and execution (target, bottom edge),
% with insertion and deletion cost 1 and substitution cost 2. The answer, 8, sits
% in the top-right cell.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  hd/.style={font=\ttfamily\small},
  num/.style={font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % body grid: 10 columns x 10 rows, offset by one header column/row
  \draw[black] (1,1) grid (11,11);
  % header separators
  \draw[black] (0,1) rectangle (1,11);
  \draw[black] (1,0) rectangle (11,1);
  % corner label
  \node[hd, font=\ttfamily\footnotesize] at (0.5,0.5) {src};
  % column headers (target: # e x e c u t i o n) across the bottom
  \node[hd] at (1.5,0.5) {\#};
  \node[hd] at (2.5,0.5) {e};
  \node[hd] at (3.5,0.5) {x};
  \node[hd] at (4.5,0.5) {e};
  \node[hd] at (5.5,0.5) {c};
  \node[hd] at (6.5,0.5) {u};
  \node[hd] at (7.5,0.5) {t};
  \node[hd] at (8.5,0.5) {i};
  \node[hd] at (9.5,0.5) {o};
  \node[hd] at (10.5,0.5) {n};
  % row headers (source: # i n t e n t i o n) up the left edge
  \node[hd] at (0.5,1.5) {\#};
  \node[hd] at (0.5,2.5) {i};
  \node[hd] at (0.5,3.5) {n};
  \node[hd] at (0.5,4.5) {t};
  \node[hd] at (0.5,5.5) {e};
  \node[hd] at (0.5,6.5) {n};
  \node[hd] at (0.5,7.5) {t};
  \node[hd] at (0.5,8.5) {i};
  \node[hd] at (0.5,9.5) {o};
  \node[hd] at (0.5,10.5) {n};
  % matrix body, Fig 2.18 values
  \node[num] at (1.5,1.5) {0};
  \node[num] at (2.5,1.5) {1};
  \node[num] at (3.5,1.5) {2};
  \node[num] at (4.5,1.5) {3};
  \node[num] at (5.5,1.5) {4};
  \node[num] at (6.5,1.5) {5};
  \node[num] at (7.5,1.5) {6};
  \node[num] at (8.5,1.5) {7};
  \node[num] at (9.5,1.5) {8};
  \node[num] at (10.5,1.5) {9};
  \node[num] at (1.5,2.5) {1};
  \node[num] at (2.5,2.5) {2};
  \node[num] at (3.5,2.5) {3};
  \node[num] at (4.5,2.5) {4};
  \node[num] at (5.5,2.5) {5};
  \node[num] at (6.5,2.5) {6};
  \node[num] at (7.5,2.5) {7};
  \node[num] at (8.5,2.5) {6};
  \node[num] at (9.5,2.5) {7};
  \node[num] at (10.5,2.5) {8};
  \node[num] at (1.5,3.5) {2};
  \node[num] at (2.5,3.5) {3};
  \node[num] at (3.5,3.5) {4};
  \node[num] at (4.5,3.5) {5};
  \node[num] at (5.5,3.5) {6};
  \node[num] at (6.5,3.5) {7};
  \node[num] at (7.5,3.5) {8};
  \node[num] at (8.5,3.5) {7};
  \node[num] at (9.5,3.5) {8};
  \node[num] at (10.5,3.5) {7};
  \node[num] at (1.5,4.5) {3};
  \node[num] at (2.5,4.5) {4};
  \node[num] at (3.5,4.5) {5};
  \node[num] at (4.5,4.5) {6};
  \node[num] at (5.5,4.5) {7};
  \node[num] at (6.5,4.5) {8};
  \node[num] at (7.5,4.5) {7};
  \node[num] at (8.5,4.5) {8};
  \node[num] at (9.5,4.5) {9};
  \node[num] at (10.5,4.5) {8};
  \node[num] at (1.5,5.5) {4};
  \node[num] at (2.5,5.5) {3};
  \node[num] at (3.5,5.5) {4};
  \node[num] at (4.5,5.5) {5};
  \node[num] at (5.5,5.5) {6};
  \node[num] at (6.5,5.5) {7};
  \node[num] at (7.5,5.5) {8};
  \node[num] at (8.5,5.5) {9};
  \node[num] at (9.5,5.5) {10};
  \node[num] at (10.5,5.5) {9};
  \node[num] at (1.5,6.5) {5};
  \node[num] at (2.5,6.5) {4};
  \node[num] at (3.5,6.5) {5};
  \node[num] at (4.5,6.5) {6};
  \node[num] at (5.5,6.5) {7};
  \node[num] at (6.5,6.5) {8};
  \node[num] at (7.5,6.5) {9};
  \node[num] at (8.5,6.5) {10};
  \node[num] at (9.5,6.5) {11};
  \node[num] at (10.5,6.5) {10};
  \node[num] at (1.5,7.5) {6};
  \node[num] at (2.5,7.5) {5};
  \node[num] at (3.5,7.5) {6};
  \node[num] at (4.5,7.5) {7};
  \node[num] at (5.5,7.5) {8};
  \node[num] at (6.5,7.5) {9};
  \node[num] at (7.5,7.5) {8};
  \node[num] at (8.5,7.5) {9};
  \node[num] at (9.5,7.5) {10};
  \node[num] at (10.5,7.5) {11};
  \node[num] at (1.5,8.5) {7};
  \node[num] at (2.5,8.5) {6};
  \node[num] at (3.5,8.5) {7};
  \node[num] at (4.5,8.5) {8};
  \node[num] at (5.5,8.5) {9};
  \node[num] at (6.5,8.5) {10};
  \node[num] at (7.5,8.5) {9};
  \node[num] at (8.5,8.5) {8};
  \node[num] at (9.5,8.5) {9};
  \node[num] at (10.5,8.5) {10};
  \node[num] at (1.5,9.5) {8};
  \node[num] at (2.5,9.5) {7};
  \node[num] at (3.5,9.5) {8};
  \node[num] at (4.5,9.5) {9};
  \node[num] at (5.5,9.5) {10};
  \node[num] at (6.5,9.5) {11};
  \node[num] at (7.5,9.5) {10};
  \node[num] at (8.5,9.5) {9};
  \node[num] at (9.5,9.5) {8};
  \node[num] at (10.5,9.5) {9};
  \node[num] at (1.5,10.5) {9};
  \node[num] at (2.5,10.5) {8};
  \node[num] at (3.5,10.5) {9};
  \node[num] at (4.5,10.5) {10};
  \node[num] at (5.5,10.5) {11};
  \node[num] at (6.5,10.5) {12};
  \node[num] at (7.5,10.5) {11};
  \node[num] at (8.5,10.5) {10};
  \node[num] at (9.5,10.5) {9};
  % highlight the answer in the top-right cell
  \node[num, text=acc, font=\bfseries] at (10.5,10.5) {8};
  \draw[acc, thick] (10,10) rectangle (11,11);
\end{tikzpicture}
$$

### The backtrace

The distance alone gives the cost of the best alignment; with one extra bookkeeping
step, the same table also recovers the alignment itself. While filling the matrix, store in each
cell a **backpointer** to the neighbor (or neighbors) that supplied its minimum: a
left arrow for an insertion, a down arrow for a deletion, a diagonal for a
substitution or match. After the table is full, **backtrace** from the top-right
cell, following pointers back to the origin. The path of cells you walk is a minimum-cost
alignment — a diagonal step aligns two characters, a horizontal step is an insertion,
a vertical step a deletion.

$$
% caption: The backtrace over the edit-distance matrix. From the answer cell (top
% right) each arrow points at a predecessor that achieved the minimum; a diagonal
% aligns or substitutes, a horizontal inserts, a vertical deletes. One path back to
% the origin is a minimum-cost alignment.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % a schematic 4x4 corner of the matrix (cells 1.8 wide, 1.1 tall) showing moves
  \draw[black] (0,0) grid[xstep=1.8, ystep=1.1] (7.2,4.4);
  % current cell and its three predecessors, one label per cell
  \node[font=\footnotesize] at (6.3,3.85) {D[i,j]};
  \node[font=\footnotesize, text=black] at (4.5,3.85) {D[i,j-1]};
  \node[font=\footnotesize, text=black] at (6.3,2.75) {D[i-1,j]};
  \node[font=\footnotesize, text=black] at (4.5,2.75) {D[i-1,j-1]};
  % the three incoming arrows into the current cell, labels beside the boxes
  \draw[->, acc, thick] (5.9,4.05) -- (5.1,4.05);
  \node[font=\scriptsize, text=acc, anchor=south] at (5.5,4.12) {ins};
  \draw[->, acc, thick] (6.3,3.55) -- (6.3,3.05);
  \node[font=\scriptsize, text=acc, anchor=west] at (6.55,3.3) {del};
  \draw[->, acc, thick] (5.7,3.5) -- (5.1,3.0);
  \node[font=\scriptsize, text=acc, anchor=west] at (5.55,3.15) {sub};
  % chosen backtrace path along the diagonal toward the origin
  \draw[->, acc, very thick] (4.2,2.5) -- (3.1,1.7);
  \draw[->, acc, very thick] (2.7,1.5) -- (1.6,0.85);
  \draw[->, acc, very thick] (1.3,0.75) -- (0.7,0.4);
  \node[font=\scriptsize, text=acc, anchor=south west] at (0.15,0.42) {origin};
\end{tikzpicture}
$$

Walk the `intention` → `execution` table concretely. Starting from the answer cell
$D[9,9]=8$, at each step you look at the three neighbors that could have produced the
cell and step to whichever one the recurrence used. The path recovered is a diagonal
at every column except one deletion near the start and one insertion in the middle,
and reading the operations off the path in source order gives:

$$
\begin{array}{lccccccccc}
\text{source } X: & \texttt{i} & \texttt{n} & \texttt{t} & \texttt{e} & \texttt{n} & \texttt{t} & \texttt{i} & \texttt{o} & \texttt{n} \\[2pt]
\text{target } Y: & \texttt{e} & \texttt{x} & \texttt{e} & \texttt{c} & \texttt{u} & \texttt{t} & \texttt{i} & \texttt{o} & \texttt{n} \\[2pt]
\text{op}: & \text{sub} & \text{sub} & \text{sub} & \text{sub} & \text{sub} & \text{match} & \text{match} & \text{match} & \text{match}
\end{array}
$$

Adjusting for the one deletion and one insertion in the full alignment, the operation
tally is one deletion, one insertion, and three substitutions that touch distinct
characters, plus four free matches on the shared suffix `tion`. Under the
substitution-cost-2 weighting that is $1 + 1 + 3\cdot 2 = 8$, matching the corner
cell exactly. The alignment is what a downstream task consumes: a speller uses it to
say _which_ letters to change, and a diff tool uses the same path to show insertions
and deletions between two files.

Drawn on the real matrix, the path is not the schematic diagonal but a concrete
staircase through the actual cells. It leaves the answer $D[9,9]=8$, walks the free
suffix `tion` straight down the diagonal at constant cost $8$, drops one cell for the
$n \to u$ substitution, takes one horizontal insertion of `c`, matches `e`, then two
substitutions and a single vertical deletion of the leading `i` land it at the origin.
Each arrow points from a cell to the predecessor that supplied its minimum, so the
whole path is read from top-right to bottom-left; reversing it recovers the edit
sequence in source order.

$$
% caption: The minimum-cost backtrace traced on the real intention-to-execution
% matrix. From the answer cell 8 (top right) each arrow points to the predecessor
% that achieved the minimum; the highlighted cells are the optimal alignment. Four
% diagonal matches down the shared suffix tion, one diagonal substitution n to u,
% one horizontal insertion of c, one diagonal match e, two more substitutions, and
% one vertical deletion of the leading i reach the origin at total cost 8.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  hd/.style={font=\ttfamily\small},
  num/.style={font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  \draw[black] (1,1) grid (11,11);
  \draw[black] (0,1) rectangle (1,11);
  \draw[black] (1,0) rectangle (11,1);
  \node[hd, font=\ttfamily\footnotesize] at (0.5,0.5) {src};
  % target column headers across the bottom
  \foreach \c/\x in {\#/1.5, e/2.5, x/3.5, e/4.5, c/5.5, u/6.5, t/7.5, i/8.5, o/9.5, n/10.5}
    \node[hd] at (\x,0.5) {\c};
  % source row headers up the left edge
  \foreach \r/\y in {\#/1.5, i/2.5, n/3.5, t/4.5, e/5.5, n/6.5, t/7.5, i/8.5, o/9.5, n/10.5}
    \node[hd] at (0.5,\y) {\r};
  % highlight the backtrace path cells (light tint) BEHIND the numbers
  \foreach \x/\y in {1.5/1.5, 1.5/2.5, 2.5/3.5, 3.5/4.5, 4.5/5.5, 5.5/5.5, 6.5/6.5, 7.5/7.5, 8.5/8.5, 9.5/9.5, 10.5/10.5}
    \fill[acc!12] (\x-0.5,\y-0.5) rectangle (\x+0.5,\y+0.5);
  % matrix body values (Fig 2.18)
  \foreach \x/\v in {1.5/0,2.5/1,3.5/2,4.5/3,5.5/4,6.5/5,7.5/6,8.5/7,9.5/8,10.5/9} \node[num] at (\x,1.5) {\v};
  \foreach \x/\v in {1.5/1,2.5/2,3.5/3,4.5/4,5.5/5,6.5/6,7.5/7,8.5/6,9.5/7,10.5/8} \node[num] at (\x,2.5) {\v};
  \foreach \x/\v in {1.5/2,2.5/3,3.5/4,4.5/5,5.5/6,6.5/7,7.5/8,8.5/7,9.5/8,10.5/7} \node[num] at (\x,3.5) {\v};
  \foreach \x/\v in {1.5/3,2.5/4,3.5/5,4.5/6,5.5/7,6.5/8,7.5/7,8.5/8,9.5/9,10.5/8} \node[num] at (\x,4.5) {\v};
  \foreach \x/\v in {1.5/4,2.5/3,3.5/4,4.5/5,5.5/6,6.5/7,7.5/8,8.5/9,9.5/10,10.5/9} \node[num] at (\x,5.5) {\v};
  \foreach \x/\v in {1.5/5,2.5/4,3.5/5,4.5/6,5.5/7,6.5/8,7.5/9,8.5/10,9.5/11,10.5/10} \node[num] at (\x,6.5) {\v};
  \foreach \x/\v in {1.5/6,2.5/5,3.5/6,4.5/7,5.5/8,6.5/9,7.5/8,8.5/9,9.5/10,10.5/11} \node[num] at (\x,7.5) {\v};
  \foreach \x/\v in {1.5/7,2.5/6,3.5/7,4.5/8,5.5/9,6.5/10,7.5/9,8.5/8,9.5/9,10.5/10} \node[num] at (\x,8.5) {\v};
  \foreach \x/\v in {1.5/8,2.5/7,3.5/8,4.5/9,5.5/10,6.5/11,7.5/10,8.5/9,9.5/8,10.5/9} \node[num] at (\x,9.5) {\v};
  \foreach \x/\v in {1.5/9,2.5/8,3.5/9,4.5/10,5.5/11,6.5/12,7.5/11,8.5/10,9.5/9} \node[num] at (\x,10.5) {\v};
  % answer cell highlighted
  \node[num, text=acc, font=\bfseries] at (10.5,10.5) {8};
  \draw[acc, thick] (10,10) rectangle (11,11);
  % backtrace arrows, each from a cell to its predecessor (drawn between cell centers,
  % shortened so heads sit clear of the numbers)
  \draw[->, acc, very thick] (10.35,10.35) -- (9.65,9.65);
  \draw[->, acc, very thick] (9.35,9.35) -- (8.65,8.65);
  \draw[->, acc, very thick] (8.35,8.35) -- (7.65,7.65);
  \draw[->, acc, very thick] (7.35,7.35) -- (6.65,6.65);
  \draw[->, acc, very thick] (6.35,6.35) -- (5.65,5.65);
  \draw[->, acc, very thick] (5.5,6.15) -- (5.5,5.85);   % insertion of c: horizontal step (down one column)
  \draw[->, acc, very thick] (5.35,5.35) -- (4.65,4.65);
  \draw[->, acc, very thick] (4.35,4.35) -- (3.65,3.65);
  \draw[->, acc, very thick] (3.35,3.35) -- (2.65,2.65);
  \draw[->, acc, very thick] (2.35,2.5) -- (1.65,2.5);   % deletion of i: vertical step (down one row)
  \draw[->, acc, very thick] (1.5,2.15) -- (1.5,1.85);
  % operation annotations to the right, aligned to path rows
  \node[anchor=west, font=\scriptsize, text=acc] at (11.2,10.5) {match n};
  \node[anchor=west, font=\scriptsize, text=acc] at (11.2,9.5)  {match o};
  \node[anchor=west, font=\scriptsize, text=acc] at (11.2,8.5)  {match i};
  \node[anchor=west, font=\scriptsize, text=acc] at (11.2,7.5)  {match t};
  \node[anchor=west, font=\scriptsize, text=acc] at (11.2,6.5)  {sub n/u};
  \node[anchor=west, font=\scriptsize, text=black] at (11.2,5.5)  {ins c, match e};
  \node[anchor=west, font=\scriptsize, text=acc] at (11.2,4.5)  {sub t/x};
  \node[anchor=west, font=\scriptsize, text=acc] at (11.2,3.5)  {sub n/e};
  \node[anchor=west, font=\scriptsize, text=black] at (11.2,2.5)  {del i};
\end{tikzpicture}
$$

That extra step generalizes. Allow arbitrary operation costs — say, cheaper
substitutions between letters adjacent on a keyboard — and the same table becomes a
spelling-correction engine. Replace "minimum cost" with "maximum probability" and the
recurrence becomes the **Viterbi** algorithm, used throughout sequence labeling and
speech recognition. The DP table filled for `intention` → `execution` is the same
machinery, reused across the subject.[^jm-edit]

### Weighted edits and the cost of the alignment

The Levenshtein weighting charges every substitution the same, but the framework
does not require it. Replace the constant `sub-cost` with a per-pair cost — a
confusion matrix — and the same table computes a distance tuned to a real error
model. For spelling correction the natural costs come from how often one letter is
mistyped for another: substituting `e` for `a` (adjacent readings, common
typo) should cost less than substituting `e` for `q`. For biological sequence
alignment the costs come from substitution matrices estimated from evolution, and the
identical DP, run with a gap penalty and those costs, is the **Needleman–Wunsch**
algorithm. Nothing in the recurrence changes; only the three cost functions do. This
is why edit distance is a template rather than a single algorithm: fix the costs and
you fix the notion of "similar."

[^jm-edit]: **Jurafsky & Martin**, §2.5 — Minimum Edit Distance: the Levenshtein distance, the dynamic-programming recurrence and algorithm, the intention/execution worked table, and the backtrace that recovers an alignment. The generalization with per-pair costs and gap penalties is Needleman & Wunsch, "A general method applicable to the search for similarities in the amino acid sequence of two proteins," _Journal of Molecular Biology_ 48 (1970).