On this page

Capstone: A Diff Tool and a Spell-Checker with DP

Three of the most familiar tools on a programmer's machine are dynamic programs in disguise. diff (and every code review screen built on it) finds a longest common subsequence of two files. A spell-checker's "did you mean…?" ranks dictionary words by edit distance. And a typesetter deciding where to break the lines of a paragraph runs a shortest-path DP over break points. In this capstone you build all three from scratch, test them against brute force and against a real tool, and then measure what the textbook space optimisation actually buys.

This is Module 6 applied. You will use the two-string grid from Grid & Path DP, the edit-distance and LCS recurrences from Sequence DP and String DP, the "cut the sequence into pieces" recurrence from Partition DP, and the debugging habits from DP Debugging. The interesting problems are the ones the recurrences leave out: turning a DP table into a readable patch, deciding which of many equally short diffs to print, keeping a dictionary search from computing 50,000 distances per keystroke, and noticing when a "space optimisation" does not make anything faster.

Goal

Build a small command-line toolkit, dptext, with three commands and one benchmark:

  1. dptext diff OLD NEW prints a unified diff (the ---/+++/@@ format of diff -u and git diff) computed from a longest common subsequence of lines.
  2. dptext suggest WORD prints the closest dictionary words by edit distance, using a BK-tree or a bounded (banded) edit distance so that it does not compare the word against every entry at full cost.
  3. dptext wrap WIDTH breaks a paragraph into lines of at most WIDTH characters minimising raggedness (the sum of squared trailing spaces), in the style of Knuth and Plass.
  4. dptext bench measures the full table against the two-row version, in time and in memory.

The diff must round-trip (applying it to OLD yields NEW) and must be minimal (no other diff changes fewer lines). The suggestions must equal those of a linear scan. The line breaker must be optimal, checked by brute force on small inputs. The reference solution is a single tested Python file; port it to the language you use at work if you like.

Requirements

  • Diff. Work on lists of lines (no trailing newline characters). Compute an LCS with the classic table; peel off the common prefix and suffix first. Emit the edit script, then group changes into hunks with 3 lines of context (configurable). Print ranges in the unified format: @@ -start,len +start,len @@, 1-based, with ,len omitted when it is 1 and start pointing at the line before an empty range (-0,0).
  • Ties. When deleting and inserting are equally good, delete first, so a changed line prints as -old then +new, the way diff and git show it.
  • Spell-checker. Levenshtein distance (insert, delete, substitute; each costs 1). A dictionary index that returns exactly the words within distance of the query. Rank by distance, then alphabetically (frequency ranking is a stretch goal).
  • Line breaker. Each line's cost is , where used counts the letters plus one space between words; the last line is free; a line that overflows is forbidden. A word longer than the width is an error.
  • Benchmark. Same inputs for both LCS versions, same answer asserted, best of 3 runs for time, a separate traced run for peak memory.
  • Tests. The acceptance tests below pass.

Getting the data

Everything here runs offline. The reference solution embeds its test inputs.

  • Diff. Any two versions of a text file. The reference uses a 17-line shopping list and an edited 18-line version, designed so that the changes form two separate hunks. For real practice, diff two releases of a source file (git show v1:file > old, git show v2:file > new) and compare your output with diff -u old new.
  • Dictionary. The acceptance tests use an embedded list of 136 common English words. For the benchmark, most Unix-like systems ship a word list at /usr/share/dict/words; macOS's is Webster's Second International (235,976 entries; see /usr/share/dict/README). On Linux it comes from a package such as wamerican. The reference samples 50,000 words from it with a fixed seed.
  • Paragraph. The first two paragraphs of Lincoln's Gettysburg Address (1863, public domain), 102 words — long enough that greedy line filling makes visibly worse choices than the DP.
flowchart LR
    OLD["old lines"] --> TRIM["Trim common prefix and suffix"]
    NEW["new lines"] --> TRIM
    TRIM --> LCS["LCS table on the middle"]
    LCS --> SCRIPT["Walk the table: keep, delete, insert"]
    SCRIPT --> HUNK["Group changes with 3 lines of context"]
    HUNK --> OUT["Unified diff out"]
    OUT --> CHECK["Apply patch: equals new? Changes = n + m - 2 LCS?"]

The staged plan

Part 1 — An LCS-based line diff with unified output

The model. Put the old file's lines down the side of a grid and the new file's lines across the top. A path from the top-left to the bottom-right corner moving down (delete an old line), right (insert a new line) or diagonally (keep a line — allowed only where the two lines are equal) is an edit script: a recipe that turns the old file into the new one. This grid is called the edit graph. The fewest deletions plus insertions is achieved by the path with the most diagonal steps, and the number of diagonals on that path is the length of a longest common subsequence (LCS) of the two line lists. If the LCS has length , the minimal script deletes lines and inserts , for changed lines in total.

Step 1: the table. Use the suffix form: = LCS length of a[i:] and b[j:].

Filling from the bottom-right lets you read the script forwards from , which is the order you print it in. (With the usual prefix form you would walk backwards from and reverse.)

Step 2: the walk. From : if the lines are equal, keep (diagonal). Otherwise delete if , else insert. The >= is the tie rule: when both moves are optimal, deleting first makes a replaced line print as -old then +new. Taking the diagonal whenever the lines match is always safe — a standard exchange argument shows some LCS uses that match (CLRS §14.4).

