The Fundamental Challenge of Computing Differences
Comparing two versions of a document or source code file seems intuitive to human eyes. We scan for changed words, deleted paragraphs, and newly inserted lines.
For a computer, however, a naive comparison between two text files of N and M lines requires exploring an exponential number of permutations. The goal of a difference algorithm is to compute the Shortest Edit Script (SES): the minimal sequence of line insertions (+) and deletions (-) required to transform string A into string B.
The Myers Difference Algorithm (1986)
Published by Eugene W. Myers in his landmark paper "An O(ND) Difference Algorithm and Its Variations", the Myers algorithm remains the default diff engine powering Git, Unix diff, and modern code review platforms.
Visualizing Diffing as an Edit Graph
Myers modeled text comparison as traversing a directed grid called an Edit Graph:Edit Graph Coordinate Grid:
Line in String B (Insertions: Moving DOWN)
b_1 b_2 b_3 b_4
(0,0)───>(0,1)───>(0,2)───>(0,3)───>(0,4)
│ │ │ │ │
a_1 │ ╲ │ │ │ │
(Deletes)▼ ╲ ▼ ▼ ▼ ▼
(1,0)───>(1,1)───>(1,2)───>(1,3)───>(1,4)
│ │ ╲ │ │ ╲ │
a_2 ▼ ▼ ╲ ▼ ▼ ╲ ▼
(2,0)───>(2,1)───>(2,2)───>(2,3)───>(2,4)
Horizontal move (x -> x+1): Deletion of line a_x
Vertical move (y -> y+1): Insertion of line b_y
Diagonal move (x,y -> x+1,y+1): Match (Free cost! No change)
- Horizontal Step (Cost = 1): Moving right from (x, y) to (x+1, y) corresponds to deleting a line from file A.
- Vertical Step (Cost = 1): Moving down from (x, y) to (x, y+1) corresponds to inserting a line into file B.
- Diagonal Step (Cost = 0 - Free!): If line A[x+1] equals line B[y+1], we can slide down the diagonal at zero cost because the lines are identical.
Greedy Breadth-First Diagonal Traversal
The Myers algorithm performs a greedy search across diagonal lines k = x - y. For each edit distance D = 0, 1, 2, \dots, it finds the furthest-reaching point along each diagonal k. Because matching lines are traversed along diagonals at zero cost, the search reaches the destination (N, M) in O(ND) time, where D is the number of differences between the files.Line-by-Line vs. Word-by-Word Granularity
Different diffing use cases require different granularities:
Private, Zero-Server Text Comparison on ToolHero
Uploading confidential business contracts, patent drafts, or proprietary source code to cloud diff websites creates substantial IP leakage risks.
ToolHero's Text Diff Checker performs line-by-line and character-level diffing entirely in local browser memory. No text is ever uploaded or retained, giving you enterprise-grade text comparison with complete confidentiality.