Edit Distance

in reviewThis lesson is complete and being validated before release - details may still change.

Edit distance

Loading interactive demo…

The table has one row per prefix of the first word and one column per prefix of the second, the letters along the edges and a blank header for the empty prefix. Each cell holds the cheapest way to turn its row prefix into its column prefix, read from its three neighbours. The strips beneath are the two words, the edits read off by the walk back from the corner, and the tapped cell.Take the tour, or press and explore. Legend:

The panel beside the stage is the real EditDistance class from the published library executing in your browser, with the current line highlighted.

The cell being filled or left, the path walked back so far, and the tapped cell.
A cell won by a match: the diagonal neighbour, no cost added.
A cell won by a change, and the diagonal neighbour while a cell is filled.
A cell won by a deletion, and the neighbour above while a cell is filled.
A cell won by an insertion, and the neighbour to the left while a cell is filled.
The border, the letter headers, and the faint finished table before play reaches it.

cells counts the inner cells filled so far, distanceis the corner's value once the recurrence reaches it,edits the non-match steps read off so far by kind,matches the free steps, and path how far the walk back has come.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The subproblems are pairs of prefixes. To turn $a$ into $b$ with the fewest single-letter edits, ask the smaller question first: what is the cheapest way to turn the first $i$ letters of $a$ into the first $j$ letters of $b$ ? Call it $D(i, j)$ . The last edit of any cheapest script does one of three things, and each one leaves a smaller pair of prefixes behind:

D(i, j) = \min \begin{cases} D(i-1, j-1) + c(a_i, b_j) & \text{line the letters up} \\ D(i-1, j) + 1 & \text{delete } a_i \\ D(i, j-1) + 1 & \text{insert } b_j \end{cases}

where $c(a_i, b_j)$ is $0$ when the letters match and the change cost otherwise. The border is the base case: $D(i, 0) = i$ and $D(0, j) = j$ , because a prefix against nothing costs one edit per letter. On the stage, each inner cell looks at exactly these three neighbours, and the one it copies from is the tint it takes.

Why a table and not a tree. The recurrence asks for $D(i-1, j-1)$ , $D(i-1, j)$ , and $D(i, j-1)$ , and those three ask for their own neighbours in turn, so plain recursion would visit the same pair of prefixes exponentially often. There are only $(m+1)(n+1)$ pairs. Filling them row by row, every neighbour a cell needs is already above it or to its left, so the whole thing is

O(mn) \text{ time and } O(mn) \text{ space}

with the corner $D(m, n)$ as the answer. The value alone needs only two rows, $O(\min(m, n))$ space; keeping the whole table is what lets the walk back read the script out, and Hirschberg's 1975 trick recovers the script in linear space by splitting the problem at its middle row.

The walk back is the proof. A cell's value says how cheap, not how. But the cell also remembers which neighbour won, so from the corner you can leave each cell by its winning neighbour until you reach the origin. A diagonal step is a match or a change, a step up deletes a letter of $a$ , a step left inserts a letter of $b$ . Read in reverse, those steps are a script that costs exactly $D(m, n)$ , which is why the count and the script always agree. Ties are broken in a fixed order (match, then delete, then insert, a change only when it is strictly cheapest), so the stage always draws one definite path; another order gives another cheapest script.

Two cost models. Levenshtein charges one for a change. The indel model charges two, a deletion plus an insertion, so a change is never worth taking and the script only deletes, inserts, and matches. The matches are then a common subsequence of the two words, the cheapest script keeps the longest one, and

D_{\text{indel}}(a, b) = m + n - 2 \cdot \mathrm{LCS}(a, b)

For kitten and sitting the longest common subsequence is ittn, four letters, so the indel distance is $6 + 7 - 8 = 5$ while the Levenshtein distance is $3$ . This is the quantity diff computes, and the second cost chip on the stage runs the same code with one constant changed.