Step 3: trim first. Real edits touch a few lines of a long file. Before building the table, strip the longest common prefix and suffix; they are kept lines in any minimal script. This turns a table into, typically, a one, and every production diff does it.

Step 4: hunks. Number the script's operations. A hunk is a run of changes plus up to context unchanged lines on each side. Two changes separated by at most unchanged lines go into the same hunk (their context windows would touch); a longer gap starts a new hunk. For each hunk print @@ -s1,l1 +s2,l2 @@, where s1 is the old file's 1-based line number of the hunk's first line and l1 counts the hunk's lines that exist in the old file (kept and deleted), and likewise for the new file (kept and inserted).

Step 5: verify. Write apply_unified(old, diff) and check on random inputs that it returns new. Then check minimality: the number of + and - lines must equal , using an independent LCS function. These two properties are all you need — the exact diff is not unique when there are ties, so do not compare against another tool's output byte for byte except on inputs without ties.

Why diff on lines, not characters?

A line is the unit people review, and hashing each line to an integer turns a 10 MB file into a list of perhaps 200,000 symbols. Comparing integers instead of strings is the other standard speed-up: production tools first map every distinct line to a small integer id, then run the DP on the ids.

Part 2 — Spell suggestions with edit distance

The distance. The Levenshtein distance between two words is the fewest single-character insertions, deletions and substitutions that turn one into the other (Levenshtein, 1965; the table algorithm is due to Wagner and Fischer, 1974). The DP is the same grid as Part 1 with a third move: a diagonal step on unequal characters costs 1 (a substitution).

Two rows suffice, because each row reads only the one above. kitten → sitting has distance 3 (substitute k→s, substitute e→i, insert g).

The naive suggester computes the distance from the query to every dictionary word and keeps those within (usually 1 or 2). With 50,000 words of about 9 letters, that is 50,000 tables of about 80 cells: 4 million cell updates per query. Two ways to do less work:

Option A: bounded (banded) edit distance. If you only care whether the distance is at most , two shortcuts apply (Ukkonen, 1985):

  1. If the lengths differ by more than , the distance is more than — no table at all.
  2. Cell with already costs more than (you need at least insertions or deletions to get there), so fill only the band of width around the diagonal: instead of .
  3. If every cell in a row exceeds , stop: values never decrease down a column of the band.

The function returns the true distance when it is at most , and otherwise.

Option B: a BK-tree. A BK-tree (Burkhard and Keller, 1973) indexes a set of words under any metric — a distance that is zero only for equal words, symmetric, and obeys the triangle inequality . Levenshtein distance is a metric. Pick any word as the root. Every other word hangs below the root on an edge labelled with its distance to the root; words at the same distance share a subtree, built recursively.

To find all words within of a query : compute ; report the node if ; then descend only into children whose edge label satisfies . Why is that safe? A word in the child with label has . By the triangle inequality, . If , nothing in that subtree can be within of .

flowchart TD
    ROOT["the"] -->|"1"| H["he"]
    ROOT -->|"4"| SP["spell"]
    ROOT -->|"5"| WS["words"]
    ROOT -->|"7"| SG["spelling"]
    H -->|"2"| T["then"]
    T -->|"1"| TM["them"]
    SP -->|"5"| W["word"]

This is the tree the reference code builds from the, he, then, them, spelling, spell, word, words, in that order. (then is at distance 1 from the, but edge 1 is taken by he, so it moves down and hangs below he at distance .) Query speling with : the root gives , so only edges labelled 5 to 7 are followed. words is at distance 7 and has no children; spelling is at distance 1 and is reported. The subtrees under he and spell are never visited: 3 distance computations instead of 8.

