Every Diff Is a Shortest-Path Problem: Myers and the LCS
Nearly every diff you have ever read — git diff, GNU diff, the output below — descends from a single 1986 paper: Eugene Myers' "An O(ND) Difference Algorithm and Its Variations". The problem it solves is finding the shortest edit script: the minimum number of line insertions and deletions that turn text A into text B. That is mathematically the same problem as finding the longest common subsequence (LCS) — the longest series of lines appearing in both texts in the same order, not necessarily adjacent. Lines in the LCS become unchanged context; everything else is a red minus or a green plus.
Myers models the two texts as an edit graph: moving right deletes a line from A, moving down inserts a line from B, and a free diagonal move is available wherever the lines match. The shortest edit script is the cheapest path from corner to corner, and the algorithm explores it greedily, one edit at a time. The O(ND) name is the key property: N is the total length and D the number of differences, so the algorithm is extremely fast when the texts are similar — the common case for revisions of the same document — and only degrades when the two inputs share almost nothing.
One subtlety worth knowing: the shortest script is usually not unique. Several different diffs can all have the minimum edit count, and which one you see depends on tie-breaking inside the implementation. That is why two diff tools can both be "correct" yet render different output for the same input pair.
old: A B C A B B A new: C B A B A C
LCS: C A B A (longest common subsequence, length 4)
shortest edit script (D = 5 edits):
-A -B C +B A B -B A +C
del del keep ins keep keep del keep ins → C B A B A CPatience Diff: When the Shortest Diff Is Not the Clearest
Optimal is not the same as readable. Myers minimizes edit count, but code is full of repeated lines — closing braces, blank lines, "end", "return nil" — and the algorithm happily matches your new function's closing brace against a different function's closing brace, because to the algorithm they are identical lines. The classic symptom is inserting a new function above an existing one and getting a diff where the boundary between the two functions is drawn in a nonsensical place: technically minimal, humanly wrong.
Bram Cohen's patience diff attacks this by refusing to anchor on noise. It first considers only lines that appear exactly once in both files — function signatures, distinctive statements — finds the longest increasing subsequence of those unique matches (via patience sorting, the card game that names the algorithm), locks them in as anchors, and recurses between anchor pairs. Braces and blank lines can no longer act as false anchors because they are not unique. The result is sometimes a few edits longer than Myers, but aligned with the semantic structure a human sees.
Histogram diff, git's refinement of the same idea, extends anchoring to low-occurrence (not strictly unique) lines and is faster in practice; it powers JGit and is a popular choice for git config diff.algorithm. Try git diff --patience or --histogram the next time a diff of moved or duplicated code looks scrambled — same input, dramatically different story.
# Same change, two algorithms
git diff file.py git diff --patience file.py
def totals(): def totals():
return sum(rows) return sum(rows)
+
+def averages(): +def averages():
+ return sum(rows)/n + return sum(rows)/n
+ +
def render(): def render():
# Myers may anchor on the shared 'return sum(rows)' line and
# split the new function across the old one; patience anchors
# on the unique 'def' lines and keeps each function intact.Line, Word, Character: Choosing the Right Granularity
Line-based diff is the default because code changes line-wise and because it is cheap: hashing whole lines shrinks each file to a short sequence of tokens before the expensive algorithm runs. But line granularity has a blind spot — change one character in a 300-character line and the diff reports the entire line as removed and re-added, leaving you to play spot-the-difference by eye.
The fix used by code review tools is a two-pass diff: a line-level pass finds which lines changed, then a character- or word-level pass runs only on each removed/added line pair to produce the inline highlight. Running character-level diff on entire files directly is rarely worth it — the edit graph grows quadratically with input length, and single-character alignments across unrelated lines produce noise rather than insight. Git exposes the word-level view as git diff --word-diff (token output) and --color-words (inline coloring), both invaluable for prose, Markdown, and translations where a "line" is really a paragraph.
The third axis is structural. Two JSON documents can be semantically identical yet textually different — key order, indentation, trailing commas — so a text diff of raw JSON mostly measures formatting. The robust workflow is to normalize first: run both documents through the same formatter (stable key order, fixed indentation), then diff. The same trick applies to SQL, XML, and code formatted by different tools; for code there are even AST-level differs like difftastic that ignore formatting entirely. A diff is only as meaningful as the normalization you did before it.
Whitespace, Line Endings, and Other Invisible Differences
The most confusing diffs are the ones where both sides look identical. The usual suspect is line endings: Windows tools write CRLF (\r\n) while Unix writes LF, so a file saved once on the wrong OS shows every single line as changed. Git's defenses are core.autocrlf and, better, a committed .gitattributes with explicit eol rules so the whole team normalizes the same way. In raw diff output a stray carriage return often shows up as ^M at line ends.
Trailing spaces and tab-versus-space indentation are the second family. Standard flags exist to suppress them: diff -b ignores changes in the amount of whitespace, diff -w ignores whitespace entirely, and git diff supports -w, -b, and --ignore-blank-lines. These are inspection tools, not fixes — if whitespace noise pollutes your diffs, fix the source with a formatter and an .editorconfig rather than permanently diffing with -w, because in Python or YAML that "noise" can be a real semantic change.
The third family is Unicode. A non-breaking space (U+00A0) pasted from a web page, a zero-width space (U+200B), or a byte order mark (U+FEFF) at the start of a file will all cause mismatches while rendering exactly like their plain counterparts. Similarly, an accented character can be one code point (NFC) or a base letter plus combining mark (NFD) — macOS file APIs famously produce NFD. When a diff flags a line you cannot see a difference in, stop trusting your eyes and hexdump both lines; the answer is always in the bytes.
# Both lines render as "hello" — the bytes disagree
$ printf 'hello \n' | xxd # trailing space: ...6f 20 0a
$ printf 'hello\r\n' | xxd # CRLF ending: ...6f 0d 0a
# Ignore whitespace while investigating
git diff -w # all whitespace
git diff -b --ignore-blank-lines # amount + blank lines
# Normalize line endings for the whole team (.gitattributes)
* text=auto
*.sh text eol=lfReading Unified Diff Output Like a Native
The unified format — invented for GNU diffutils and universal since git adopted it — packs a lot of information into a few sigils. A hunk header like @@ -117,6 +117,8 @@ reads: this hunk covers 6 lines of the original starting at line 117, and 8 lines of the new version starting at line 117. The counts include the unchanged context lines (three above and three below by default, tunable with -U). Since a replaced line is one minus plus one plus, added-minus-removed always equals the difference between the two counts — a quick sanity check when hand-editing patches.
Two markers trip people up. The text after the second @@ is not part of the diff; it is the enclosing function or section heading, provided as orientation. And the line "\ No newline at end of file" is not literal content — it flags that the preceding line lacks a trailing newline, which is why appending a final newline to a file produces a two-line diff for a one-character change.
Understanding hunks also demystifies patching. The patch and git apply tools do not use line numbers blindly: they search for the context lines near the stated position, applying with an offset when the file has shifted, and with fuzz when context partially matches — which is how a patch written against last week's file can still apply today. It is also why context matters in merges: a three-way merge conflict (<<<<<<< / ======= / >>>>>>>) is exactly the case where the same context region received two different hunks, and git diff3 style (merge.conflictStyle = diff3) adds the common ancestor between the markers so you can see what both sides changed from.
@@ -117,6 +117,8 @@ function render() {
const rows = fetchRows(); ← context (3 lines above)
const total = sum(rows);
- return format(total); ← removed from old file
+ const avg = total / rows.length;
+ return format(total, avg); ← added in new file
}
// counts: old 6 = 3+1+2 ctx, new 8 = 3+2+2 ctx +1
\ No newline at end of file