Two prefixes index this table, one per string, and each cell reads exactly three neighbours. The number it produces is checked against a recursion with no table; the script it produces is checked by being performed, one operation at a time, on the word it claims to transform — refusing if an operation names a character that is not there. A script of the right length and the wrong content cannot survive that.
Core ideas
The hard idea is the last one: a reconstruction can be checked by executing it, which is a stronger check than comparing two numbers.
D(i, j) is the cheapest way to turn the first i characters of the first word into the first j of the second. The last operation is a delete, an insert, or a keep-or-substitute, and those three are exactly the cell above, the cell to the left, and the cell diagonally back. The base row and column are j and i — turning nothing into a prefix costs one insert per character.
Walking the recorded pointers from the bottom-right corner to the origin gives a sequence of operations. On kitten and sitting there are seven of them and the distance is three, because four are keeps and a keep costs nothing. Confusing the two counts is the commonest reading error on this page, and the panel prints both figures in separate rows for that reason.
Every operation names the character it acts on: delete the t at position 3, keep the n, substitute e for i. Carrying the script out means walking the first word and refusing as soon as an operation names a character that is not where it says. A wrong reconstruction of the right length passes a cost check and fails this one, because the characters are what it gets wrong.
The material
The recurrence and its proof, the walk back, why performing beats costing, and the two counts that diverge.
The edit distance between strings a and b is the fewest single-character operations — insert, delete, substitute — that turn a into b. Each costs one; keeping a character costs nothing and is not an operation in the count, though it is a step in the script.
With D(i, 0) = i and D(0, j) = j, for i, j ≥ 1: D(i, j) = min( D(i−1, j) + 1, D(i, j−1) + 1, D(i−1, j−1) + c ), where c is 0 if the i-th character of a equals the j-th of b and 1 otherwise.
Consider a cheapest sequence of operations turning a[1..i] into b[1..j] and look at what happens to the last character of each. Either a[i] is deleted, in which case the rest is a cheapest way of turning a[1..i−1] into b[1..j], costing D(i−1, j) + 1; or b[j] is inserted, giving D(i, j−1) + 1; or a[i] is aligned with b[j], kept if they are equal and substituted otherwise, giving D(i−1, j−1) + c.
In each case the remaining sub-sequence must itself be cheapest, or substituting a cheaper one would beat the original — optimal substructure again, discharged by the same substitution argument as every other page on this course. No other last step is possible, so the minimum over three cases is the distance.
□
Filling this table in row-major order is correct, and it is worth pausing on why, given “The Fill Order Is Part of the Algorithm”. The three cells a cell reads are (i−1, j), (i, j−1) and (i−1, j−1): one row up, one column left, and both. Row-major writes every cell of row i−1 before any of row i, and within row i it writes column j−1 before column j. All three reads are therefore already written, and the count of reads landing on unwritten cells is zero. The fill order is not always wrong; it is always something to check.
The table is 7 by 8, fills 56 cells and makes 126 reads, and its corner is 3. A recursion with no table at all reaches 3 after 29 737 calls. The script the pointers spell out is: substitute k for s, keep i, keep t, keep t, substitute e for i, keep n, insert g. Performing that on kitten, character by character, produces sitting, and the panel compares that string with the second word rather than trusting the walk.
Suppose the walk back followed one wrong pointer and returned a script that still had three paid operations. Costing it would give 3, matching the table, and the check would pass. Performing it would not: a delete that names the wrong character, or a keep whose character is not where the script says, stops the execution and the panel reports that the script could not be performed. The stronger check is available because the object here is a program, and a program can be run.
This generalises past strings. Whenever a reconstruction is a sequence of steps rather than a set, executing it against the input is strictly more informative than re-costing it, and usually no harder to write. The knapsack's set could only be re-weighed; this script can be run.
The measured figures are 56 cells against 29 737 calls on two words of six and seven letters. The proved bounds are Θ(mn) for the table and, for the memo-free recursion, at most 3^(m+n) calls because each call makes three and the arguments shrink by at least one in total. For kitten and sitting that upper bound is 3^13, which is 1 594 323 — true, and roughly fifty times the measured 29 737.
That gap is worth naming rather than smoothing over. The bound is an over-count because many branches hit a base case early and because the three recursive calls do not all reduce the same amount. A measurement cannot repair a loose bound; it can only tell you that on this input the truth is well below it. Change the pair to sunday and saturday and the measured count is 60 121 against a bound of 3^14, so the ratio moved without either number being wrong.
One more count that does not mean what it looks like: the panel reports seven operations in the script and a distance of three. Four of the seven are keeps. A reader who quotes the script's length as the distance has reported the length of a path instead of the cost of one, and on dog to dogma the two numbers are five and two.
Interactive
The table checked against a recursion, and the script checked by performing it
Method
Four steps, and the last one is the one that distinguishes this page from the two before it.
D(i, 0) = i and D(0, j) = j, because turning a prefix into nothing is one delete per character. Getting the base row wrong is the commonest way to build a table that is off by a constant everywhere and looks fine in the middle.
Three of them here, and they map onto three neighbours. If you find yourself with four cases or with a case that does not reduce both indices or one, the state is not two prefixes and the table will not close.
Row-major is correct here and the count of reads landing on unwritten cells is zero. Checking costs one glance at the painting and it is the difference between knowing and assuming, which the matrix chain has already shown is not a small difference.
A step that says only substitute is not checkable. A step that says substitute e for i at position 5 can be performed, and performing it is what turns the reconstruction from a claim into a demonstration.
Run it on the first word, refusing on the first operation whose character is not where it says, and compare the output with the second word. Report the distance and the script length separately; they are different numbers.
Rows are prefixes of kitten, columns are prefixes of sitting. The top row and left column are the costs of turning a prefix into nothing and nothing into a prefix.
Each paid operation moves the walk diagonally or sideways and each keep moves it diagonally for free. The four keeps are why the script is longer than the distance, and they are also why the alignment is readable: itt and n survive intact from one word to the other, and the script says so rather than reporting three anonymous edits.
The execution is the check. It walks kitten from the left with a cursor, and every operation but insert has to find its named character under that cursor. Swap two operations in the script and the execution stops; drop one and the cursor finishes short of the end of the word, which the panel also refuses. Only a script that is right about every character survives.
For a faded rehearsal, change the words to abc and xyz before running it. The supplied first move: no character of one appears in the other, so no keep is possible and no insert or delete can help, which fixes the distance at 3 — the largest it can be when the lengths match. Predict the script's length as well as its cost, and check both.
You should be able to write the three-case recurrence with its base row and column, confirm that row-major respects the reads by counting, walk the pointers back into operations that name their characters, and separate the script's length from its cost.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.