Ranking. Return words sorted by distance, then alphabetically. Real spell-checkers also weigh how common each candidate is (Norvig's essay "How to Write a Spelling Corrector" is a good short read) and model typing errors: swapping two adjacent letters is one of the most common typos, but plain Levenshtein charges 2 for it. That is why teh has no suggestion within distance 1 in the acceptance tests, and why Damerau's variant (below) exists.

Part 3 — Minimum-raggedness line breaking

The problem. Lay out the words of a paragraph in lines of at most W characters, keeping word order, one space between words. A greedy layout (put as many words as fit on each line, then start a new one) is what most text boxes do. It never looks ahead, so one long word can leave a big gap on the line before. Knuth and Plass ("Breaking paragraphs into lines", 1981) built TeX's line breaker on a DP that looks at the whole paragraph at once. Their real cost model (stretchable glue, hyphenation, penalties, "demerits") is rich; we use the classic simplified version, the minimum raggedness objective:

Squaring makes two lines with 3 spare characters each (cost ) better than one with 0 and one with 6 (cost ): it prefers even margins.

The DP. Let be the minimum cost of laying out words . The first line of that layout holds words for some :

This is a shortest path in a DAG whose vertices are "the next line starts at word " — the same shape as Partition DP. Loop upward from and stop as soon as the line overflows; a line holds at most about words, so the work is rather than . Record the best for each and follow those pointers to print the layout.

Real paragraph, width 40. Greedy (cost 292):

|Four score and seven years ago our      |  6 spare
|fathers brought forth on this continent,|  0
|a new nation, conceived in Liberty, and |  1
|dedicated to the proposition that all   |  3
|men are created equal. Now we are       |  7
|engaged in a great civil war, testing   |  3
|whether that nation, or any nation so   |  3
|conceived and so dedicated, can long    |  4
|endure. We are met on a great           | 11
|battle-field of that war. We have come  |  2
|to dedicate a portion of that field, as |  1
|a final resting place for those who here|  0
|gave their lives that that nation might |  1
|live. It is altogether fitting and      |  6
|proper that we should do this.          | 10 (last line, free)

Minimum raggedness (cost 224):

|Four score and seven years ago our      |  6 spare
|fathers brought forth on this continent,|  0
|a new nation, conceived in Liberty,     |  5
|and dedicated to the proposition that   |  3
|all men are created equal. Now we are   |  3
|engaged in a great civil war, testing   |  3
|whether that nation, or any nation      |  6
|so conceived and so dedicated, can      |  6
|long endure. We are met on a great      |  6
|battle-field of that war. We have come  |  2
|to dedicate a portion of that field,    |  4
|as a final resting place for those who  |  2
|here gave their lives that that nation  |  2
|might live. It is altogether fitting and|  0
|proper that we should do this.          | 10 (last line, free)

Greedy's worst line has 11 spare characters (endure. We are met on a great) because it packed so and long onto the two lines before it. The DP moves so and long down, spreading the gap over three lines of 6 each: instead of . The total cost drops from 292 to 224, with the same 15 lines. Check the arithmetic: greedy ; DP .

Not LeetCode 68

LeetCode 68 "Text Justification" asks for greedy filling and then spreading the spaces to make both margins straight. That is a formatting exercise, not an optimisation. Here the line breaks themselves are the decision, and full justification is just a way of printing the lines you chose (a stretch goal).

Part 4 — Benchmark: full table versus two rows

Every DP textbook says "LCS needs only two rows, so space drops from to ". Measure what that buys, and what it costs.

  1. Generate two random DNA-like strings of length over ACGT with a fixed seed, for .
  2. Run the full-table LCS length and the two-row version on the same pair. Assert equal answers.
  3. Time each as the best of 3 runs with time.perf_counter(). Measure peak memory in a separate run with tracemalloc (tracing slows Python allocation by an order of magnitude; do not time a traced run — that was the first mistake made while writing this page).
  4. Tabulate, and explain the shape of each column.

The full table is what Part 1 needs to reconstruct the edit script. The two-row version gives only the length. Hirschberg's algorithm (stretch goal 2) gets the script in linear space too, by recomputing.

Milestones

#MilestoneDone when
1LCS table and edit scriptedit_script changes exactly lines on 500 random pairs
2Unified outputthe golden shopping-list diff matches byte for byte; identical files give empty output
3Patch applicationapply_unified(old, diff) == new for context 0, 1 and 3 on 500 random pairs
4Edit distance, full and boundedbounded(s, t, k) == min(full(s, t), k + 1) on 2,000 random pairs for
5BK-treesearch results equal a linear scan for every test query
6Line breakerDP cost equals brute force over all break sets on 300 random small paragraphs
7Benchmarka table of time and peak memory for 4 sizes, with an explanation
8CLIdptext diff/suggest/wrap/bench wired to the functions above

Acceptance tests

Your toolkit passes when:

TestExpected
Diff of the shopping lists, context 3exactly the two hunks below (@@ -1,10 +1,10 @@ and @@ -13,5 +13,6 @@)
Diff of a file with itselfno output
Diff of empty → ["x"]@@ -0,0 +1 @@ then +x
Diff of ["x"] → empty@@ -1 +0,0 @@ then -x
500 random pairs over a 5-letter alphabet, lengths 0–20patch round-trips for context 0, 1, 3; changed lines
levenshtein("kitten", "sitting"), ("flaw", "lawn"), ("", "abc")3, 2, 3
Bounded distance, 2,000 random pairs, equals
Suggestions (136-word dictionary, )speling → spelling; recieve → receive; dinamic → dynamic; langauge → language
teh with / no suggestions / the among them
BK-tree vs linear scan for speling wrod progam xyzzy distnce tehidentical (distance, word) lists
Gettysburg paragraph, width 40greedy cost 292, DP cost 224, both 15 lines
Line breaker vs brute force, 300 random paragraphs of ≤ 9 words, width 10equal costs
Full vs two-row LCS, 200 random pairsequal

The golden diff (your tool's header names may differ):

--- list.old
+++ list.new
@@ -1,10 +1,10 @@
 # Shopping list
 apples
 bread
-butter
 cheese
 eggs
 flour
+honey
 milk
 mustard
 oats
@@ -13,5 +13,6 @@
 rice
 salt
 sugar
-tea
+green tea
 yoghurt
+zucchini

Between the two hunks lie pasta and pepper: the gap from flour/honey to tea is 8 unchanged lines, more than , so the hunks stay separate. On this input the output is identical (apart from the timestamps in the header lines) to diff -u from the system diff on macOS 26, which was checked while writing this page.

Reference solution

Reference solution (Python, tested)

One file, standard library only. python3 capstone.py runs every acceptance test; python3 capstone.py --bench runs Part 4 and the dictionary benchmark (about a minute). The CLI wrapper (milestone 8) is left to you: it is a few lines of argparse around unified_diff, suggest, break_min_raggedness and benchmark.

"""DP capstone reference solution: line diff, spell suggestions, line breaking, benchmarks.

Run `python3 capstone.py` for the acceptance tests, `python3 capstone.py --bench` for Part 4.
"""
import random
import sys
import time
import tracemalloc

# ---------------------------------------------------------------- Part 1: diff


def lcs_suffix_table(a, b):
    """L[i][j] = length of an LCS of a[i:] and b[j:]  (an (n+1) x (m+1) table)."""
    n, m = len(a), len(b)
    L = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        row, below = L[i], L[i + 1]
        for j in range(m - 1, -1, -1):
            if a[i] == b[j]:
                row[j] = below[j + 1] + 1
            else:
                row[j] = max(below[j], row[j + 1])
    return L


def edit_script(a, b):
    """Minimal list of (op, line) with op in ' ', '-', '+' turning a into b.

    Common prefix and suffix are peeled off first (cheap, and usually most of a file).
    On ties we delete before we insert, so a changed line prints as '-old' then '+new'.
    """
    pre = 0
    while pre < len(a) and pre < len(b) and a[pre] == b[pre]:
        pre += 1
    suf = 0
    while suf < len(a) - pre and suf < len(b) - pre and a[-1 - suf] == b[-1 - suf]:
        suf += 1
    mid_a, mid_b = a[pre:len(a) - suf], b[pre:len(b) - suf]
    L = lcs_suffix_table(mid_a, mid_b)
    ops = [(" ", line) for line in a[:pre]]
    i = j = 0
    while i < len(mid_a) or j < len(mid_b):
        if i < len(mid_a) and j < len(mid_b) and mid_a[i] == mid_b[j]:
            ops.append((" ", mid_a[i]))
            i, j = i + 1, j + 1
        elif j == len(mid_b) or (i < len(mid_a) and L[i + 1][j] >= L[i][j + 1]):
            ops.append(("-", mid_a[i]))
            i += 1
        else:
            ops.append(("+", mid_b[j]))
            j += 1
    ops += [(" ", line) for line in a[len(a) - suf:]]
    return ops


def _range(start, length):
    """Unified-diff range: 1-based start, ',length' omitted when it is 1."""
    if length == 0:
        return f"{start - 1},0"             # empty range points at the line before
    if length == 1:
        return f"{start}"
    return f"{start},{length}"


def unified_diff(a, b, from_name="a", to_name="b", context=3):
    """Lines of a unified diff of the line lists a and b (no trailing newlines)."""
    ops = edit_script(a, b)
    changes = [k for k, (op, _) in enumerate(ops) if op != " "]
    if not changes:
        return []
    # Group changes whose context windows touch into hunks of op indices [lo, hi).
    hunks = []
    lo, hi = max(0, changes[0] - context), changes[0] + 1
    for k in changes[1:]:
        if k - context <= hi + context:      # gap of at most 2*context unchanged lines
            hi = k + 1
        else:
            hunks.append((lo, min(len(ops), hi + context)))
            lo, hi = k - context, k + 1
    hunks.append((lo, min(len(ops), hi + context)))

    out = [f"--- {from_name}", f"+++ {to_name}"]
    # line numbers (1-based) of a and b at each op index
    a_line = b_line = 1
    starts = []
    for op, _ in ops:
        starts.append((a_line, b_line))
        if op != "+":
            a_line += 1
        if op != "-":
            b_line += 1
    for lo, hi in hunks:
        a_len = sum(1 for op, _ in ops[lo:hi] if op != "+")
        b_len = sum(1 for op, _ in ops[lo:hi] if op != "-")
        a_start, b_start = starts[lo]
        out.append(f"@@ -{_range(a_start, a_len)} +{_range(b_start, b_len)} @@")
        out += [op + line for op, line in ops[lo:hi]]
    return out


def apply_unified(a, diff):
    """Apply a unified diff produced above to a; returns the new line list."""
    result, pos = [], 0                       # pos = 0-based index into a
    k = 2
    while k < len(diff):
        header = diff[k].split()
        old = header[1][1:].split(",")
        start = int(old[0])
        length = int(old[1]) if len(old) > 1 else 1
        first = start - 1 if length > 0 else start   # 0-based index of the hunk's first old line
        result += a[pos:first]
        pos = first
        k += 1
        while k < len(diff) and not diff[k].startswith("@@"):
            op, line = diff[k][0], diff[k][1:]
            if op == " ":
                assert a[pos] == line, "context mismatch"
                result.append(line)
                pos += 1
            elif op == "-":
                assert a[pos] == line, "deleted line mismatch"
                pos += 1
            else:
                result.append(line)
            k += 1
    return result + a[pos:]


# ------------------------------------------------------- Part 2: spell checker


def levenshtein(s, t):
    """Edit distance (insert, delete, substitute, each cost 1) with two rows."""
    if len(s) < len(t):
        s, t = t, s
    prev = list(range(len(t) + 1))
    for i, cs in enumerate(s, 1):
        cur = [i] + [0] * len(t)
        for j, ct in enumerate(t, 1):
            cur[j] = min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + (cs != ct))
        prev = cur
    return prev[-1]


def bounded_levenshtein(s, t, k):
    """Edit distance if it is <= k, else k + 1. Only a diagonal band of width 2k+1 is filled."""
    if abs(len(s) - len(t)) > k:
        return k + 1
    big = k + 1
    prev = [j if j <= k else big for j in range(len(t) + 1)]
    for i in range(1, len(s) + 1):
        lo, hi = max(1, i - k), min(len(t), i + k)
        cur = [big] * (len(t) + 1)
        if i <= k:
            cur[0] = i
        for j in range(lo, hi + 1):
            cur[j] = min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + (s[i - 1] != t[j - 1]), big)
        if min(cur[max(0, lo - 1):hi + 1]) > k:
            return big                        # every path already costs more than k
        prev = cur
    return min(prev[len(t)], big)


