Understanding Diff Algorithms and Patch Workflows
The math and mechanics of calculating text differences: Longest Common Subsequences, Myers algorithm, and unified diff syntax.
The Longest Common Subsequence (LCS) Problem
At the core of any diff tool is finding what remained unchanged between two versions of a document. This is mathematically formulated as the Longest Common Subsequence (LCS) problem.
By identifying the elements that both versions share in order, the differences can be represented as a minimal sequence of insertions and deletions.
The Myers Diff Algorithm
Published by Eugene Myers in 1986, the Myers algorithm is the default engine behind `git diff` and standard Unix `diff`. It treats difference calculation as finding the shortest path on an edit graph.
Myers operates in O((N+M)D) time, where N and M are line counts and D is the number of edits. For typical code files where edits are small compared to total file length, it executes almost instantaneously.
Anatomy of a Unified Diff
Unified format combines differences into a single stream with context lines. It starts with file headers (`--- original` and `+++ modified`), followed by hunk headers like `@@ -1,5 +1,6 @@`.
Lines prefixed with ` ` (space) are unchanged context. Lines prefixed with `-` are deleted, and lines prefixed with `+` are inserted.
Applications Beyond Code Reviews
Diff algorithms are not limited to Git commits. Modern software uses diffing for API payload drift detection, database schema migrations, collaborative real-time editing (Operational Transformation / CRDTs), and client-side form change tracking.