Edit Distance, in depth: the Levenshtein recurrence, a full worked table, traceback, weighted costs, OSA vs true Damerau, banded checks and BK-tree search

Deriving the recurrence

Let a have length m and b length n. Define D[i][j] as the minimum number of edits to turn the first i characters of a into the first j characters of b. The answer is D[m][n].

Look at the last position of an optimal edit script for the prefixes. Only three things can have happened to a[i-1] and b[j-1]. Either a[i-1] was deleted, so the rest of the work was turning a[:i-1] into b[:j], or b[j-1] was inserted at the end, or the two characters were lined up with each other, free if they are equal and a substitution if not. That gives the recurrence:

D[i][0] = i                       # delete all i characters
D[0][j] = j                       # insert all j characters
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])   # keep (0) or substitute (1)
)

Each cell depends only on the cell above, the cell to the left and the cell diagonally up-left, so filling the table row by row works. That is the Wagner-Fischer algorithm: O(mn) time and O(mn) space if you keep the table, O(min(m, n)) space if you only need the number and keep two rows. The structure is the same as longest common subsequence; the LCS article shows the shared shape and Hirschberg's linear-space traceback, which works for edit distance too.

Worked example: kitten to sitting

Take kitten and sitting. Row 0 and column 0 are the base cases. In row 1 ("k"), every column needs at least one edit because k matches nothing in sitting, so the row reads 1, 1, 2, 3 and so on. Row 2 ("ki") reaches 1 at column 2: substitute k with s and keep i. The diagonal of matches (i, t, t) keeps the cost at 1 down to row 4. Row 5 is "kitte" against "sitti": e and i differ, so the diagonal adds one and the cell is 2. Row 6 matches n with n at cost 2, and one more insertion for the final g makes the answer 3.

Reading the path backwards gives an edit script: substitute k with s, keep i, t, t, substitute e with i, keep n, insert g. Two substitutions and one insertion, three edits. There can be several optimal paths; which one you get depends on the order in which the traceback checks the three moves, which matters when you show the alignment to a user.

