Every time you run git diff, open a pull request on GitHub, or paste two text blocks into a web-based code comparison utility, an algorithm computes the exact additions, deletions, and updates between the old and new texts.
Calculating this difference might seem simple, but doing it in a way that aligns with human intuition and runs efficiently on large files requires clever graph theory. Let's look at the algorithms that power diff tools.
1. What is a Diff?
At its core, computing a diff is the process of finding the shortest sequence of edits (insertions and deletions) to transform String A into String B.
A naive algorithm might compare character-by-character, but this leads to erratic results (for example, matching single characters in unrelated lines, causing a visual mess). Instead, professional diff engines parse the text line-by-line, treating each line as a distinct token.
2. Myers' Diff Algorithm
Invented by Eugene Myers in 1986, Myers' Diff is the default algorithm used by Git. It models the edit problem as finding a path through an **Edit Graph**.
- The Edit Graph: The old text lies on the X-axis (length $N$), and the new text lies on the Y-axis (length $M$). The grid represents all potential edit states.
- Movement Rules: Moving horizontally (right) represents deleting a line from the old text. Moving vertically (down) represents inserting a line from the new text. Moving diagonally (down-right) is free and represents matching lines in both texts.
- The Goal: Find the path from $(0, 0)$ to $(N, M)$ that contains the fewest possible horizontal and vertical steps (deletions and insertions). The algorithm uses a breadth-first search (BFS) optimization to find this path in $O(ND)$ time, where $D$ is the size of the edit script.
3. Levenshtein Distance
Another common string comparison metric is **Levenshtein Distance**, which measures the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into another.
Unlike Myers' algorithm, Levenshtein includes a "substitution" operation (which counts as a single edit step). It is widely used in spellcheckers and search engines, but is less suited for code repositories because developers prefer to see updates explicitly marked as a separate deletion and insertion (red and green lines) rather than an inplace replacement.
4. How Diff Tools Work in the Browser
In browser tools, computing diffs is done client-side using JavaScript libraries like diff (based on Myers' algorithm).
The script splits the inputs by newlines, runs the diff algorithm to tag each line as added, removed, or unchanged, and then outputs HTML table rows. Inline changes (highlighting specific changed words inside a line) are computed by running a second character-level diff on adjacent deleted and inserted lines.