class BKTree:
    """Burkhard-Keller tree: children keyed by their distance to the parent."""

    def __init__(self, distance=levenshtein):
        self.distance = distance
        self.root = None                      # node = [word, {dist: child}]
        self.calls = 0

    def add(self, word):
        if self.root is None:
            self.root = [word, {}]
            return
        node = self.root
        while True:
            d = self.distance(word, node[0])
            if d == 0:
                return                        # already present
            child = node[1].get(d)
            if child is None:
                node[1][d] = [word, {}]
                return
            node = child

    def search(self, word, tol):
        """All (distance, word) with distance <= tol. Triangle inequality prunes children."""
        found, stack = [], [self.root] if self.root else []
        while stack:
            node = stack.pop()
            d = self.distance(word, node[0])
            self.calls += 1
            if d <= tol:
                found.append((d, node[0]))
            for edge, child in node[1].items():
                if d - tol <= edge <= d + tol:
                    stack.append(child)
        return sorted(found)


def suggest(tree, word, max_dist=2, limit=5):
    """Closest dictionary words: nearest distance first, then alphabetical."""
    return [w for _, w in tree.search(word.lower(), max_dist)[:limit]]


# ---------------------------------------------- Part 3: minimum-raggedness lines


def break_greedy(words, width):
    """First fit: put as many words as possible on each line."""
    lines, cur = [], []
    for w in words:
        if cur and len(" ".join(cur + [w])) > width:
            lines.append(cur)
            cur = []
        cur.append(w)
    return lines + [cur] if cur else lines