def edit_distance(a: str, b: str) -> tuple[int, list[tuple[str, str, str]]]:
    m, n = len(a), len(b)
    D = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): D[i][0] = i
    for j in range(n + 1): D[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            D[i][j] = min(D[i-1][j] + 1, D[i][j-1] + 1,
                          D[i-1][j-1] + (a[i-1] != b[j-1]))
    ops, i, j = [], m, n                      # traceback: prefer diagonal moves
    while i > 0 or j > 0:
        if i and j and D[i][j] == D[i-1][j-1] + (a[i-1] != b[j-1]):
            ops.append(("keep" if a[i-1] == b[j-1] else "sub", a[i-1], b[j-1])); i -= 1; j -= 1
        elif i and D[i][j] == D[i-1][j] + 1:
            ops.append(("del", a[i-1], "-")); i -= 1
        else:
            ops.append(("ins", "-", b[j-1])); j -= 1
    return D[m][n], ops[::-1]

# edit_distance("kitten", "sitting")
# -> (3, [('sub','k','s'), ('keep','i','i'), ('keep','t','t'), ('keep','t','t'),
#         ('sub','e','i'), ('keep','n','n'), ('ins','-','g')])

Weighted costs

Unit costs treat every typo as equally likely, which is false. On a QWERTY keyboard, typing "teh" for "the" or "gor" for "for" is common, and in OCR "rn" is often read as "m". Weighted edit distance replaces the constant 1 with cost functions: ins(c), del(c) and sub(x, y). The recurrence is unchanged; only the added terms differ. Costs can come from a keyboard adjacency table or, better, from logged corrections: if users who typed x meant y often, sub(x, y) should be low. Taking costs as negative log probabilities turns the minimum cost into the most likely error sequence, which is the noisy-channel view behind classic spell correction.

Two cautions. Weighted distances need not be symmetric, so d(a, b) may differ from d(b, a), and any index that assumes a metric breaks. And normalising by length (dividing by max(m, n)) gives a similarity in [0, 1] that is handy for thresholds, but it is not a metric either.

Transpositions: OSA vs true Damerau

Swapping two adjacent characters ("form" for "from") costs 2 in Levenshtein distance, one substitution for each letter. Damerau's observation was that transpositions are among the most common typing errors, so they should cost 1. There are two different algorithms with that name, and libraries often do not say which one they implement.

The common one is optimal string alignment (OSA): add a fourth case to the recurrence, D[i-2][j-2] + 1 when a[i-1] == b[j-2] and a[i-2] == b[j-1]. It is a five-line change. Its restriction is that no substring may be edited more than once, so you cannot transpose two letters and then insert between them. The true Damerau-Levenshtein distance (Lowrance and Wagner's algorithm) drops that restriction and needs an extra table of last-seen positions per alphabet symbol.

The difference looks academic until you check the triangle inequality. Running both on three short strings:

With OSA, d(CA, ABC) = 3 but d(CA, AC) + d(AC, ABC) = 2, so the triangle inequality fails. OSA is not a metric. True Damerau finds CA to AC to ABC as a transposition then an insertion, costing 2, and is a metric. This matters the moment you put the distance into an index that prunes using the triangle inequality, as the next section shows.

Is it within k? Banded computation

Most production questions are not "what is the distance?" but "is it at most k?" A spell checker wants candidates within 2; a deduplication job wants pairs within 3. Three observations make this far cheaper than the full table. First, if |m - n| > k the answer is no without any work. Second, any path through a cell more than k steps off the main diagonal already costs more than k, so only a band of width 2k + 1 needs computing. That is Ukkonen's banded approach, O(kn) instead of O(mn). Third, the minimum of a row never decreases in the next row, so when a whole row exceeds k you can stop.

def within(a: str, b: str, k: int) -> int | None:
    """Levenshtein distance if <= k, else None. O(k * len) time."""
    if abs(len(a) - len(b)) > k:
        return None
    if len(a) > len(b):
        a, b = b, a
    INF = k + 1
    prev = [j if j <= k else INF for j in range(len(b) + 1)]
    for i in range(1, len(a) + 1):
        cur = [INF] * (len(b) + 1)
        cur[0] = i if i <= k else INF
        for j in range(max(1, i - k), min(len(b), i + k) + 1):
            cur[j] = min(prev[j] + 1, cur[j-1] + 1,
                         prev[j-1] + (a[i-1] != b[j-1]), INF)
        if min(cur) > k:                        # row minimum only grows: stop early
            return None
        prev = cur
    return prev[-1] if prev[-1] <= k else None

# within("kitten", "sitting", 2) -> None ; within("kitten", "sitting", 3) -> 3

For long strings there is a faster family again: bit-parallel algorithms (Myers, 1999) encode a whole column of the table in machine words and update it with a handful of bitwise operations, giving roughly O(n) word operations for patterns up to 64 characters. The same idea drives approximate search in Bitap. Use a tested library for those rather than writing your own.

Searching a dictionary with a BK-tree

Comparing a query against every word in a million-word dictionary is a million DP runs. A BK-tree (Burkhard and Keller, 1973) cuts that using the triangle inequality. Each node holds a word; its children are keyed by their distance to it. To search for words within k of query q, compute d = d(q, node); by the triangle inequality, any match in the child subtree at edge e must satisfy d - k <= e <= d + k, so the other subtrees can be skipped.

class BKTree:
    def __init__(self, dist):
        self.dist, self.root = dist, None

    def add(self, word):
        if self.root is None:
            self.root = (word, {}); return
        node = self.root
        while True:
            d = self.dist(word, node[0])
            if d == 0:
                return                                   # duplicate
            if d not in node[1]:
                node[1][d] = (word, {}); return
            node = node[1][d]

    def search(self, q, k):
        out, stack = [], [self.root]
        while stack:
            word, kids = stack.pop()
            d = self.dist(q, word)
            if d <= k:
                out.append((d, word))
            stack.extend(ch for e, ch in kids.items() if d - k <= e <= d + k)
        return sorted(out)

With the eight words book, books, cake, boo, boon, cook, cape and cart inserted in that order, searching for "bo0k" within 1 returns book after computing 5 of the 8 distances, and "caqe" returns cake and cape after 4. On real dictionaries the saving is larger for k = 1 and shrinks quickly as k grows, because the allowed edge range widens.

Now the trap. If you plug OSA into a BK-tree, pruning assumes a triangle inequality that OSA does not have, and the tree silently misses true matches. A randomised test over short strings from a three-letter alphabet, 12 words per tree and k = 1, found missed matches in 14 of 3,000 trials, for example query "aba" failing to return "baa", which is one transposition away. Use Levenshtein or true Damerau in metric indexes, or verify recall against a brute-force scan.

Edit distance in production

A few practical points decide whether edit distance helps or hurts in production.

• Units. Python strings index code points, but a user sees graphemes: an emoji with a skin-tone modifier or an accented letter in decomposed form is several code points. Normalise (NFC) and, where it matters, compare grapheme clusters, or one visible typo will count as two or three edits.
• Case and spacing. Decide whether "Smith" and "smith" differ by one. Usually normalise case and whitespace first and keep distance for real typos.
• Tokens, not characters. Word error rate runs the same DP over word lists. Name matching often works better on tokens sorted alphabetically, so "Smith, John" and "John Smith" compare as equal.
• Candidate generation. For huge dictionaries, precomputed deletion neighbourhoods (the SymSpell idea) or n-gram filters in a trie or inverted index find candidates, and the DP only verifies them.
• Quadratic blow-up. Two 100,000-character documents need 10 billion cells. Use a bounded check, a diff algorithm, or chunking instead of the full table.

Failure modes

• Off-by-one in base cases. Forgetting D[i][0] = i makes every deletion at the start free; the empty-string tests catch it immediately.
• Wrong Damerau. A library labelled "Damerau-Levenshtein" that is really OSA, used in a BK-tree or for clustering that assumes a metric.
• Thresholds on raw distance. Distance 2 is a big change for a 3-letter word and small for a 30-letter one. Scale k with length or use normalised similarity.
• Rolling arrays plus traceback. Two-row memory loses the table needed for traceback; use Hirschberg if you need both.
• Unicode mismatch. Composed and decomposed forms of the same letter are "different" until normalised.

What to do next

1. Implement the full-table version with traceback and test it on empty strings, identical strings and kitten/sitting.
2. Add the two-row version and confirm it returns the same distances on random pairs.
3. Write the bounded within function and measure its speed-up for k = 1 and 2 on your real data.
4. Check which Damerau variant your library implements, using CA, AC and ABC as a test.
5. Build a BK-tree over a dictionary, and compare its results with a brute-force scan.
6. Decide on normalisation (Unicode, case, whitespace, tokens) before choosing thresholds.
7. Read the dynamic programming guide and string matching to place edit distance in the wider family.