warming up your workspace

Build your own diff, the algorithm you stare at every day

You look at a diff dozens of times a day: the red-minus and green-plus lines in a pull request, the output of git diff, the side-by-side in your editor's merge tool. It feels like the computer just noticed which lines changed. But "which lines changed" is a genuinely hard question, because there are many ways to explain how one file became another, and diff has to find the simplest one. The answer is one of the most elegant algorithms in everyday use, and it rests entirely on a single idea you can build from scratch.

The one idea

To diff two files, first find the lines they have in common, in order, keeping as many as possible. That is the longest common subsequence: the longest list of lines that appear in both files in the same relative order, not necessarily adjacent. Once you know the longest shared skeleton, everything else is forced. Lines in the old file but not in the skeleton were deleted. Lines in the new file but not in the skeleton were added. Lines in the skeleton are unchanged. So the whole diff reduces to "find the biggest thing they share", and minimizing the changes is the same as maximizing the overlap.

Build the table

Longest common subsequence is the textbook dynamic-programming problem. Build a table where L[i][j] is the length of the longest shared subsequence of the old file from line i onward and the new file from line j onward. If the two current lines match, that is one shared line plus whatever the rest shares. If not, you skip a line from one side or the other, whichever leaves more in common.

def lcs_table(a, b):
    n, m = len(a), len(b)
    L = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n-1, -1, -1):
        for j in range(m-1, -1, -1):
            L[i][j] = (L[i+1][j+1] + 1 if a[i] == b[j]
                       else max(L[i+1][j], L[i][j+1]))
    return L

Three details that matter:

  • The unit is a whole line, not a character. Diff hashes each line and compares hashes, which is why line-based diff is fast even on huge files and why reformatting that changes every line produces a giant, useless diff, every line is a different "letter".
  • The max(L[i+1][j], L[i][j+1]) on a mismatch is the entire decision: is it better to consider this old line deleted, or this new line added? The table computes both futures and keeps the better one, so the final diff is provably minimal.
  • The table is filled from the bottom-right corner backward, so each cell can read the answers it depends on. This is the same reuse-subproblems pattern behind edit distance and sequence alignment.

Walk the table to emit the diff

With the table built, walk forward from the top-left. Matching lines are unchanged; otherwise the table tells you whether to record a deletion or an addition.

def diff(a, b):
    L = lcs_table(a, b)
    i = j = 0; out = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            out.append(("  ", a[i])); i += 1; j += 1     # in both: unchanged
        elif L[i+1][j] >= L[i][j+1]:
            out.append(("- ", a[i])); i += 1             # only in old: deleted
        else:
            out.append(("+ ", b[j])); j += 1             # only in new: added
    while i < len(a): out.append(("- ", a[i])); i += 1
    while j < len(b): out.append(("+ ", b[j])); j += 1
    return out

Proof: it produces the diff you would draw by hand

  import os
+ import sys
  def main():
-     print('hi')
+     print('hello')
      return 0

That is exactly right. import os, def main():, and return 0 are the shared skeleton and stay unmarked. import sys was added, so it is a plus. The print line changed, which diff correctly represents as the old one deleted and the new one added, because line diff has no notion of "edited", only removed and inserted. Cross-checking against Python's own difflib on the same input gives the identical set of plus and minus lines: your 20 lines agree with the standard library.

Where this shows up

This is the core of git diff, of every code-review tool, and of the three-way merge that decides whether your pull request has a conflict. Production diffs use a smarter variant, the Myers algorithm, which finds the same minimal answer without building the whole quadratic table, so it scales to large files, but the definition of "best diff" is exactly the longest-common-subsequence one you just built. The same idea powers document comparison, DNA alignment, and the autocorrect that measures how far one word is from another.

If you want to build the Myers algorithm, three-way merge, and the patch format that turns a diff into something you can apply, that is the path the general-coding track on IWTLP builds next.