def break_min_raggedness(words, width):
    """Knuth-Plass-style DP: minimise the sum of squared trailing spaces (last line free).

    best[i] = min over j of cost(words i..j-1) + best[j],   best[n] = 0.
    """
    n = len(words)
    lengths = [len(w) for w in words]
    if max(lengths, default=0) > width:
        raise ValueError("a word is longer than the line width")
    best = [0] * (n + 1)
    nxt = [n] * (n + 1)
    for i in range(n - 1, -1, -1):
        best[i] = None
        used = -1
        for j in range(i + 1, n + 1):
            used += lengths[j - 1] + 1
            if used > width:
                break                         # longer lines only get longer
            cost = 0 if j == n else (width - used) ** 2
            if best[i] is None or cost + best[j] < best[i]:
                best[i], nxt[i] = cost + best[j], j
    lines, i = [], 0
    while i < n:
        lines.append(words[i:nxt[i]])
        i = nxt[i]
    return lines


def raggedness(lines, width):
    """Sum of squared trailing spaces over all lines except the last."""
    return sum((width - len(" ".join(line))) ** 2 for line in lines[:-1])


# ------------------------------------------------------------ Part 4: benchmark


def lcs_full(a, b):
    """LCS length with the full (n+1) x (m+1) table."""
    return lcs_suffix_table(a, b)[0][0]


def lcs_two_rows(a, b):
    """LCS length with two rows of length min(n, m) + 1."""
    if len(a) < len(b):
        a, b = b, a
    prev = [0] * (len(b) + 1)
    for x in a:
        cur = [0] * (len(b) + 1)
        for j, y in enumerate(b, 1):
            cur[j] = prev[j - 1] + 1 if x == y else max(prev[j], cur[j - 1])
        prev = cur
    return prev[-1]


def measure(fn, *args):
    """(result, best wall time of 3 runs in seconds, peak traced bytes of one run)."""
    times = []
    for _ in range(3):
        t0 = time.perf_counter()
        result = fn(*args)
        times.append(time.perf_counter() - t0)
    tracemalloc.start()                       # memory measured separately: tracing slows code
    fn(*args)
    _, peak = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    return result, min(times), peak


def benchmark(sizes=(500, 1000, 2000, 4000), seed=6):
    rng = random.Random(seed)
    print(f"{'n = m':>6} {'full s':>8} {'full MiB':>9} {'2-row s':>8} {'2-row KiB':>10}")
    for n in sizes:
        a = "".join(rng.choice("ACGT") for _ in range(n))
        b = "".join(rng.choice("ACGT") for _ in range(n))
        r1, t1, m1 = measure(lcs_full, a, b)
        r2, t2, m2 = measure(lcs_two_rows, a, b)
        assert r1 == r2
        print(f"{n:>6} {t1:>8.3f} {m1 / 2**20:>9.1f} {t2:>8.3f} {m2 / 2**10:>10.1f}")


