Dynamic programming on real problems: diffs and edit distance
Dynamic programming explained with the problems it solves in real tools: the longest common subsequence behind diff, edit distance behind 'did you mean', and how to keep memory down.
Dynamic programming (DP) sounds academic, but it's behind tools you use daily: git diff, spell
checkers and "did you mean". The idea: the answer for the whole input is built from answers for
smaller prefixes, stored in a table.
The idea
Three steps, every time:
- Define the table. What does
T[i][j]mean, in words? (For example: "the answer for the firstiitems of A and the firstjitems of B".) - Write the rule. How is
T[i][j]computed from entries with smalleriorj? - Fill it in order so each entry's inputs are already there, starting from the empty-prefix row and column.
Step 1 is where the thinking happens. If you can say what one cell means, the rest follows.
Longest common subsequence
Two files, as lists of lines A (length n) and B (length m). L[i][j] = length of the longest
common subsequence of the first i lines of A and the first j lines of B:
L[0][j] = 0, L[i][0] = 0 # an empty prefix has nothing in common
if A[i-1] == B[j-1]: L[i][j] = L[i-1][j-1] + 1
else: L[i][j] = max(L[i-1][j], L[i][j-1])L[n][m] is the number of lines that stay unchanged. Everything else is a deletion from A or an
insertion from B.
Walking back to get the answer
The table gives the length; the edit script comes from walking back from (n, m) to (0, 0):
while i > 0 or j > 0:
if i > 0 and j > 0 and A[i-1] == B[j-1]: emit "keep A[i-1]"; i--, j--
elif j > 0 and (i == 0 or L[i][j-1] >= L[i-1][j]): emit "insert B[j-1]"; j--
else: emit "delete A[i-1]"; i--
reverse the emitted listWhen both directions are equally good, the tie-break decides which of several minimal diffs you get. Tests expect one specific diff, so pick the rule the ticket describes and apply it consistently. Build it in a diff engine for Mergebay.
Edit distance
The Levenshtein distance between two words is the fewest single-character insertions, deletions
and substitutions that turn one into the other. D[i][j] = distance between the first i letters
of a and the first j of b:
D[i][0] = i, D[0][j] = j
D[i][j] = min( D[i-1][j] + 1, # delete a[i-1]
D[i][j-1] + 1, # insert b[j-1]
D[i-1][j-1] + (a[i-1] == b[j-1] ? 0 : 1) ) # substitute or keepdistance("kitten", "sitting") is 3.
One row at a time
Each row of the table only needs the row above it. Keep two rows instead of the whole table and memory drops from O(n·m) to O(m).
This is also how fuzzy search works in a trie: walking down from the root adds one letter to the candidate word, which is exactly one new row of the edit-distance table. Each child gets its own row computed from its parent's, and if the smallest value in a row is already above the allowed distance, no word below that node can match, so you skip the whole branch. See search suggestions for Findly.
Cost and limits
An n × m table costs O(n·m) time. For two 10,000-line files that's 100 million cells: fine for time, but a full table of 4-byte integers is 400 MB. Real diff tools first strip the common prefix and suffix (often most of the file), and use smarter algorithms (Myers' diff) for big inputs. Know your limits, and say so in the design note.
Questions and answers
- What is dynamic programming, in one sentence?
- Solving a problem by filling in a table of answers to smaller versions of it, in an order where each entry only needs entries you've already computed.
- Is the longest common subsequence the same as the longest common substring?
- No. A subsequence keeps the order but may skip elements (A, C from A, B, C); a substring must be contiguous. Diff tools use the subsequence: the lines that stayed, in order, with changes in between.
Practise it in a project
These projects put this guide to work, with tickets, tests and code review.
Mergebay
A diff engine for Mergebay
Compute minimal line diffs with the longest common subsequence, then render them as unified-diff hunks with context, exactly like the tools reviewers already know.
- dynamic programming
- LCS
- unified diff format
- edge cases
Findly
Search suggestions for Findly
Build the autocomplete behind Findly's search box with a trie, then add 'did you mean' suggestions using edit distance computed along the trie.
- tries
- tree ownership
- edit distance
- dynamic programming
Read next
- Big-O in practice: amortised cost, worst cases and memory
What Big-O tells you on the job: the costs of common operations, amortised O(1), inputs that trigger the worst case, memory as a cost, and when to measure instead of guessing.