Tri's external memory

Lesson 6 Edit Distance

3 min read

Problem

Given two strings:

A = CAT
B = CUT

Find the minimum number of operations required to convert:

A

into:

B

Allowed operations:

Insert
Delete
Replace

Each operation has cost:

1

Example:

CAT
↓
CUT

Replace:

A -> U

Cost:

1

Answer:

1

State Design

Define:

edit(i,j)

Meaning:

Minimum cost to convert:
 
A[i..end]
 
into
 
B[j..end]

Example:

A = CAT
B = CUT
edit(1,1)

means:

Convert:
 
"AT"
 
into
 
"UT"

with minimum cost.

DP State

dp[i][j]

stores:

Minimum cost to convert:
 
A[i..]
 
into
 
B[j..]

Notice:

dp[i][j]

is simply:

edit(i,j)

written down in a table.

Match Case

If:

A[i] == B[j]

Example:

T
T

No operation is needed.

Therefore:

edit(i,j)
=
edit(i+1,j+1)

or:

dp[i][j]
=
dp[i+1][j+1]

No additional cost.

Mismatch Case

Example:

A
U

Three choices exist.

Replace

Replace:

A -> U

Cost:

1 + edit(i+1,j+1)

Delete

Delete:

A

Cost:

1 + edit(i+1,j)

Insert

Insert:

U

before A.

Cost:

1 + edit(i,j+1)

Choose the cheapest:

edit(i,j)
=
1 + min(
        edit(i+1,j+1),
        edit(i+1,j),
        edit(i,j+1)
    )

Recurrence

Match

if A[i] == B[j]
 
dp[i][j]
=
dp[i+1][j+1]

Mismatch

if A[i] != B[j]
 
dp[i][j]
=
1 + min(
        dp[i+1][j+1],   // replace
        dp[i+1][j],     // delete
        dp[i][j+1]      // insert
    )

Base Cases

Source String Exhausted

Suppose:

A = ""
B = "ABC"

Need:

3 inserts

Therefore:

edit(end, j)
=
remaining characters in B

Target String Exhausted

Suppose:

A = "ABC"
B = ""

Need:

3 deletes

Therefore:

edit(i, end)
=
remaining characters in A

Example

edit(1,1)
 
"AT"
→
"UT"

Mismatch:

A != U

Replace

AT
→
UT

Cost:

1

Delete

AT
→
T
→
UT

Cost:

2

Insert

AT
→
UAT
→
UT

Cost:

2

Result:

edit(1,1)
=
1

Relationship to LCS

State:

lcs(i,j)

and

edit(i,j)

share the same state space:

(i,j)

representing positions in two strings.

LCS

Goal:

maximize matches

Match:

1 + diagonal

Mismatch:

max(
    down,
    right
)

Edit Distance

Goal:

minimize operations

Match:

0 + diagonal

Mismatch:

1 + min(
        diagonal,
        down,
        right
    )

Geometry

Like LCS, each state depends on:

right
down
diagonal

Visualized as:

          j
      +---+---+
i     | * | R |
      +---+---+
i+1   | D | X |
      +---+---+

Where:

R = dp[i][j+1]
D = dp[i+1][j]
X = dp[i+1][j+1]

Important Realization

A DP cell is not a number.

It represents a subproblem.

Example:

dp[1][1]

is not:

row 1 column 1

It means:

Convert:
 
"AT"
 
into
 
"UT"

Every cell in the table is a specific problem instance.

The table merely stores the answers.

Personal Observation

A major DP milestone is realizing:

dp[i][j]

is not the state.

The state is:

(i,j)

The DP table is only storage.

The true DP design is:

State
Transition
Base Cases

The table is simply a cache of solved subproblems.

Connection to Earlier Lessons

Fibonacci
    state = n
 
House Robber
    state = i
 
Knapsack
    state = (item, capacity)
 
Coin Change
    state = amount
 
LCS
    state = (i, j)
 
Edit Distance
    state = (i, j)

The state space can stay the same while the optimization objective changes.

This is one of the deepest DP insights learned so far.

Graph View

Backlinks