Turning one string into another

Edit distance is the two sequence grid at its clearest, and it is the engine behind spell checkers, diff tools and fuzzy search.

The table

def edit_distance(a, b):
    n, m = len(a), len(b)
    d = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1): d[i][0] = i      # delete all of a
    for j in range(m + 1): d[0][j] = j      # insert all of b

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                d[i][j] = d[i-1][j-1]       # free, no edit needed
            else:
                d[i][j] = 1 + min(d[i-1][j],      # delete from a
                                  d[i][j-1],      # insert into a
                                  d[i-1][j-1])    # replace
    return d[n][m]

Reading the moves off the grid

Each neighbour is one edit, and which one follows from which string it consumes:

The matching case takes the diagonal at no cost, which is the fourth case people forget and the reason the answer is not simply the length difference.

The base cases matter

Leaving row 0 and column 0 as zeroes is the classic bug. It claims an empty string can be turned into a ten character one for free, and since the recurrence takes a minimum, those false zeroes are attractive and get chosen. Every distance comes out too small, and nothing errors.

Worked

        ""  k   i   t   t   e   n
   ""    0  1   2   3   4   5   6
    s    1  1   2   3   4   5   6
    i    2  2   1   2   3   4   5
    t    3  3   2   1   2   3   4
    t    4  4   3   2   1   2   3
    i    5  5   4   3   2   2   3
    n    6  6   5   4   3   3   2
    g    7  7   6   5   4   4   3

Three: substitute k with s, substitute e with i, insert g.

Recovering the edits

Walk back from the bottom right, at each cell asking which neighbour produced its value. That produces the actual script of changes, which is what a diff tool displays and what a spell checker uses to rank suggestions.

Space

Only the previous row is read, so two rows suffice and the space drops from O(nm) to O(m). As always, that costs the reconstruction. Hirschberg's algorithm recovers the alignment in linear space by recursively splitting, at roughly double the time, and it is the answer when both matter.

The family

Longest common subsequence is the same grid with a maximum and a credit instead of a minimum and a cost. Sequence alignment in bioinformatics is the same grid with per character costs. Damerau-Levenshtein adds transposition as a fourth move, because swapping two letters is one typo rather than two.