Continuous Function

NLP & Speech

Edit Distance

Edit distance fills a dynamic-programming table for two sequences: predict one cell, then follow the cheapest insert, delete, or substitute path.

status: reviewimportance: importantdifficulty 3/5math: undergraduateread: 16mlive demo
Back to NLP & Speech

Concept Structure

Edit Distance

01Intuition

Start with the picture, metaphor, or geometric mechanism.

02Math

Make the objects explicit and connect them with notation.

03Code

Mirror the equations with runnable implementation details.

04Interactive Demo

Manipulate the mechanism and watch the idea respond.

0prerequisites
1next concepts
3related links

Learner Contract

What this page should let you do.

You are here becauseEdit distance fills a dynamic-programming table for two sequences: predict one cell, then follow the cheapest insert, delete, or substitute path.

This NLP & Speech concept is the current idea: keep the same invariant visible across Intuition, Math, Code, Interactive Demo.

Before thisNo hard prerequisite

No hard prerequisite is listed; start from the intuition and fill gaps only when the notation demands it.

By the end4/4 sections ready | runnable code expected | live demo

Explain the mechanism, trace the main notation, and test one prediction in the live demo.

Do this firstIntuition

Read the intuition before the notation; the math should name a mechanism you already felt.

Then go nextAutomatic Speech Recognition (planned)

Follow this edge after making one prediction here; the next page should reuse the result, not restart the route.

Test the linkManipulate one control and predict the visible change.

Claim/source review status

Substantive review recorded

2/2 claims have bounded review metadata; still check caveats and source scope.Metadata-derived; review may be AI-assisted. Not a human certification.
Claims2/2 reviewed
Sources3 cited
Codeattached
Demolive
Reviewed2026-07-03
Updatedpage 2026-07-03

Learning item flow

4/4 sections readyAsk about thisResearch room
ConceptEdit DistanceNLP & SpeechEquationEdit Distance equation 1Exact equationCodeEdit Distance runnable code 1Exact runnable codeDemoEdit Distance interactive demoInteractive demoClaimMinimum edit distance defines the least-cost sequence of edit operati...Exact claim checkSourceSpeech and Language Processing, Chapter 2: Regular Expressions, Text...Exact source
ConceptEdit DistanceNLP & Speech
3 sources attachedLocal snapshot ready
concept:nlp-speech/edit-distance
CodenearbyPredictbefore revealRoomitem handoff
01IntuitionStart with the picture, metaphor, or geometric mechanism.02MathMake the objects explicit and connect them with notation.03CodeMirror the equations with runnable implementation details.04Interactive DemoManipulate the mechanism and watch the idea respond.
01

01

Intuition

Build the mental picture first so the rest of the page has something to attach to.

Section prompt

Edit distance asks a very concrete question: how many edits does it take to turn one string into another?

If a learner types sittnig when the intended word is sitting, the strings are close. If an ASR system outputs a sentence, we can compare it with a reference transcript by counting word insertions, deletions, and substitutions. The final number is useful, but the alignment path explains which edits were paid for.

The brute-force search space is huge because many edit sequences can transform the source into the target. Dynamic programming makes the problem inspectable. Instead of searching every full path separately, it asks a smaller question for every prefix pair:

What is the cheapest way to transform the first ii characters of the source into the first jj characters of the target?

Each table cell has only three local ways to arrive:

  • delete the next source character,
  • insert the next target character,
  • substitute or match the two current characters.

The caveat matters. Edit distance measures operation cost, not meaning. cat and car are close by character edits, but cat and feline are semantically closer than their edit distance suggests. Use edit distance when the literal sequence matters; use embeddings, language models, or task-specific scoring when meaning matters.

Sources used: Jurafsky and Martin, Speech and Language Processing, Chapter 2; Stanford CS124 Minimum Edit Distance; MIT OpenCourseWare 6.006 Lecture 21.

02

02

Math

Translate the story into symbols, assumptions, and a derivation you can inspect.