How fast can it be. The table is quadratic, and in 2015 Backurs and Indyk showed that an exact algorithm in $O(n^{2-\varepsilon})$ time for any constant $\varepsilon$ would falsify the strong exponential time hypothesis. That is a conditional lower bound, not a proof, but it is why fifty years of work have produced faster special cases (a bounded distance, a long common prefix, bit-parallel tricks) and not a faster general algorithm.

Where this goes next. The knapsack lesson keeps the shape and changes the axes: one row per item, one column per remaining capacity, each cell the better of taking an item or leaving it, and the last row read backward names the items that won.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

One choose serves the fill and the walk back. The three candidates and the winning move are computed in one private method, called once per cell while filling and once per step while backtracking. The table does not store the winning move; the walk back recomputes it from the same arithmetic, so the two can never disagree.
The border is one base method. The origin, the top row, and the first column are all a prefix against nothing, so one method writes max(i, j) and emits the one base event; the trace tag has a single call site, which the source-line mapping relies on.
Ties have an order. A match wins whenever the diagonal is cheapest, then a delete, then an insert; a change is taken only when it is strictly cheapest. Under indel costs a change is never strictly cheaper than a delete plus an insert, so the script never substitutes, which is what makes the indel distance the longest common subsequence count.
The script is built backward and reversed once. The walk back pushes each step as it leaves a cell, from the corner toward the origin, and reverse turns it into a forward script; replaying the steps on a produces b, which the library's tests check.
cells counts the inner table only. The report's cells is m * n, the cells the recurrence actually filled; the border is the base case and is not counted as work.
A length cap, not a performance fix. EDIT_MAX_LENGTH is 8 because the stage draws every cell as a tile with a glyph; the algorithm itself has no such limit, and a RangeError names the cap rather than silently truncating.

Vladimir Levenshtein defined the distance in 1965 while studying codes that correct deletions, insertions, and reversals, and in the same years Frederick Damerau was counting the single edits behind most typing errors. The table that computes it was found again and again, in speech recognition, in molecular biology, and in the string-to-string correction paper of Wagner and Fischer whose name it carries in most courses. Every version is the same recurrence over pairs of prefixes, and the walk back that reads the edits out is what diff tools and sequence aligners have run ever since.

1964Frederick Damerau - Reports that in an information-retrieval system more than 80 percent of spelling errors were a single insertion, deletion, substitution, or transposition of adjacent letters, and corrects words at most one such edit away.source
1965Vladimir Levenshtein - Introduces the distance in a paper on binary codes capable of correcting deletions, insertions, and reversals, in the Doklady of the Soviet Academy of Sciences; the English translation appears in 1966.source
1970Saul Needleman and Christian Wunsch - Align protein and nucleotide sequences globally with the same prefix table, one of the first applications of dynamic programming to the comparison of biological sequences.source
1974Robert Wagner and Michael Fischer - 'The String-to-String Correction Problem' in the Journal of the ACM gives the table the lesson fills; the algorithm had been found independently several times before, from Vintsyuk in 1968 on.source
1975Dan Hirschberg - A linear space algorithm for computing maximal common subsequences, in Communications of the ACM: the alignment itself, not just its cost, in space proportional to the shorter string while the time stays quadratic.source

Used today

Spell checking - A misspelled word's suggestions are the dictionary words a small edit distance away; Damerau's count says one edit covers most typos.
diff and version control - diff and the merges in Git line up two files by their longest common subsequence, which is the indel edit distance of this lesson's second cost model.
Sequence alignment - Needleman-Wunsch and its descendants align DNA and protein sequences with the same table, with a scoring matrix in place of a flat cost per change.
Fuzzy search - Approximate lookup in text databases and optical character recognition cleanup both ask which stored string is within a few edits of the one seen.

pair

costs

cells: 42 of 42
distance: 3
edits: 2 sub, 1 ins, 0 del
matches: 4
path: 7 of 7

edit-distance.ts

