Edit Distance: From Memorization to Derivation

Dynamic programming is usually taught as a list of solutions to memorise. I want to do the opposite. Over the next twenty minutes we are going to derive one, from a problem statement, with nothing remembered at all. The problem is edit distance, and what falls out of it is the method itself. So, two words. The source word is s u n, sun. The target word is s a n d, sand. You are allowed to change the source one character at a time until it reads like the target, and the question is how few changes that takes. Three moves are allowed, and only three. You can insert a character anywhere in the word. You can delete one. Or you can substitute one character for another, which is the only one of the three that leaves the length alone. Here is one way to get from one to the other. The s at the front already matches, so leave it alone. The u has to become an a, and that is one substitution. The n already matches too. And then there is a d hanging off the end of the target with nothing above it, so insert it. Look at the shape of that. Four columns, and the source only has three characters in it. That is exactly what an insertion is: a column with a target character in it and nothing standing above. Two edits in total, because two of the four columns cost nothing. Two is not obviously the smallest, though. Written out, that route is sun to san to sand. And here is a clumsier one: delete the u to get s n, insert an a, insert a d. Three edits, same destination. The edit distance is the minimum over every possible route, and there are a great many routes. Which means we are not going to enumerate them. We need to break the problem into smaller copies of itself, and that is the move that starts every dynamic program there is. Not a table. A sentence. Here is that sentence, and it is worth saying slowly. D of i and j is the edit distance between the first i characters of the source word and the first j characters of the target word. That is the entire definition. Prefixes, in other words. Not arbitrary pieces of the words, not suffixes, not substrings. Just: how much of each word have I dealt with so far? Sun has three characters and sand has four, so the answer to the original question is one single value. And choosing prefixes is a real choice, by the way. It is the choice that does all of the work here, and if you pick the wrong subproblem the rule will not close up on itself and you will have to come back and pick another one. Expect that to happen. Now suppose you code that definition up recursively, the obvious way. To compute D of three and four you try all three moves, and each one hands you back a smaller pair of prefixes to solve. Deleting gives you D of two, four. Inserting gives D of three, three. Substituting gives D of two, three. Three calls, every one of them strictly smaller than the thing we started with. Expand one more level and each of those three splits into three again. Nine calls, and we have only gone two deep. Now look carefully at what is actually written down there. D of two, three is here. And here. And again here. Three copies of one subproblem, and each copy is about to go off and compute the same number from scratch, knowing nothing whatsoever about the other two. That is the whole disease, and it is worth being precise about it. The recursion is correct. It is simply doing the same work over and over because it has no memory of what it has already worked out. Right at the end we will count exactly how much. So we have a subproblem. What we do not have yet is the rule that ties one subproblem to the smaller ones, and that rule comes out of a single question about the last character.

The rule always comes out of the same question, whatever the problem happens to be. Look at the very end of both prefixes, and ask what the last step was. These four squares are a corner of the table we are about to build. The one at the bottom right is the cell we want, D of i and j. The other three are all strictly smaller subproblems: one row up, one column to the left, and one of each. Suppose the last edit deleted the source character A sub i. Then that character is gone, it was matched against nothing at all, and what is left over is the first i minus one characters of the source against the whole first j of the target. That is the cell directly above, plus one for the deletion itself. Suppose instead that the last edit inserted the target character B sub j. Now the source is untouched, and it is the target that has one fewer character left to account for. That is the cell immediately to the left, plus one for the insertion. And the third possibility is that A sub i and B sub j were simply lined up against each other. Both prefixes lose a character, so we arrive from the diagonal. What that step costs depends entirely on the two characters. That case is worth pausing on, because it is doing two jobs at once. When the two characters already agree, it is a match and it costs nothing at all. When they disagree, it is a substitution and it costs one. Same arrow, same neighbour, two different prices. Make that concrete. Take i equals two and j equals two, so the prefixes are s u and s a. The last characters are u and a. They are different, so that diagonal step costs one, sitting on top of whatever the distance between s and s turned out to be. Call that extra cost c. Zero when the two characters agree, one when they do not. That single letter is the only place the actual words enter the arithmetic. Everything else in the rule is pure bookkeeping. Three cases, three neighbours, and no fourth possibility anywhere. Any edit sequence at all has to end in one of those three, so the cheapest sequence ends in whichever of the three is cheapest. So there is the recurrence, and notice that we did not guess it and we did not remember it. It is nothing more than the minimum over the three ways the last step could have gone. Read it as a picture rather than as algebra. One plus the cell above. One plus the cell to the left. Or c plus the cell on the diagonal. Take whichever of those three is smallest, and that is your answer. And here is the cost, spelled out properly. c is zero if the character at position i and the character at position j are the same, and one if they are not. There is a hole in this, though. Every one of those three cases points at a smaller cell, which is perfectly fine right up until the moment there is no smaller cell to point at. The recurrence cannot start itself. So we also need the cases that are true with no recursion at all. Those turn out to be the easy part, because a prefix of length zero is just the empty word. And that is where the table finally comes in.

