LCS and edit distance

Comparing two strings is one of the most used DPs: it finds what two files have in common, suggests spellings, and lines up DNA. The state is a pair of prefixes, one from each string, so the table has a row for each prefix of one string and a column for each prefix of the other.

Two strings, one table

Let the strings be a, with n letters, and b, with m letters. The state (i, j) stands for the first i letters of a and the first j letters of b: a[:i] and b[:j]. Both i and j start at 0, the empty prefix, so the table has (n + 1) rows and (m + 1) columns. Row 0 and column 0 are the base cases: one of the two prefixes is empty.

The rules below look at the last letters of the two prefixes, a[i - 1] and b[j - 1], and read only the cell above, the cell to the left, and the cell above-left. So row by row, left to right, is a safe order.

Longest common subsequence

A common subsequence of a and b is a subsequence of both (lesson 6: letters kept in order, with skips). The longest common subsequence, or LCS, of ABCBDAB and BDCABA has length 4: for example BCBA. Let L[i][j] be the LCS length of a[:i] and b[:j].

• The last letters are equal. Then L[i][j] = L[i - 1][j - 1] + 1. It is at least that, because the shared letter can be added to an LCS of the two shorter prefixes. It is not more, because removing the last letter of any common subsequence of a[:i] and b[:j] leaves a common subsequence of a[:i - 1] and b[:j - 1]: the letters left were matched to positions before the removed letter’s positions.
• The last letters differ. A common subsequence cannot use both of them, since both would have to be its last letter. So it fits in a[:i - 1] and b[:j], or in a[:i] and b[:j - 1]: L[i][j] is the larger of the cell above and the cell to the left.

def lcs_length(a, b):
    prev = [0] * (len(b) + 1)          # row 0
    for x in a:
        cur = [0]                      # column 0
        for j, y in enumerate(b):
            if x == y:
                cur.append(prev[j] + 1)
            else:
                cur.append(max(prev[j + 1], cur[j]))
        prev = cur
    return prev[-1]

Edit distance

The edit distance (or Levenshtein distance) from a to b is the fewest edits that turn a into b, where an edit inserts a letter, deletes a letter, or replaces one letter with another. From kitten to sitting it is 3: replace k with s, replace e with i, insert g.

Let D[i][j] be the edit distance from a[:i] to b[:j]. Row 0 is j (insert every letter), column 0 is i (delete every letter). For the other cells, think about what a best list of edits does at the end of the two prefixes:

• if the last letters are equal, they can simply be kept: D[i - 1][j - 1];
• otherwise the last edit is one of three, each costing 1: replace a’s last letter with b’s (above-left), delete a’s last letter (above), or insert b’s last letter (left). Take the cheapest.

The second version of the figure fills the table from horse to ros. A diagonal arrow is a kept letter or a replacement, an up arrow a delete, a left arrow an insert. Writing this as code is DYNP-P7.

Time and space

Both tables have (n + 1)(m + 1) cells and each takes O(1) time: O(n · m). Each row needs only the row above, so two rows give the length or the distance in O(m) space; making b the shorter string makes it O(min(n, m)).

For two strings of 1,000 letters that is a million cells, under a second in Python. For two files of 100,000 lines it is 10 billion cells, which is too many. Tools that compare similar files use the fact that the answer is small: when the two are at most d edits apart, only cells within d of the diagonal matter, and the work drops to about O((n + m) · d). Myers’ method, used by git diff, works this way.

Where they are used

• Comparing files. The lines kept in a diff are a longest common subsequence of the two files’ lines; the rest are shown as removed or added.
• Spelling. A spell checker suggests dictionary words within edit distance 1 or 2 of the typed word.
• DNA and proteins. Alignment uses the same table with scores: a reward for a match, a cost for a mismatch and for a gap (the Needleman–Wunsch method). Finding the best matching part of two long sequences is a small change to the rule (the Smith–Waterman method).

Now try DYNP-P7, Edit distance.