How diff tools work — the algorithm behind 'what changed'

Comparing two versions of a document by eye is slow and error-prone; a diff does it in milliseconds and highlights exactly what changed. The algorithm behind it is one of computer science's neat results and it shapes what a diff can and can't show — which is worth knowing whether you're reviewing a contract in the text diff tool or a code change on GitHub.

The problem: minimal edits

Given an old text and a new one, a diff wants the shortest script of insertions and deletions that turns one into the other — the "edit script". Shortest matters: a diff that deletes everything and inserts everything is technically correct and useless. Finding the shortest is equivalent to finding the longest run of material both versions share, in order, and treating everything else as changed.

Longest common subsequence

The shared material is the longest common subsequence (LCS): the longest sequence of items (lines, usually) that appears in both texts in the same order, not necessarily contiguously. Computing it exactly is a dynamic-programming table of size old × new — fine for documents, slow for huge files — and the standard practical algorithm is Eugene Myers's 1986 method, which finds the edit script in time proportional to the size of the difference, so two nearly identical files diff almost instantly. Git's default diff is a Myers variant; alternatives ("patience", "histogram") choose among equally short scripts the one that looks most sensible to humans, by anchoring on unique lines first.

Lines, words, characters

The unit matters. Line diffs (the default for code) treat any change to a line as replacing the whole line, which is right for code and wrong for prose, where one changed word marks a whole paragraph. Word diffs compare within lines and show the changed words; character diffs go finer and are best for short strings. Most tools do a line diff first and then a word-level pass inside changed lines. Whitespace handling is a separate choice: ignoring it hides reformatting noise and hides accidental changes inside strings; a tool that lets you toggle it is the honest one.

Reading a unified diff

--- old.txt
+++ new.txt
@@ -12,4 +12,5 @@
 unchanged context
-a removed line
+the line that replaced it
+an added line
 more context

The @@ header gives the line ranges in each file; lines beginning with a space are context, − removed, + added. It is the format of patches, pull requests and the output of diff -u, and it is designed so a program can apply it to the old file to produce the new one — which is what "applying a patch" means.

Where diffs fall down

• Moved blocks show as a deletion here and an insertion there; plain diffs don't detect moves.
• Reformatting (re-wrapped paragraphs, re-indented code) swamps the real change; diff after normalising whitespace, or with a word diff.
• Structured data: two JSON files with reordered keys are semantically identical and textually all different — use a structural comparison like JSON diff.
• Binary files and images have no meaningful text diff; compare with checksums (How checksums verify downloads and backups — and which one to use) or visually with the image compare tool.
• Rich documents: Word's track changes is a diff over its own structure; exporting to plain text first (PDF to Word or the reverse) loses formatting changes but gets the words compared.