def benchmark_bktree(path="/usr/share/dict/words", sample=50_000, queries=200, seed=7):
    """Distance computations per query: BK-tree vs scanning the whole word list."""
    try:
        with open(path) as f:
            words = sorted({w.strip().lower() for w in f if w.strip().isalpha()})
    except OSError:
        print("no word list at", path)
        return
    rng = random.Random(seed)
    words = rng.sample(words, min(sample, len(words)))
    tree = BKTree()
    t0 = time.perf_counter()
    for w in words:
        tree.add(w)
    print(f"built BK-tree of {len(words)} words in {time.perf_counter() - t0:.1f} s")
    for tol in (1, 2):
        tree.calls = 0
        t0 = time.perf_counter()
        for _ in range(queries):
            w = list(rng.choice(words))
            w[rng.randrange(len(w))] = rng.choice("abcdefghijklmnopqrstuvwxyz")
            tree.search("".join(w), tol)
        per_query = tree.calls / queries
        ms = 1000 * (time.perf_counter() - t0) / queries
        print(f"tol {tol}: {per_query:,.0f} distance calls per query "
              f"({100 * per_query / len(words):.1f}% of a linear scan), {ms:.1f} ms per query")
    for name, dist in (("full", lambda s, t: levenshtein(s, t) <= 2),
                       ("bounded", lambda s, t: bounded_levenshtein(s, t, 2) <= 2)):
        t0 = time.perf_counter()
        for _ in range(20):
            w = rng.choice(words)
            hits = [x for x in words if dist(w, x)]
            assert w in hits
        print(f"linear scan, {name} edit distance, tol 2: "
              f"{1000 * (time.perf_counter() - t0) / 20:.0f} ms per query")


# ------------------------------------------------------------- acceptance tests

OLD = """\
# Shopping list
apples
bread
butter
cheese
eggs
flour
milk
mustard
oats
pasta
pepper
rice
salt
sugar
tea
yoghurt""".split("\n")

NEW = """\
# Shopping list
apples
bread
cheese
eggs
flour
honey
milk
mustard
oats
pasta
pepper
rice
salt
sugar
green tea
yoghurt
zucchini""".split("\n")

DICTIONARY = """a about above after again algorithm all also an and answer any are as at be
because been before being below between both but by can cannot change characters could
dictionary did different distance do does doing down during dynamic each edit few for
from further had has have having he her here hers him his how i if in into is it its
just language letter letters like line lines more most my no nor not now of off on
once only or other our out over own program programming receive same she should so
some spell spelling string such than that the their them then there these they this
those through to too under until up very was we were what when where which while who
why will with word words would you your""".split()

GETTYSBURG = (
    "Four score and seven years ago our fathers brought forth on this continent, a new "
    "nation, conceived in Liberty, and dedicated to the proposition that all men are "
    "created equal. Now we are engaged in a great civil war, testing whether that nation, "
    "or any nation so conceived and so dedicated, can long endure. We are met on a great "
    "battle-field of that war. We have come to dedicate a portion of that field, as a "
    "final resting place for those who here gave their lives that that nation might live. "
    "It is altogether fitting and proper that we should do this."
)


def run_tests():
    # Part 1: golden output
    diff = unified_diff(OLD, NEW, "list.old", "list.new")
    expected = [
        "--- list.old", "+++ list.new",
        "@@ -1,10 +1,10 @@",
        " # Shopping list", " apples", " bread", "-butter", " cheese", " eggs", " flour",
        "+honey", " milk", " mustard", " oats",
        "@@ -13,5 +13,6 @@",
        " rice", " salt", " sugar", "-tea", "+green tea", " yoghurt", "+zucchini",
    ]
    assert diff == expected, "\n".join(diff)
    assert apply_unified(OLD, diff) == NEW
    assert unified_diff(OLD, OLD) == []
    assert unified_diff([], ["x"]) == ["--- a", "+++ b", "@@ -0,0 +1 @@", "+x"]
    assert unified_diff(["x"], []) == ["--- a", "+++ b", "@@ -1 +0,0 @@", "-x"]
    # Part 1: random round trips, and the diff is minimal
    rng = random.Random(1986)
    for _ in range(500):
        a = [rng.choice("abcde") for _ in range(rng.randint(0, 20))]
        b = [rng.choice("abcde") for _ in range(rng.randint(0, 20))]
        for ctx in (0, 1, 3):
            assert apply_unified(a, unified_diff(a, b, context=ctx)) == b
        changed = sum(op != " " for op, _ in edit_script(a, b))
        assert changed == len(a) + len(b) - 2 * lcs_two_rows(a, b)

    # Part 2: distances, bounded distances, BK-tree vs linear scan
    assert levenshtein("kitten", "sitting") == 3
    assert levenshtein("", "abc") == 3 and levenshtein("flaw", "lawn") == 2
    for _ in range(2000):
        s = "".join(rng.choice("abc") for _ in range(rng.randint(0, 8)))
        t = "".join(rng.choice("abc") for _ in range(rng.randint(0, 8)))
        d = levenshtein(s, t)
        for k in range(0, 5):
            assert bounded_levenshtein(s, t, k) == min(d, k + 1)
    tree = BKTree()
    for w in DICTIONARY:
        tree.add(w)
    assert suggest(tree, "speling") == ["spelling"]
    assert suggest(tree, "recieve") == ["receive"]
    assert suggest(tree, "dinamic") == ["dynamic"]
    assert suggest(tree, "langauge") == ["language"]
    assert suggest(tree, "teh", 1) == []             # a swap costs 2 in plain Levenshtein
    assert "the" in suggest(tree, "teh", 2, limit=10)
    for word in ["speling", "wrod", "progam", "xyzzy", "distnce", "teh"]:
        scan = sorted((levenshtein(word, w), w) for w in DICTIONARY if levenshtein(word, w) <= 2)
        assert tree.search(word, 2) == scan

    # Part 3: line breaking on a real paragraph
    words = GETTYSBURG.split()
    greedy = break_greedy(words, 40)
    best = break_min_raggedness(words, 40)
    assert [w for line in best for w in line] == words
    assert all(len(" ".join(line)) <= 40 for line in best)
    assert (raggedness(greedy, 40), raggedness(best, 40)) == (GREEDY_COST, DP_COST)
    for _ in range(300):                       # DP is optimal: compare with brute force
        ws = ["x" * rng.randint(1, 6) for _ in range(rng.randint(1, 9))]
        assert raggedness(break_min_raggedness(ws, 10), 10) == brute_raggedness(ws, 10)

    # Part 4: both LCS versions agree
    for _ in range(200):
        a = "".join(rng.choice("AC") for _ in range(rng.randint(0, 30)))
        b = "".join(rng.choice("AC") for _ in range(rng.randint(0, 30)))
        assert lcs_full(a, b) == lcs_two_rows(a, b)
    print("all acceptance tests passed")