Section prompt
Equation 1D[0,j]=jcins,D[i,0]=icdel.D[0,j]=j c_{\mathrm{ins}}, \qquad D[i,0]=i c_{\mathrm{del}}.Equation 2D[i,j]=min⁡{D[i−1,j]+cdeldelete xi,D[i,j−1]+cinsinsert yj,D[i−1,j−1]+csub(xi,yj)substitute or match.D[i,j]= \min\begin{cases} D[i-1,j] + c_{\mathrm{del}} & \text{delete } x_i,\\ D[i,j-1] + c_{\mathrm{ins}} & \text{insert } y_j,\\ D[i-1,j-1] + c_{\mathrm{sub}}(x_i,y_j) & \text{substitute or match}. \end{cases}

Let the source string be x=x1,…,xnx=x_1,\dots,x_n and the target string be y=y1,…,ymy=y_1,\dots,y_m.

Define D[i,j]D[i,j] as the minimum edit cost to transform the prefix x1:ix_{1:i} into the prefix y1:jy_{1:j}.

The boundary conditions are:

D[0,j]=jcins,D[i,0]=icdel.D[0,j]=j c_{\mathrm{ins}}, \qquad D[i,0]=i c_{\mathrm{del}}.

With unit insertion and deletion cost, turning the empty string into the first jj target characters requires jj insertions, and turning the first ii source characters into the empty string requires ii deletions.

For i>0i>0 and j>0j>0, the recurrence is:

D[i,j]=min⁡{D[i−1,j]+cdeldelete xi,D[i,j−1]+cinsinsert yj,D[i−1,j−1]+csub(xi,yj)substitute or match.D[i,j]= \min\begin{cases} D[i-1,j] + c_{\mathrm{del}} & \text{delete } x_i,\\ D[i,j-1] + c_{\mathrm{ins}} & \text{insert } y_j,\\ D[i-1,j-1] + c_{\mathrm{sub}}(x_i,y_j) & \text{substitute or match}. \end{cases}

Here csub(xi,yj)=0c_{\mathrm{sub}}(x_i,y_j)=0 when xi=yjx_i=y_j and 11 for a unit-cost substitution.

The final distance is D[n,m]D[n,m]. If we also store which candidate achieved the minimum in each cell, we can backtrace from (n,m)(n,m) to (0,0)(0,0) and recover an alignment.

For kitten -> sitting with unit costs, one optimal alignment is:

k i t t e n -
s i t t i n g
S M M M S M I

The operation sequence has cost 33: substitute k -> s, substitute e -> i, and insert g.

03

03

Code

Keep the implementation aligned with the notation so the algorithm is legible.

Section prompt
Runnable code 1source = "kitten" target = "sitting" n, m = len(source), len(target) D = [[0] * (m + 1) for _...python

This small script builds the DP table and backtraces one optimal alignment.

source = "kitten"
target = "sitting"

n, m = len(source), len(target)
D = [[0] * (m + 1) for _ in range(n + 1)]
back = [[None] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    D[i][0] = i
    back[i][0] = "delete"
for j in range(1, m + 1):
    D[0][j] = j
    back[0][j] = "insert"

for i in range(1, n + 1):
    for j in range(1, m + 1):
        sub_cost = 0 if source[i - 1] == target[j - 1] else 1
        choices = [
            (D[i - 1][j] + 1, "delete"),
            (D[i][j - 1] + 1, "insert"),
            (D[i - 1][j - 1] + sub_cost, "match" if sub_cost == 0 else "substitute"),
        ]
        D[i][j], back[i][j] = min(choices, key=lambda item: item[0])

i, j = n, m
ops = []
while i or j:
    op = back[i][j]
    ops.append((op, source[i - 1] if i else "-", target[j - 1] if j else "-"))
    if op == "delete":
        i -= 1
    elif op == "insert":
        j -= 1
    else:
        i -= 1
        j -= 1

print("distance:", D[n][m])
print("operations:", list(reversed(ops)))

The table has (n+1)(m+1)(n+1)(m+1) cells. Each cell checks three candidates, so the simple algorithm runs in O(nm)O(nm) time and uses O(nm)O(nm) memory when we keep the full backtrace table.

04

04

Interactive Demo

Use direct manipulation to connect the explanation to a moving system.

Section prompt

Prediction check: inspect the source and target tapes, then predict which operation sets the highlighted table cell and what final distance the bottom-right cell will show before revealing the completed table and alignment.

The lab hides the highlighted cell value, the final distance, the backtrace path, the operation list, and the alignment caveat until you commit. The goal is to connect each table entry to a local edit choice instead of treating dynamic programming as a memorized grid.

Live Concept Demo

Explore Edit Distance

The stage is code-native and interactive. Use it to test the explanation against the mechanism.

difficulty 3/5undergraduatecode-aligned
Demo Prediction Checkpoint

Manipulate one control and predict the visible change.

Commit to what Edit Distance should make visible before reading the result.

After The First Pass

Turn the concept into an inspected object.

Once the invariant is visible in the intuition, math, code, and demo, use these panels to inspect the mechanism visually, check source support, practice the idea, and attach a grounded research question.

Mechanism Storyboard

See the idea move before the page explains it

Edit distance fills a dynamic-programming table for two sequences: predict one cell, then follow the cheapest insert, delete, or substitute path.

Prediction open01 / Intuition
Prediction lens

Start with the picture, metaphor, or geometric mechanism.

Commit first

Before reading further, choose the kind of change Edit Distance should make visible.

Visual Inquiry

Make the image answer a mathematical question

Edit distance fills a dynamic-programming table for two sequences: predict one cell, then follow the cheapest insert, delete, or substitute path.

4/4 stages readyLive demo connected
Prediction

Which visible object should carry the first intuition?

Commit first

Pick the cue that should make Edit Distance easier to reason about before the page gives the answer.

Source Grounding

Canonical references for the mechanism on this page.

book · 2026Speech and Language Processing, Chapter 2: Regular Expressions, Text Normalization, Edit DistanceJurafsky and Martin

Book source for minimum edit distance, insert/delete/substitute operations, dynamic programming, and NLP uses such as spelling correction.

Open source
course-notes · 2023Stanford CS124: Minimum Edit DistanceStanford CS124

Course-note source for edit distance as a least-cost path through edit operations and for table/backtrace intuition.

Open source
course-notes · 2011MIT 6.006 Lecture 21: Dynamic Programming IIIMIT OpenCourseWare

Algorithms source for string subproblems, edit distance, and the dynamic-programming recurrence pattern.

Open source

Claim Review

Edit distance fills a dynamic-programming table for two sequences: predict one cell, then follow the cheapest insert, delete, or substitute path.

Status2 substantive reviews recorded

Claims without a substantive review badge still need exact source-support review.

Sources3 references

jurafsky-martin-slp3-edit-distance, stanford-cs124-minimum-edit-distance, mit-6006-string-dp

Local checks4 local checks

Use equations, runnable code, and demos to check whether the source support is operational.

Substantively reviewedMinimum edit distance defines the least-cost sequence of edit operations, typically insertions, deletions, and substitutions, needed to transform one string or token sequence into another.Claim metadata: source checked

SLP3 and Stanford CS124 support the operation-set framing and the least-cost transformation definition used by the page and demo.

Sources: Speech and Language Processing, Chapter 2: Regular Expressions, Text Normalization, Edit Distance, Stanford CS124: Minimum Edit DistanceThe page uses unit insertion, deletion, and substitution costs. Real spell correction, ASR, OCR, biosequence alignment, and task-specific metrics can use weighted costs, token-level costs, transpositions, phonetic costs, or domain-specific scoring.A bounded review summary is present; still check caveats and exact reference scope.

Checked SLP3 Chapter 2 and Stanford CS124 minimum-edit-distance slides for the edit-operation definition and least-cost path framing.

Reviewer: codex-local-source-review; reviewed 2026-07-03
source-span-jurafsky-martin-slp3-edit-distancesource-span-stanford-cs124-minimum-edit-distanceEquation 1Runnable code 1Interactive demo
Substantively reviewedThe standard dynamic-programming algorithm fills a table D[i,j] for prefix pairs, using neighboring cells for deletion, insertion, and substitution or match decisions; the bottom-right cell gives the minimum cost and backpointers recover an alignment.Claim metadata: source checked

SLP3 and Stanford CS124 support the prefix-table and backtrace view for minimum edit distance; MIT 6.006 supports the broader string-subproblem dynamic-programming framing.

Sources: Speech and Language Processing, Chapter 2: Regular Expressions, Text Normalization, Edit Distance, Stanford CS124: Minimum Edit Distance, MIT 6.006 Lecture 21: Dynamic Programming IIIThe demo shows one deterministic Levenshtein table for a tiny example. It does not cover affine gaps, local alignment, transposition distance, noisy-channel spell correction, or weighted ASR word-error-rate scoring.A bounded review summary is present; still check caveats and exact reference scope.

Checked SLP3, Stanford CS124, and MIT 6.006 for prefix subproblems, recurrence choices, table fill, and backtrace scope.

Reviewer: codex-local-source-review; reviewed 2026-07-03
source-span-jurafsky-martin-slp3-edit-distancesource-span-stanford-cs124-minimum-edit-distancesource-span-mit-6006-string-dpEquation 2Runnable code 1Interactive demo

Source support candidates

book 2026Speech and Language Processing, Chapter 2: Regular Expressions, Text Normalization, Edit Distance

Book source for minimum edit distance, insert/delete/substitute operations, dynamic programming, and NLP uses such as spelling correction.

course-notes 2023Stanford CS124: Minimum Edit Distance

Course-note source for edit distance as a least-cost path through edit operations and for table/backtrace intuition.

course-notes 2011MIT 6.006 Lecture 21: Dynamic Programming III

Algorithms source for string subproblems, edit distance, and the dynamic-programming recurrence pattern.

Mechanism checks

Equation 1
D[0,j]=jcins,D[i,0]=icdel.D[0,j]=j c_{\mathrm{ins}}, \qquad D[i,0]=i c_{\mathrm{del}}.
Equation 2
D[i,j]=min⁡{D[i−1,j]+cdeldelete xi,D[i,j−1]+cinsinsert yj,D[i−1,j−1]+csub(xi,yj)substitute or match.D[i,j]= \min\begin{cases} D[i-1,j] + c_{\mathrm{del}} & \text{delete } x_i,\\ D[i,j-1] + c_{\mathrm{ins}} & \text{insert } y_j,\\ D[i-1,j-1] + c_{\mathrm{sub}}(x_i,y_j) & \text{substitute or match}. \end{cases}
Runnable code 1source = "kitten" target = "sitting" n, m = len(source), len(target) D = [[0] * (m + 1) for _...Demo stateLive mechanism probe

Practice Loop

Try the idea before it explains itself

Edit distance fills a dynamic-programming table for two sequences: predict one cell, then follow the cheapest insert, delete, or substitute path.

Readiness0/3 checks ready
Predict

Before touching the demo, predict one visible change that should happen in Edit Distance.

Hint 1

Reveal when your model needs a nudge.

Hint 2

Reveal when your model needs a nudge.

Hint 3

Reveal when your model needs a nudge.

Grounded research drawerClose
ConceptEdit DistanceNLP & Speech
Runnable code comparisonEdit Distance runnable code 1source = "kitten" target = "sitting" n, m = len(source), len(target) D = [[0] * (m + 1) for _...Prediction before revealEdit Distance interactive demoManipulate one control and predict the visible change.
Grounded room questionWhat is the smallest example that makes Edit Distance click without losing the math?Local snapshot ready

Research Room

Attach the question to a claim, equation, code, or demo

Pick the concept, equation, source, runnable code, claim, misconception, or demo state before asking for help. The handoff keeps that page item in context.
Next local actionNo local draft saved yet

Open the draft below to save one note and next action in this browser.

conceptNLP & Speech

Edit Distance

Attached question

What is the smallest example that makes Edit Distance click without losing the math?

Local action draftNo local draft saved yetExpand only when ready to capture one local next action
Local action draft

This draft stays in this browser, attached to the selected learning item.

No local draft saved.
Evidence to inspect
  • References to inspect: attached references on this page.
  • Definition, prerequisite, and contrast concept links
  • The equation or runnable code that makes the concept operational
  • One demo state that shows the invariant instead of a slogan
What would resolve this
  • The learner can state the mechanism in their own words
  • The learner can name the prerequisite that would repair confusion
  • The learner can predict how the mechanism changes under one perturbation
Grounded AI handoff

I am working in Continuous Function's research reading room. Object: concept - Edit Distance Selected item key: recorded for copy. Context: NLP & Speech Page anchor: recorded for copy. Open question: What is the smallest example that makes Edit Distance click without losing the math? Evidence to inspect: - References to inspect: attached references on this page. - Definition, prerequisite, and contrast concept links - The equation or runnable code that makes the concept operational - One demo state that shows the invariant instead of a slogan What would resolve this: - The learner can state the mechanism in their own words - The learner can name the prerequisite that would repair confusion - The learner can predict how the mechanism changes under one perturbation Answer as a careful research tutor: stay source-grounded, separate verified evidence from assumptions, name the relevant math objects, and end with one next action.

View it in context
concept/concept-notebook/nlp-speech/edit-distance concept:nlp-speech/edit-distance