A program that compares two texts does not read them and decide "what changed" the way a person does. Instead, it looks for the smallest number of deletions and insertions that turn one list into the other. This guide explains how diff computes that answer, and why the result sometimes differs from what a person would expect.
Units of comparison: lines, words, characters
diff first splits the text into a list of tokens. Traditional diff and git treat each line as one token. That is why changing a single character in a line shows the whole line as "1 line deleted + 1 line added".
Line-based comparison is fast and fits code review well, but in documents where a long paragraph sits on one line, it is hard to see what actually changed. So many tools compare in two stages.
- Compare line by line to find the changed lines.
- Pair up the changed lines and compare their contents again by word or character.
This site works the same way. For the in-line comparison you can choose words, space-separated chunks, or characters.
Longest common subsequence (LCS)
The mathematical core of diff is the longest common subsequence (LCS). A subsequence is what you get by picking some elements while keeping their order. For example, the longest common subsequences of ABCABBA and CBABAC have length 4; CABA and BABA are two of them.
Elements in the LCS are "what stayed the same"; everything else is either "deleted" (only on the left) or "added" (only on the right). The longer the LCS, the fewer deletions and additions are needed. If the two lists have lengths N and M and the LCS has length L, the total number of deletions and additions D is:
D = (N - L) + (M - L)In the example above, N=7, M=6, and L=4, so D = 3 + 2 = 5. This D is called the edit distance (when only insertions and deletions are allowed), and the list of deletions and additions is called the edit script.
The edit graph and the Myers algorithm
Computing the LCS the textbook way (dynamic programming) requires an N×M table. Comparing two 10,000-line files means 100 million cells, which is slow and memory-hungry. In 1986, Eugene W. Myers presented a faster method in the paper "An O(ND) Difference Algorithm and Its Variations", and it became the foundation of the default algorithms in GNU diff and git today.
Myers turns comparison into finding the shortest path on a grid.
- You travel from the top-left corner (0,0) to the bottom-right corner (N,M).
- One step right = delete one element of the left text; one step down = add one element of the right text. Each costs 1.
- Where the two elements are equal, you can move diagonally for free. A run of such diagonal moves is called a snake.
The cheapest path is the shortest edit script. The Myers algorithm keeps extending "the farthest point reachable with cost 0", "the farthest point reachable with cost 1", and so on, and stops when it reaches the end. At each step it only needs to remember the farthest position on each diagonal, so the running time is roughly proportional to (N+M)×D. When the two texts are nearly identical, D is small and it is very fast; when they are completely different, it slows down.
Linear memory and the middle snake
To trace the path back, you have to keep a record for each step, so memory can grow in proportion to D². In the same paper, Myers also presented a variant that runs a forward search from the start and a backward search from the end at the same time and finds the diagonal segment where they meet (the middle snake). Splitting the problem into two smaller ones at that point and repeating uses memory only in proportion to the input size.
When it gets too expensive: approximation heuristics
When both inputs are tens of thousands of lines long and differ a lot, D grows too, and (N+M)×D can reach billions. GNU diff guards against this with a heuristic: if the search goes past a certain number of steps, it cuts the problem at the diagonal that has advanced the farthest so far. The result is still a correct edit script, but it is no longer guaranteed to be the shortest. The --minimal option in GNU diff and in git makes it find the minimal result even if that takes longer.
Minimal is not always the most readable
There can be several paths with the same edit distance. For example, when you add a function to code, there are closing braces } and blank lines in many places, so the algorithm may pair "the new function's }" with "an existing function's }". The result is minimal but looks awkward to a person. That is why git uses a heuristic by default that shifts boundaries based on indentation, and offers other algorithms such as patience and histogram. They are compared in detail in Comparing diff algorithms.
In this tool
This site's comparison engine implements the linear-memory variant of the Myers algorithm in JavaScript, and switches to approximate splitting in the same way as GNU diff when the input is large. The computation runs in a Web Worker, so the page does not freeze even with large files. Once the line-level result is ready, changed lines with similar content are paired and marked as "modified", and their contents are compared once more in the unit you chose (word, space-separated chunk, or character) and highlighted.
Try putting in two texts in the Text Diff Checker and see how the result changes as you switch the in-line diff unit. To read the result in git format, see How to read a unified diff.