import type { Tracer } from "../trace";/** The cost model: Levenshtein charges a substitution 1, indel charges 2 (a deletion plus an insertion, what `diff` and LCS measure). */export const EDIT_COSTS = ["levenshtein", "indel"] as const;export type EditCosts = (typeof EDIT_COSTS)[number];/** What one substitution costs under each model; a deletion or an insertion always costs 1. */export const EDIT_SUBSTITUTE_COST: Record<EditCosts, number> = { levenshtein: 1, indel: 2 };/** The longest string either side takes, so the table is at most 9 by 9. */export const EDIT_MAX_LENGTH = 8;/** The four ways a cell is reached: along the diagonal with no cost (match) or the substitution cost, from above (delete a's char), or from the left (insert b's char). */export const EDIT_OPS = ["match", "substitute", "delete", "insert"] as const;export type EditOp = (typeof EDIT_OPS)[number];export interface EditDistanceOptions {  /** Default levenshtein. */  costs?: EditCosts;}/** One edit of the script that turns `a` into `b`, read off the table from the corner back to the origin and listed forward. */export interface EditStep {  op: EditOp;  /** The character of `a` the step consumes, or "" for an insert. */  a: string;  /** The character of `b` the step produces, or "" for a delete. */  b: string;  /** The cell the step leaves: `a`'s first i characters against `b`'s first j. */  i: number;  j: number;}export interface EditDistanceReport {  a: string;  b: string;  /** The cheapest cost of turning `a` into `b` under the cost model. */  distance: number;  /** The edits in forward order; replaying them on `a` gives `b`. */  steps: EditStep[];  /** Cells filled by the recurrence, the border row and column not counted. */  cells: number;  matches: number;  substitutes: number;  deletes: number;  inserts: number;}interface Candidates {  diag: number;  fromDiagonal: number;  up: number;  fromAbove: number;  left: number;  fromLeft: number;  best: number;  cheapest: number;  op: EditOp;}/** * The edit distance between two strings: the fewest single-character * edits (delete, insert, substitute) that turn one into the other, * as Levenshtein defined it in 1965 and Wagner and Fischer tabulated * it in 1974. The subproblems are prefix pairs: cell (i, j) holds the * distance from `a`'s first i characters to `b`'s first j, and it * depends only on its three neighbours. The diagonal neighbour plus * the cost of lining up a[i-1] with b[j-1] (0 when they match), the * cell above plus one (delete a's character), the cell to the left * plus one (insert b's character): the cheapest of the three wins. * The border is the base case, a prefix against nothing costs its * length. Filling the table row by row answers (m, n) in the corner, * and walking back from the corner along the winning neighbours reads * the edit script out. Under the indel cost model a substitution * costs as much as a delete plus an insert, so the script never * substitutes and the distance is m + n minus twice the longest * common subsequence. * * Ties are broken in favour of a match, then a delete, then an insert; * a substitute is chosen only when it is strictly cheapest, which is * what keeps the indel script free of substitutions. * * Time: O(m * n). Space: O(m * n) for the table the backtrack reads. */export class EditDistance {  readonly costs: EditCosts;  readonly substituteCost: number;  private a = "";  private b = "";  /** Row i, column j: the distance between the first i characters of `a` and the first j of `b`. */  private cells: number[][] = [];  constructor(options: EditDistanceOptions = {}, private readonly tracer?: Tracer) {    const costs = options.costs ?? "levenshtein";    if (!EDIT_COSTS.includes(costs)) throw new RangeError(`costs must be one of ${EDIT_COSTS.join(", ")}`);    this.costs = costs;    this.substituteCost = EDIT_SUBSTITUTE_COST[costs];  }  /** The table of the last call: rows 0..m, columns 0..n; empty before the first call. */  get table(): readonly (readonly number[])[] {    return this.cells;  }  /** Fills the table for one pair from scratch, then reads the edits back from the corner. */  distance(a: string, b: string): EditDistanceReport {    if (a.length > EDIT_MAX_LENGTH) throw new RangeError(`a must be at most ${EDIT_MAX_LENGTH} characters`);    if (b.length > EDIT_MAX_LENGTH) throw new RangeError(`b must be at most ${EDIT_MAX_LENGTH} characters`);    this.a = a;    this.b = b;    const m = a.length;    const n = b.length;    this.cells = Array.from({ length: m + 1 }, () => Array.from({ length: n + 1 }, () => 0));    this.base(0, 0);    for (let j = 1; j <= n; j++) this.base(0, j);    for (let i = 1; i <= m; i++) {      this.base(i, 0);      for (let j = 1; j <= n; j++) this.fill(i, j);    }    const steps = this.backtrack();    const count = (op: EditOp) => steps.filter((step) => step.op === op).length;    return {      a,      b,      distance: this.cells[m]![n]!,      steps,      cells: m * n,      matches: count("match"),      substitutes: count("substitute"),      deletes: count("delete"),      inserts: count("insert"),    };  }  /** The border: a prefix against the empty string costs its length, whether the corner, the top row, or the first column. */  private base(i: number, j: number): void {    const value = Math.max(i, j);    this.cells[i]![j] = value;    // ▸ the border: a prefix against nothing costs its length, one edit per letter    this.tracer?.emit("base", { i, j, value });  }  /** One inner cell: the cheapest of its three neighbours, written down with the move that won. */  private fill(i: number, j: number): void {    const { diag, up, left, best, op } = this.choose(i, j);    const { fromDiagonal, fromAbove, fromLeft, cheapest, op } = this.choose(i, j);    this.cells[i]![j] = best;    this.cells[i]![j] = cheapest;    // ▸ one cell: the cheapest of the diagonal plus the match or change cost, above plus one, left plus one    this.tracer?.emit("cell", { a: this.a[i - 1]!, b: this.b[j - 1]!, best, diag, i, j, left, op, up });    this.tracer?.emit("cell", { a: this.a[i - 1]!, b: this.b[j - 1]!, cheapest, fromDiagonal, i, j, fromLeft, op, fromAbove });  }  /** The recurrence itself: diagonal plus the match or substitution cost, above plus one, left plus one; the same arithmetic serves the fill and the backtrack. */  private choose(i: number, j: number): Candidates {    const cost = this.a[i - 1] === this.b[j - 1] ? 0 : this.substituteCost;    const diag = this.cells[i - 1]![j - 1]! + cost;    const fromDiagonal = this.cells[i - 1]![j - 1]! + cost;    const up = this.cells[i - 1]![j]! + 1;    const fromAbove = this.cells[i - 1]![j]! + 1;    const left = this.cells[i]![j - 1]! + 1;    const fromLeft = this.cells[i]![j - 1]! + 1;    const best = Math.min(diag, up, left);    const cheapest = Math.min(fromDiagonal, fromAbove, fromLeft);    let op: EditOp;    if (cost === 0 && diag === best) op = "match";    if (cost === 0 && fromDiagonal === cheapest) op = "match";    else if (up === best) op = "delete";    else if (fromAbove === cheapest) op = "delete";    else if (left === best) op = "insert";    else if (fromLeft === cheapest) op = "insert";    else op = "substitute";    return { diag, up, left, best, op };    return { fromDiagonal, fromAbove, fromLeft, cheapest, op };  }  /** From the corner back to the origin, one winning neighbour at a time; the border leaves only one way out. */  private backtrack(): EditStep[] {    const steps: EditStep[] = [];    let i = this.a.length;    let j = this.b.length;    while (i > 0 || j > 0) {      const op: EditOp = i === 0 ? "insert" : j === 0 ? "delete" : this.choose(i, j).op;      const consumesA = op !== "insert";      const consumesB = op !== "delete";      const step: EditStep = { op, a: consumesA ? this.a[i - 1]! : "", b: consumesB ? this.b[j - 1]! : "", i, j };      // ▸ from the corner, leave each cell by the neighbour that won it; the moves are the edits      this.tracer?.emit("backtrack", { a: step.a, b: step.b, i, j, op, value: this.cells[i]![j]! });      steps.push(step);      if (consumesA) i--;      if (consumesB) j--;    }    return steps.reverse();  }}

distance =: 3
steps =: 7
matches =: 4
substitutes =: 2
deletes =: 0
inserts =: 1

Done: kitten becomes sitting in 3 edits over 7 steps: 4 matches, 2 changes, 0 deletions, 1 insertion, from 42 cells filled.

import type { Tracer } from "../trace";/** The cost model: Levenshtein charges a substitution 1, indel charges 2 (a deletion plus an insertion, what `diff` and LCS measure). */export const EDIT_COSTS = ["levenshtein", "indel"] as const;export type EditCosts = (typeof EDIT_COSTS)[number];/** What one substitution costs under each model; a deletion or an insertion always costs 1. */export const EDIT_SUBSTITUTE_COST: Record<EditCosts, number> = { levenshtein: 1, indel: 2 };/** The longest string either side takes, so the table is at most 9 by 9. */export const EDIT_MAX_LENGTH = 8;/** The four ways a cell is reached: along the diagonal with no cost (match) or the substitution cost, from above (delete a's char), or from the left (insert b's char). */export const EDIT_OPS = ["match", "substitute", "delete", "insert"] as const;export type EditOp = (typeof EDIT_OPS)[number];export interface EditDistanceOptions { /** Default levenshtein. */ costs?: EditCosts;}/** One edit of the script that turns `a` into `b`, read off the table from the corner back to the origin and listed forward. */export interface EditStep { op: EditOp; /** The character of `a` the step consumes, or "" for an insert. */ a: string; /** The character of `b` the step produces, or "" for a delete. */ b: string; /** The cell the step leaves: `a`'s first i characters against `b`'s first j. */ i: number; j: number;}export interface EditDistanceReport { a: string; b: string; /** The cheapest cost of turning `a` into `b` under the cost model. */ distance: number; /** The edits in forward order; replaying them on `a` gives `b`. */ steps: EditStep[]; /** Cells filled by the recurrence, the border row and column not counted. */ cells: number; matches: number; substitutes: number; deletes: number; inserts: number;}interface Candidates { diag: number; fromDiagonal: number; up: number; fromAbove: number; left: number; fromLeft: number; best: number; cheapest: number; op: EditOp;}/** * The edit distance between two strings: the fewest single-character * edits (delete, insert, substitute) that turn one into the other, * as Levenshtein defined it in 1965 and Wagner and Fischer tabulated * it in 1974. The subproblems are prefix pairs: cell (i, j) holds the * distance from `a`'s first i characters to `b`'s first j, and it * depends only on its three neighbours. The diagonal neighbour plus * the cost of lining up a[i-1] with b[j-1] (0 when they match), the * cell above plus one (delete a's character), the cell to the left * plus one (insert b's character): the cheapest of the three wins. * The border is the base case, a prefix against nothing costs its * length. Filling the table row by row answers (m, n) in the corner, * and walking back from the corner along the winning neighbours reads * the edit script out. Under the indel cost model a substitution * costs as much as a delete plus an insert, so the script never * substitutes and the distance is m + n minus twice the longest * common subsequence. * * Ties are broken in favour of a match, then a delete, then an insert; * a substitute is chosen only when it is strictly cheapest, which is * what keeps the indel script free of substitutions. * * Time: O(m * n). Space: O(m * n) for the table the backtrack reads. */export class EditDistance { readonly costs: EditCosts; readonly substituteCost: number; private a = ""; private b = ""; /** Row i, column j: the distance between the first i characters of `a` and the first j of `b`. */ private cells: number[][] = []; constructor(options: EditDistanceOptions = {}, private readonly tracer?: Tracer) { const costs = options.costs ?? "levenshtein"; if (!EDIT_COSTS.includes(costs)) throw new RangeError(`costs must be one of ${EDIT_COSTS.join(", ")}`); this.costs = costs; this.substituteCost = EDIT_SUBSTITUTE_COST[costs]; } /** The table of the last call: rows 0..m, columns 0..n; empty before the first call. */ get table(): readonly (readonly number[])[] { return this.cells; } /** Fills the table for one pair from scratch, then reads the edits back from the corner. */ distance(a: string, b: string): EditDistanceReport { if (a.length > EDIT_MAX_LENGTH) throw new RangeError(`a must be at most ${EDIT_MAX_LENGTH} characters`); if (b.length > EDIT_MAX_LENGTH) throw new RangeError(`b must be at most ${EDIT_MAX_LENGTH} characters`); this.a = a; this.b = b; const m = a.length; const n = b.length; this.cells = Array.from({ length: m + 1 }, () => Array.from({ length: n + 1 }, () => 0)); this.base(0, 0); for (let j = 1; j <= n; j++) this.base(0, j); for (let i = 1; i <= m; i++) { this.base(i, 0); for (let j = 1; j <= n; j++) this.fill(i, j); } const steps = this.backtrack(); const count = (op: EditOp) => steps.filter((step) => step.op === op).length; return { a, b, distance: this.cells[m]![n]!, steps, cells: m * n, matches: count("match"), substitutes: count("substitute"), deletes: count("delete"), inserts: count("insert"), }; } /** The border: a prefix against the empty string costs its length, whether the corner, the top row, or the first column. */ private base(i: number, j: number): void { const value = Math.max(i, j); this.cells[i]![j] = value; // ▸ the border: a prefix against nothing costs its length, one edit per letter this.tracer?.emit("base", { i, j, value }); } /** One inner cell: the cheapest of its three neighbours, written down with the move that won. */ private fill(i: number, j: number): void { const { diag, up, left, best, op } = this.choose(i, j); const { fromDiagonal, fromAbove, fromLeft, cheapest, op } = this.choose(i, j); this.cells[i]![j] = best; this.cells[i]![j] = cheapest; // ▸ one cell: the cheapest of the diagonal plus the match or change cost, above plus one, left plus one this.tracer?.emit("cell", { a: this.a[i - 1]!, b: this.b[j - 1]!, best, diag, i, j, left, op, up }); this.tracer?.emit("cell", { a: this.a[i - 1]!, b: this.b[j - 1]!, cheapest, fromDiagonal, i, j, fromLeft, op, fromAbove }); } /** The recurrence itself: diagonal plus the match or substitution cost, above plus one, left plus one; the same arithmetic serves the fill and the backtrack. */ private choose(i: number, j: number): Candidates { const cost = this.a[i - 1] === this.b[j - 1] ? 0 : this.substituteCost; const diag = this.cells[i - 1]![j - 1]! + cost; const fromDiagonal = this.cells[i - 1]![j - 1]! + cost; const up = this.cells[i - 1]![j]! + 1; const fromAbove = this.cells[i - 1]![j]! + 1; const left = this.cells[i]![j - 1]! + 1; const fromLeft = this.cells[i]![j - 1]! + 1; const best = Math.min(diag, up, left); const cheapest = Math.min(fromDiagonal, fromAbove, fromLeft); let op: EditOp; if (cost === 0 && diag === best) op = "match"; if (cost === 0 && fromDiagonal === cheapest) op = "match"; else if (up === best) op = "delete"; else if (fromAbove === cheapest) op = "delete"; else if (left === best) op = "insert"; else if (fromLeft === cheapest) op = "insert"; else op = "substitute"; return { diag, up, left, best, op }; return { fromDiagonal, fromAbove, fromLeft, cheapest, op }; } /** From the corner back to the origin, one winning neighbour at a time; the border leaves only one way out. */ private backtrack(): EditStep[] { const steps: EditStep[] = []; let i = this.a.length; let j = this.b.length; while (i > 0 || j > 0) { const op: EditOp = i === 0 ? "insert" : j === 0 ? "delete" : this.choose(i, j).op; const consumesA = op !== "insert"; const consumesB = op !== "delete"; const step: EditStep = { op, a: consumesA ? this.a[i - 1]! : "", b: consumesB ? this.b[j - 1]! : "", i, j }; // ▸ from the corner, leave each cell by the neighbour that won it; the moves are the edits this.tracer?.emit("backtrack", { a: step.a, b: step.b, i, j, op, value: this.cells[i]![j]! }); steps.push(step); if (consumesA) i--; if (consumesB) j--; } return steps.reverse(); }}