LCS and edit distance visualizer

Row i of the table stands for the first i characters of string A, and column j for the first j characters of B; ε is the empty prefix. Press Fill to compute the cells row by row, or One cell to step. The highlighted cell is being computed from the three cells it reads, and the text under the table says which rule applied.

• Fill the textbook pair ABCBDAB and BDCABA. The bottom-right cell is the answer, 4. The side panel lists all 3 subsequences of that length; the arrows pick one of them.
• Switch to Edit distance on kitten and sitting. The first row and column are no longer zeros: turning a prefix into the empty string costs one deletion per character.
• Type two strings with nothing in common and watch the count of calls without a table explode while the table stays the same size.

The table code is checked against brute force: on random strings it finds the same LCS length and the same set of longest subsequences as trying every subsequence, the same edit distance as plain recursion, and the same number of changed lines as GNU diff --minimal.

Dynamic programming is a way of solving a problem whose answer can be built from the answers to smaller instances of the same problem, when those smaller instances overlap so heavily that solving each one separately would repeat work. The fix is to solve each subproblem once and store the result, either by caching the results of a recursive function (memoization) or by filling a table in an order where every entry's inputs are ready (tabulation).

Two properties make it work. Optimal substructure: the best answer for the whole contains the best answers for its parts. Overlapping subproblems: the recursion keeps asking the same questions. Comparing two strings has both, which is why longest common subsequence and edit distance are the standard first examples.

A subsequence keeps some characters of a string in their original order, not necessarily side by side; the longest common subsequence of two strings is the longest string that is a subsequence of both. Let T[i][j] be the LCS length of the first i characters of A and the first j of B. Then:

T[i][0] = T[0][j] = 0
T[i][j] = T[i−1][j−1] + 1 if A[i] = B[j]
T[i][j] = max(T[i−1][j], T[i][j−1]) otherwise

If the last characters match, some longest subsequence ends with that character, so the answer is one more than for the two shorter prefixes. If they differ, at least one of them is not in the subsequence, so the answer is the better of dropping A's last character or B's. The table is filled row by row, and T[m][n] is the answer.

To recover the subsequence itself, walk back from the bottom-right corner: a diagonal step through a match contributes that character, and the other steps move toward whichever neighbour the value came from. When both neighbours are equal there is a choice, and different choices can give different subsequences. ABCBDAB and BDCABA have 3: BCAB, BCBA, BDAB.

The edit distance or Levenshtein distance between two strings is the smallest number of single-character insertions, deletions and substitutions that turn one into the other. The table now holds costs, and the first row and column count the insertions or deletions needed to reach an empty prefix:

T[i][0] = i, T[0][j] = j
T[i][j] = min(T[i−1][j] + 1, T[i][j−1] + 1, T[i−1][j−1] + (A[i] = B[j] ? 0 : 1))

“kitten” becomes “sitting” in 3 edits: substitute k → s, substitute e → i, insert g. Variants change the costs: the Damerau–Levenshtein distance also counts swapping two adjacent characters as one edit, and in biology the Needleman–Wunsch algorithm (1970) uses the same table with scores for matches, mismatches and gaps to align protein and DNA sequences.

The recurrences above are already a correct recursive program. Run without a table, though, each mismatch branches two ways for LCS (three for edit distance), and the same pairs of prefixes are reached by many different paths. The number of calls, counted exactly for the examples on this page:

Both tables take O(mn) time, one constant-time step per cell. If only the length or the distance is needed, each row depends only on the row above it, so two rows are enough: O(min(m, n)) space. Recovering the subsequence or the alignment seems to need the whole table for the traceback, but Dan Hirschberg showed in 1975 that it can be done in linear space by finding the middle of the optimal path with two half-size passes and recursing on each half, at about twice the time.

Doing fundamentally better than O(mn) in the worst case is unlikely. Arturs Backurs and Piotr Indyk proved in 2015 that an algorithm for edit distance running in O(n^2−ε) time for any ε > 0 would refute the Strong Exponential Time Hypothesis, a widely believed conjecture about satisfiability; similar results followed for LCS. Practical speed-ups instead exploit inputs that are similar, as diff does.

A diff between two files is a list of lines to delete and lines to insert, and the shortest such list keeps a longest common subsequence of lines. With m and n lines and an LCS of length L, it has m + n − 2L changed lines; the side panel shows the same thing for characters.

The O(mn) table is too slow for large files, so diff tools use algorithms that are fast when the files are mostly the same. The Unix diff of 1976 used the Hunt–McIlroy algorithm, which works from matching lines. Eugene Myers's 1986 algorithm runs in O((m + n)D) time, where D is the size of the difference, and is the default in Git and the basis of GNU diff. Both GNU diff and Git use heuristics that can give a slightly longer diff on hard inputs unless asked for a minimal one (diff --minimal, git diff --diff-algorithm=minimal). Git's patience and histogram diffs give up minimality on purpose to line up unique lines such as function headers, which often reads better.

Richard Bellman developed dynamic programming at the RAND Corporation in the early 1950s for multistage decision problems and published the book Dynamic Programming in 1957; he later wrote that he chose the name partly because it sounded impressive and hard to object to. Vladimir Levenshtein defined the distance that bears his name in 1965, for error-correcting codes. Needleman and Wunsch published their sequence alignment method in 1970, and Robert Wagner and Michael Fischer gave the table algorithm for edit distance in "The String-to-String Correction Problem" in 1974. Hirschberg's linear-space method followed in 1975, the Hunt–McIlroy diff in 1976, and Myers's O(ND) algorithm in 1986.