def brute_raggedness(words, width):
    """Try all 2^(n-1) ways to break the line sequence."""
    n, best = len(words), None
    for mask in range(1 << (n - 1)):
        lines, cur = [], [words[0]]
        for k in range(1, n):
            if mask >> (k - 1) & 1:
                lines.append(cur)
                cur = []
            cur.append(words[k])
        lines.append(cur)
        if all(len(" ".join(line)) <= width for line in lines):
            cost = raggedness(lines, width)
            best = cost if best is None else min(best, cost)
    return best


GREEDY_COST, DP_COST = 292, 224               # width 40, measured and checked by hand

if __name__ == "__main__":
    if "--bench" in sys.argv:
        if "--skip-lcs" not in sys.argv:
            benchmark()
        benchmark_bktree()
    else:
        run_tests()

Benchmarks and what the numbers should look like

All numbers below were measured while writing this page, with CPython 3.12 on an Apple-silicon Mac. Your absolute times will differ; the ratios and the shapes should not.

Full table versus two rows (LCS length of two random ACGT strings).

Full table: timeFull table: peak memoryTwo rows: timeTwo rows: peak memory
5000.016 s2.1 MiB0.015 s14.0 KiB
1,0000.074 s11.4 MiB0.068 s43.1 KiB
2,0000.331 s53.4 MiB0.302 s96.1 KiB
4,0001.382 s228.8 MiB1.037 s199.8 KiB

How to read it:

  • Time is quadratic for both, about ×4 per doubling, because both fill cells. The space optimisation does not reduce the number of cells. It is 5–25% faster here, mostly because the two rows stay in the CPU cache while the full table does not, and because Python allocates fewer list objects.
  • Memory is quadratic for the full table and linear for two rows. At the table is million cells; a CPython list stores an 8-byte pointer per cell (small integers are shared objects), so MB of pointers plus list overheads and the integers above 256 that CPython does not cache — 229 MiB in total. In C with 16-bit cells the same table is 32 MB. The two-row version's memory grows linearly (two rows plus the input strings).
  • The crossover that matters is memory, not time. A full table is cells — impossible in RAM in any language — while two rows of are trivial. That is why genome aligners and diff on big files never build the full table.

Dictionary search (50,000 words sampled from /usr/share/dict/words, 200 queries, each a dictionary word with one random letter replaced).

MethodDistance computations per queryTime per query
BK-tree, 1,672 (3.3% of the dictionary)13 ms
BK-tree, 12,545 (25.1%)109 ms
Linear scan, full Levenshtein, 50,000390 ms
Linear scan, bounded Levenshtein, 50,000 (most rejected by length or after a few rows)88 ms

(Building the BK-tree took about 3 s. Timings vary by about ±10% between runs.)

The honest lesson: the BK-tree is excellent for and mediocre for . Edit distances between dictionary words cluster in a narrow range (in a sample of 5,000 random pairs from the same word list, 80% were between 6 and 11 apart), so the window covers a large share of every node's children. And the BK-tree must compute exact distances to decide which edges to follow, while the linear scan can use the banded, early-exit distance, which rejects most words after a length check or a few rows. A cheap linear scan beat the clever index at . Production spell-checkers use different structures altogether: tries with a DP row per node (each shared prefix is computed once), Levenshtein automata (Schulz and Mihov, 2002; used by Lucene's fuzzy queries), or symmetric-delete indexes (SymSpell).

Line breaking. The DP takes well under a millisecond on the 102-word paragraph. Its cost is — each start word tries at most the words that fit on one line — so a 10,000-word chapter at width 72 is about line evaluations.

