The Computer Science of Diff: Myers Algorithm & Edit Graphs
Determining the minimum set of differences between two sequences of text is a fundamental problem in computer science. In 1986, Dr. Eugene W. Myers published his seminal paper, "An O(ND) Difference Algorithm and Its Variations", establishing the mathematical standard that powers contemporary version control systems including Git, Mercurial, and SVN.
The algorithm translates the comparison of two strings of length $N$ and $M$ into finding the Shortest Edit Script (SES) across a directed grid graph (the edit graph). A diagonal move represents identical lines ($0$ cost), while horizontal and vertical moves represent deletions and insertions ($1$ cost). By performing a breadth-first search along diagonal $K$-lines ($K = X - Y$), Myers finds the optimal edit sequence in $O(ND)$ time, where $D$ is the number of differences.
Comparison of Version Control Diff Algorithms
| Algorithm | Time Complexity | Core Characteristics | Primary Use Cases |
|---|---|---|---|
| Myers Algorithm | O(N × D) | Greedy breadth-first diagonal traversal; guaranteed to find the minimal edit script. | Standard default in Git (git diff), Linux patch utility, and code merge engines. |
| Patience Diff | O(N log N) | Isolates unique, non-repeating lines first to prevent misaligning repeated braces {}. | Heavy refactorings, moved functions, and structured languages with repeated blocks. |
| Histogram Diff | O(N) expected | An optimized variant of Patience Diff that uses frequency histograms to isolate low-occurrence anchors. | Modern Git alternative (--diff-algorithm=histogram) for large repositories. |
| Levenshtein Distance | O(N × M) | Calculates single-character insertions, deletions, and substitutions via dynamic programming matrix. | Spell-checking, fuzzy string matching, and word-level token diffing inside modified lines. |
The Anatomy of a Unified Diff Patch (RFC 4648 & POSIX)
The Unified Diff format groups text revisions into cohesive units called hunks, surrounded by unmodified context lines to assist patch applications:
--- a/src/auth.js (Original file timestamp)
+++ b/src/auth.js (Modified file timestamp)
@@ -14,6 +14,7 @@ function verifyUser(token) {
if (!token) {
- return null;
+ logAuditFailure("Empty token supplied");
+ throw new AuthException("Invalid session");
}
return jwt.decode(token);
}
The hunk header @@ -14,6 +14,7 @@ communicates that the original file began at line 14 for 6 lines, while the modified file begins at line 14 for 7 lines.