Dynamic programming on sequences: one prefix at a time

Type “recieve” and a spell checker offers “receive”. A diff tool lines up two versions of a file and shows only the lines that changed. Both are asking how alike two sequences are: what they share, in order, and how few changes turn one into the other.

Trying every answer is hopeless: a word of m letters has $2^m$ subsequences, about a million for 20 letters and a trillion for 40. The dynamic programming lesson filled a table of smaller answers instead. With two sequences, the smaller answers are about prefixes: the first i letters of one and the first j of the other. One table holds every pair, and each cell costs a single comparison.

subsequence and substring

A subsequence keeps some letters in their order and may skip the rest: “hat” is a subsequence of “chart”. A substring is a run of consecutive letters, such as “har”.

prefix

A[1..i], the first i letters of A, counted from 1. The empty prefix, ε, has none; row 0 and column 0 stand for it.

L[i,j] and D[i,j]

What one cell means. L[i,j] is the length of the longest common subsequence (LCS) of A[1..i] and B[1..j]; D[i,j] is the fewest edits that turn A[1..i] into B[1..j].

edit distance

The fewest single-letter edits (insert, delete or replace) that turn one word into another, also called the Levenshtein distance.

traceback

A walk from the table's corner back to its edge, following the neighbour each cell was built from, to recover the letters or edits themselves.

For the longest common subsequence, the four decisions of dynamic programming are:

• State: L[i,j] is the length of the LCS of A[1..i] and B[1..j].
• Base cases: an empty prefix shares nothing, so row 0 and column 0 are all 0.
• Recurrence: look only at the last letters, A[i] and B[j]. If they match, that letter can end a common subsequence, so extend the best for the shorter prefixes: L[i,j] = L[i−1,j−1] + 1. If they differ, at most one of them can end it, so leave out A[i] (the cell above) or B[j] (the cell to the left) and keep the better: L[i,j] = max(L[i−1,j], L[i,j−1]).
• Fill order: a cell reads the cells above, to the left and diagonally up-left, so fill row by row, left to right.

The answer is the corner, L[m,n], the one cell that covers both whole words. The letters come from the walk back: a match steps diagonally and keeps its letter; otherwise the walk steps to the larger neighbour (up on a tie).

With a different rule, the same table gives the edit distance, D[i,j]. Turning i letters into nothing takes i deletes, and building j letters from nothing takes j inserts, so row 0 and column 0 count up from 0. For any other cell, think about the last edit of a cheapest script:

• Delete A[i], after turning A[1..i − 1] into B[1..j]: the cell above, plus 1.
• Insert B[j], after turning A[1..i] into B[1..j − 1]: the cell to the left, plus 1.
• Replace A[i] with B[j], after turning A[1..i − 1] into B[1..j − 1]: the diagonal, plus 1.

D[i,j] is the smallest of the three. When A[i] = B[j] there is nothing to replace, so the cell copies the diagonal, which the other two can never beat.

Turn “stop” into “tops”. Before each cell, predict its value or its cheapest edit: delete (from above), insert (from the left) or replace (from the diagonal). Then name the edit each step of the walk back stands for.

Here is the LCS table in code, for “no” and “on”. Strings count from 0, so letter i of a is a[i - 1]. The program makes a table of zeros, then fills it from row 1 and column 1.

def lcs_length(a, b):
    dp = []
    for i in range(len(a) + 1):
        dp.append([0] * (len(b) + 1))
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[len(a)][len(b)]

print(lcs_length('no', 'on'))

The table has (m + 1)(n + 1) cells at O(1) each: O(mn) time, for edit distance too. Each row reads only itself and the row above, so for the number alone two rows are enough: O(n) memory. The walk back can pass through any row, so recovering the letters or edits keeps the whole table. (Hirschberg's algorithm avoids that, at about twice the work.)

The word subsequence matters: DYNAMIC and PANORAMIC share NAMIC, five letters, as a subsequence, but only AMIC, four, as an unbroken run.

Edit distance has a tempting shortcut too: count the positions where the letters differ.

One sequence can be compared with itself, too. A longest increasing subsequence (LIS) keeps values that strictly rise from left to right. Whether v[i] can extend a run depends on the value the run ends with, so dp[i] is the length of the longest increasing run that ends exactly at v[i]: 1 more than the largest dp[j] over earlier positions j with a smaller value, or 1 if there is none. Each position looks back at every earlier one: n(n − 1)/2 comparisons, O(n²).

A faster version keeps tails[k], the smallest value so far that ends an increasing run of length k. A smaller end leaves more room for later values, and tails always rises, so each value finds its place by binary search: it replaces the first tail at least as large as itself or, if there is none, extends the longest run. That is O(n log n).

• Cell (i, j) answers the question for the first i items of one sequence and the first j of the other. Row 0 and column 0 are the empty prefixes, and the answer is the corner.
• LCS: a match adds 1 to the diagonal; a mismatch keeps the larger of above and left. Edit distance: the edges count up from 0, and a cell is the smallest of above + 1, left + 1 and diagonal + 1, or the diagonal when the letters match.
• Both take O(mn) time. Two rows give the number; listing the letters or edits walks back from the corner through the whole table.
• A subsequence may skip letters, so the LCS is often longer than any shared run. Inserts and deletes shift letters, so edit distance can be far below the count of positions that differ.
• LIS: dp[i] is the longest increasing run ending exactly at v[i], O(n²), and the answer is the largest entry, not the last. Binary searching the smallest tail of each length makes it O(n log n).
• Next: practise with Longest Common Subsequence, Fewest Edits Between Two Words and Longest Increasing Subsequence, or try your own input on the LCS, edit distance and LIS visualisers.