Extension ideas

  1. Myers' diff. The LCS table costs time even when the files differ in one line. Myers ("An O(ND) Difference Algorithm and Its Variations", Algorithmica 1, 1986) explores the edit graph in order of the number of edits , along diagonals, and takes time — near-linear for similar files. It is the default algorithm in GNU diff and in git diff. Implement it, check that it produces the same number of changed lines as your LCS diff on random inputs, and benchmark both on two versions of a large file. Git's diff options and the history behind them are covered in Git and Diff.
  2. Linear-space diff (Hirschberg). Compute the middle row of the table from both ends with two-row passes, split the problem at the best crossing point, and recurse on the two halves (Hirschberg, "A linear space algorithm for computing maximal common subsequences", CACM 18(6), 1975). Time stays , space drops to , and you still get the full script. Myers' paper uses the same "middle snake" idea.
  3. Patience and histogram diff. Minimal diffs are not always readable diffs: in code, a minimal script often matches lone braces and blank lines and produces confusing hunks. Patience diff (Bram Cohen) first matches lines that are unique in both files, using a longest increasing subsequence, and recurses between them; histogram diff extends it. Both are available as git diff --patience and git diff --histogram. Implement patience diff with the LIS and compare hunks on real code.
  4. Word-level and character-level diff inside changed lines, as code review tools show: run the same DP on tokens within each -/+ pair.
  5. Three-way merge (diff3). Diff a common ancestor against two edited versions and merge non-overlapping hunks; report overlaps as conflicts.
  6. Damerau–Levenshtein distance. Add the transposition move: when and (the "optimal string alignment" variant; Damerau, CACM 7(3), 1964). Now teh → the costs 1. Note that this variant is not a true metric (it breaks the triangle inequality), so check whether your BK-tree still returns exact results — and if it does not, use the unrestricted Damerau–Levenshtein distance, which is a metric.
  7. Frequency and keyboard-aware ranking. Count word frequencies in a corpus and rank suggestions by distance, then frequency. Make substitutions between adjacent keys cheaper (weighted edit distance — same DP, different costs).
  8. A trie-based suggester. Walk a trie of the dictionary, carrying one DP row per node and pruning a branch when the row's minimum exceeds . Compare its work with the BK-tree and the banded scan. See Tries.
  9. Full justification and real typesetting. Print the DP's lines fully justified (spread the spare spaces between words). Then add Knuth–Plass features: stretchable and shrinkable spaces, a penalty for hyphenating, and "demerits" that discourage consecutive very loose and very tight lines.
  10. Faster line breaking. The squared cost satisfies the quadrangle inequality, so the line-breaking DP is a "least weight subsequence" problem solvable in or (Hirschberg and Larmore, 1987; Wilber, 1988). See DP Optimizations.

Further reading: how production tools do it

flowchart LR
    LCSDP["LCS table, O(nm)"] --> HM["Hunt-McIlroy 1976: match lists"]
    LCSDP --> HIR["Hirschberg 1975: linear space"]
    HM --> MY["Myers 1986: O(ND), greedy diagonals"]
    HIR --> MY
    MY --> GIT["git diff: Myers default, patience and histogram options"]
    ED["Edit distance table"] --> BAND["Ukkonen 1985: banded, cutoff"]
    ED --> BIT["Myers 1999: bit-parallel rows"]
    BAND --> LEV["Levenshtein automata: fuzzy search in Lucene"]
  • Unix diff. The original Unix diff used the Hunt–McIlroy algorithm (Hunt and McIlroy, "An Algorithm for Differential File Comparison", Bell Labs Computing Science Technical Report 41, 1976), which computes an LCS from the list of matching line pairs. GNU diff uses Myers' algorithm with heuristics that trade minimality for speed on huge inputs (its --minimal flag turns them off).
  • Git. git diff defaults to Myers and offers --minimal, --patience and --histogram. Patience diff was added to Git in 2009 and histogram diff (ported from JGit) in 2011.
  • Edit distance at scale. Wagner and Fischer, "The String-to-String Correction Problem", JACM 21(1), 1974, is the table algorithm. Ukkonen, "Algorithms for approximate string matching", Information and Control 64, 1985, introduced the band and cut-off ideas. Myers' bit-vector algorithm (JACM 46(3), 1999) computes 64 cells per machine instruction and powers aligners such as Edlib.
  • Spelling. Burkhard and Keller, "Some approaches to best-match file searching", CACM 16(4), 1973 (BK-trees). Damerau, "A technique for computer detection and correction of spelling errors", CACM 7(3), 1964. Peter Norvig's essay "How to Write a Spelling Corrector" (2007) is a 30-line probabilistic corrector worth reading after this capstone.
  • Line breaking. Donald Knuth and Michael Plass, "Breaking paragraphs into lines", Software: Practice and Experience 11(11), 1981 — the algorithm in TeX, with its full cost model.
  • The textbooks. CLRS 4th ed. §14.4 (LCS), Kleinberg and Tardos §6.6–6.7 (sequence alignment and Hirschberg's linear-space alignment), and the "printing neatly" problem at the end of CLRS's dynamic programming chapter, which is Part 3.

Course navigation. Previous: DP Debugging. Module overview: Dynamic Programming. Course: DSA: Zero to Mastery. Next: Module 7, String Algorithms.