How diff tools work: longest common subsequence and Myers' algorithm

When you compare two versions of a document, a diff tool shows what was removed and what was added. It seems like a simple task, but finding the "right" set of changes is a genuinely interesting problem, and the approach behind it explains why diff output sometimes looks different from what you expected.

The problem diff solves

There are many possible ways to describe how one text turned into another. At the extreme, you could say the entire original was deleted and the entire new version was inserted. That's technically correct but useless. A good diff finds the smallest reasonable set of changes: it keeps as much of the original as possible and marks only what actually differs.

Longest common subsequence

The classic approach is to find the longest common subsequence (LCS): the longest sequence of items that appears in both texts in the same order, though not necessarily next to each other. Those shared items are shown as unchanged. Everything in the original that isn't part of the subsequence is a deletion, and everything in the new version that isn't part of it is an insertion.

For example, comparing the lines A, B, C, D with A, C, D, E, the longest common subsequence is A, C, D. So the diff says: B was removed, and E was added. That's the smallest description of the change.

Myers' algorithm

In 1986, Eugene Myers published an efficient algorithm for finding the shortest set of insertions and deletions between two sequences. It's fast when the two texts are mostly similar, which is the usual case in real editing, and it became the default in tools like GNU diff and Git. The diff library used by this site's diff checker is based on the same approach.

Lines, words, or characters

A diff has to decide what counts as one item. Line diffs treat each line as a unit, which is ideal for code, configuration files, and lists, where lines are meaningful chunks. Word diffs treat each word as a unit, which suits prose: if you change one word in a long paragraph, a line diff marks the whole paragraph as changed, while a word diff highlights only that word. Character diffs go further still, useful for spotting typos or small changes inside identifiers.

Why diffs sometimes look strange

Sometimes there are several equally short ways to describe a change, and the algorithm picks one that isn't the most intuitive. A common example is adding a new block of code that begins and ends with the same line as the block above it; the diff may show the insertion shifted by a line. Some tools apply extra heuristics, such as Git's "patience" and "histogram" diff options, to produce more readable results in those cases.

Whitespace is another common surprise. A trailing space, a tab instead of spaces, or Windows versus Unix line endings will all register as changes even though the text looks identical.

Diffs beyond code

Diff algorithms power far more than code review: tracked changes in word processors, the edit history on wikis, plagiarism detection, comparing contract drafts, and even DNA sequence comparison in bioinformatics, which uses closely related alignment algorithms.

Compare your own text

The diff checker compares two blocks of text in your browser, with both line and word granularity. Try both on the same text to see how much the choice of unit changes the result.