The core problem is easy to state: given two sequences A and B, find the smallest number of insertions and deletions that turn A into B. That word "smallest" is what decides which of several possible alignments a diff tool shows you.
Longest common subsequence
Almost every diff algorithm rests on one idea: the longest common subsequence (LCS).
Take the part of A and B that appears in both, in the same order, without requiring it to be contiguous. Whatever is left over is what changed. A small example:
A: A B C D E
B: A C D F EThe common subsequence is A C D E, length 4. So the extra F in B is an insertion and the extra B in A is a deletion.
Computing the LCS directly with dynamic programming costs O(n×m). For two files of ten thousand lines each, that is hundreds of millions of operations — visibly slow in a browser.
So real implementations cut corners
Practical diff algorithms find leverage in a few directions.
Strip the common prefix and suffix first
The simplest optimisation is often the most effective. If the two texts share their first 5,000 lines and their last 3,000, skip both and run the algorithm only over the middle. In everyday use this removes the overwhelming majority of the work.
Find the shortest path through an edit graph
Picture the comparison as a grid: moving right means deleting, moving down means inserting, and moving diagonally means the two items are equal. The goal is to walk from the top-left corner to the bottom-right one while taking as many diagonal steps as possible.
Myers' 1986 algorithm is built on exactly this graph. It prunes using the observation that the number of paths reaching a given edit distance is bounded, bringing the average cost close to O(nd), where d is the number of actual differences. The fewer the changes, the faster it runs — which is precisely the common case.
Two passes, not one
A good diff tool works at two levels:
- Line level. Decide which lines were added or removed. This establishes the overall alignment.
- Word level. Run the comparison again inside each changed line, this time over words or characters, and highlight only what really moved.
Without the second pass, an entire line is marked as deleted-plus-added, and changing a single comma looks indistinguishable from rewriting the sentence. It also explains why word level is the usual granularity for that second pass: characters are too fine, lines are too coarse.
Why the result sometimes looks wrong
Back to the opening question. A diff algorithm returns the answer with the fewest edits — and "fewest edits" is not always "what a human would call correct".
A typical example: you indent a whole block of code by two extra spaces. From the algorithm's point of view every line changed, and the cheapest way to express that is "delete everything, add everything". What a person wants to see is "the indentation changed". This is exactly why mature diff tools offer an ignore-whitespace option: it removes that noise from the algorithm's input rather than asking the algorithm to guess your intent.
Reordered blocks are hard for the same reason. The algorithm only understands sequence; it cannot tell whether you moved a section or deleted the old one and wrote a new one, so a move appears as one deletion plus one insertion.
To feel this for yourself, try the indentation, line-break and punctuation cases in the diff checker, then flip the ignore options on and compare.