Diff Algorithm

A diff algorithm computes the difference between two sequences, typically text files, producing an edit script that transforms one into the other. The canonical diff algorithm, developed by Eugene Myers in 1986 and deployed in Unix diff, is a linear-space refinement of the edit distance dynamic programming approach that finds the longest common subsequence (LCS) between two sequences.

Myers' Algorithm

Myers' algorithm reformulates the LCS problem as a shortest-path problem in the edit graph. Instead of filling the entire DP matrix, it explores diagonals outward from the origin, tracking the furthest-reaching point on each diagonal for each possible edit distance. This reduces space complexity from O(nm) to O(n+m) while maintaining O(nm) worst-case time complexity. In practice, when the sequences are similar, the algorithm runs in near-linear time.

The key insight is that the edit graph has a regular structure: horizontal moves are deletions, vertical moves are insertions, and diagonal moves are matches. The shortest path from the origin to the target corner is the edit script of minimal length. The algorithm is greedy in the sense that it always pushes the furthest point on each diagonal as far as possible, but it is exact in that it is guaranteed to find the optimal path.

Applications Beyond Version Control

While diff is most commonly associated with version control systems like Git, its applications extend far beyond software engineering. In genomics, diff algorithms align DNA sequences to reference genomes. In computational linguistics, they align parallel texts for translation memory systems. In law, they compare contract versions. In biology, they track lineage divergence.

The diff algorithm is also the ancestor of modern document comparison tools, three-way merge algorithms, and patch management systems. The patch format, which encodes the diff output, is a universal language of textual transformation.

Diff as a Model of Change

The diff algorithm does not merely describe change; it provides a minimal model of it. The edit script it produces is the shortest sequence of operations that transforms one state into another. This is not just a computational convenience; it is an epistemological claim. The diff algorithm assumes that change is additive: that the difference between two things can be represented as a sequence of insertions and deletions.

This assumption is powerful but not universal. Some forms of change — structural reorganization, simultaneous multi-point mutation, topological transformation — cannot be naturally represented as a diff. The diff algorithm is a model of linear, sequential change, and like all models, it makes some changes visible and others invisible.

The diff algorithm assumes that the best way to understand the difference between two things is to find the minimal sequence of insertions and deletions that transforms one into the other. This is a powerful assumption, but it is an assumption nonetheless. Not all change is additive. Some differences are better understood as simultaneous transformations or structural reorganizations that no edit script can capture. The diff algorithm is a lens, and like all lenses, it distorts what it reveals.