Here is the table. Four rows, because sun has three characters and we need a row for zero characters as well. Five columns, for the same reason, with sand. Every single square in it is one subproblem. The square in row i and column j is going to hold D of i and j, and the one we actually want is down there in the bottom right corner. Start with row zero. That row is the source prefix of length zero, which is the empty word. Turning the empty word into the first j characters of sand costs exactly j insertions, one per character, so row zero simply counts up. Zero, one, two, three, four. Column zero is the mirror image of that. Turning the first i characters of sun into the empty word costs i deletions, so it counts down the side. One, two, three. Those eight squares are true by definition rather than by any rule. And look at the corner one: no characters against no characters, nothing to do, zero. Everything else comes from the rule we derived, and the three ways in keep the three colours from before: red from above, blue from the left, yellow from the diagonal. Twelve squares left, and each one is the smallest of three numbers already sitting on the page. Take the first empty one, row one, column one. Row one means the source prefix is s. Column one means the target prefix is s. Three arrows point into that square, one from each neighbour, and the square holds the smallest of what those three arrows offer. From above, the neighbour holds one, and a deletion costs one more, so two. From the left, one again, plus one for an insertion, so two again. From the diagonal, zero, and both characters here are s, so c is zero and the diagonal asks for nothing extra. Zero wins, so the square is zero, and that is exactly right. Turning s into s costs nothing at all. Now slide the arrows one column to the right. Row one is still just s. Column two is s a. From above, three. From the left, one. From the diagonal, one, and this time the characters are s and a, which differ, so add one and you get two. The smallest is one. One insertion. Build s a out of a single s by adding an a on the end. The table just derived that on its own, and it will keep doing it. The rest of that row goes the same way. Column three, two. Column four, three. Row one now reads one, zero, one, two, three, and each of those is the cost of building a longer and longer prefix of sand out of one s. Row two now, so the source prefix is s u. Back to column one, where the target is s. From above, zero plus one is one. From the left, two plus one is three. From the diagonal, one plus one is two, because u and s are different. One wins. And notice which arrow it came from. The one from above, the red one, which is a deletion. Turning s u into s means throwing the u away, and the table found that by itself. This next one is the interesting square. Row two, column two: s u against s a. From above, two. From the left, two. From the diagonal, zero plus one, because u and a differ. One, from the diagonal, and that diagonal step is exactly the substitution we spotted by eye at the very start. Finish the row. Column three gives two. Column four gives three. Nothing matches anywhere along there, so every step is costing something. Last row, so the source is the whole word, s u n. Column one gives two. Column two gives two as well. Column three is worth slowing down for. Source s u n, target s a n. The last characters are both n, so c is zero, and the diagonal offers one plus nothing. Above offers three, the left offers three, the diagonal offers one. The number drops. That is a free match paying for itself. And now the very last square. Source s u n, target s a n d. The last characters are n and d, which differ. Above gives four. The diagonal gives three. And from the left, one plus one is two. Two. That is the edit distance between sun and sand, and every one of those twenty numbers was worked out exactly once, from numbers already sitting above it and to its left. Now the number on its own is not really the interesting part. The table also knows which moves it used to get there, and we can read them back out by walking the winning arrows backwards from the corner. Start at the bottom right. The two there came from the left neighbour, which held one. A step from the left is an insertion, so the last edit was inserting the d. From that square, the one came from the diagonal, and the characters there were n and n, equal, so the step cost nothing. A free diagonal step is a match. Keep the n exactly as it is. From there, the one came from the diagonal again, but this time u and a were different, so the step cost one. That is a substitution. And the last diagonal step is another free match, s against s, and it lands us back in the empty corner. Four steps, one for each column of the alignment we drew at the very beginning. Read that path forwards and you have the script. Match the s at the front. Substitute the u with an a. Match the n in the middle. Insert a d at the end. Two of those four steps are free, and the two that cost anything add up to two, which is the number sitting in the corner. So the table did not merely measure the distance. It constructed the edits. So what did all of that buy us? Twenty squares. Twenty subproblems, each one solved exactly once and then written down where the others can see it. The plain recursion from earlier, run to completion on these same two short words, makes a hundred and ninety three calls. Same answer, nearly ten times the work, and the extra nine tenths of it is the same handful of subproblems being recomputed. And it gets worse very fast. Take kitten and sitting, which is the standard example. The table has fifty six squares in it. The recursion makes nearly thirty thousand calls. The table is m plus one times n plus one, always, no matter what the words are. The recursion is exponential in the length of the words. That gap is the whole of what dynamic programming buys you, and it is bought with a grid you could draw on a napkin. And notice that nothing in that argument was about spelling. Strip the two words out of it and what is left is a procedure. Name the subproblem in one sentence. If you cannot say it in one sentence you do not have it yet, and no amount of staring at a table will rescue you. Ask what the last decision could have been. Not the first one, the last one, because the last one is what leaves a smaller version of the same problem behind it. Then let each answer point at that smaller version. Write down the cases the rule cannot reach, which are almost always the empty ones. And then fill the thing in in an order where everything a square needs is already there. For us that was left to right and top to bottom, because every arrow pointed up or left. Five steps, and not one of them mentioned edit distance. The next time you meet one of these, do not go looking for the solution you memorised. Go and find the sentence.