From Red Pens to Algorithms: The Stakes Behind Text Comparison

The Algorithm Behind the Comparison

Douglas McIlroy and James Hunt developed the first practical text comparison utility at Bell Labs in the early 1970s, and it became part of the fifth edition of Unix in June 1974. Their published paper from 1976 introduced what became known as the Hunt-McIlroy algorithm, later refined into the Hunt-Szymanski algorithm. The mathematical problem they were solving has a formal name: the longest common subsequence problem.

The longest common subsequence is the longest list of elements that appear in both texts, in the same order, without necessarily being adjacent. For two pieces of text, the longest common subsequence is the foundation of the comparison: once you find what both versions share, everything in the first text that is not in that shared sequence is a deletion, and everything in the second text that is not in it is an addition.

This is more difficult than it sounds. A 100-line document has nearly 10^30 possible pairings of subsequences to evaluate in naive brute-force comparison. Hunt and McIlroy's algorithm brought this to tractable time. Eugene Myers published further improvements in 1986 with his O(ND) algorithm, and modern version control systems like Git use a further refinement called the histogram diff algorithm, which handles common real-world code patterns more gracefully than Myers' original.

None of this is visible to a person pasting two texts into a comparison tool. They see additions highlighted in green and deletions in red. Behind that display, the tool solved a combinatorics problem that stumped computer scientists for years.

Redlining's Hidden Failure Rate

Before automated diffing became standard in legal practice, the redlining process was the final quality gate on contract language. Its failure rate was not zero.

A single word change -- reasonable efforts versus best efforts -- carries entirely different legal standards in American contract law. A missed change in a force majeure clause can determine whether a party can exit a contract during a pandemic. The stakes of a missed diff are not typographical.

This is why automated document comparison became one of the first serious applications of computer text processing in professional services. Legal tech companies built comparison tools directly into word processors in the 1990s. Microsoft Word's Track Changes feature, which appeared in Word 6 in 1994, was essentially a user-facing implementation of the same longest common subsequence logic applied in real time as the document was edited, storing each edit rather than comparing two finished versions after the fact.

The consequence of this automation is that a task that once required an hour of a junior lawyer's time now happens in a second. The discipline of attention that used to be demanded from a human reader -- holding two versions of a clause in memory simultaneously and identifying whether they are identical -- has been delegated to an algorithm.

When a One-Word Change Changes Everything

The practical importance of text comparison extends well past contract law. Translators comparing source text and translated output catch omissions that would otherwise reach publication. Academic journal editors comparing a submitted manuscript against a revised version verify that authors addressed reviewer comments without quietly removing other parts of the paper. Software developers reviewing a pull request need to see not just that a function was modified but exactly which lines were modified -- and diff output structured into unified patches has been the mechanism for this since Larry Wall created the patch utility in 1984.

What all these use cases share is a concern with the difference between two states of the same thing. Not a general sense of whether a document changed, but a precise, line-by-line accounting. Human readers are good at absorbing meaning from text; they are poor at detecting changes in familiar text, because the brain's reading process is predictive -- it recognizes patterns rather than reading every character independently. This is why proofreaders often read text backwards, disrupting the predictive flow that causes the eye to skip over familiar material.

An algorithm has no predictive reading strategy to disrupt. It compares every token. It reports every mismatch. The Hunt-McIlroy algorithm published in 1976 did not care whether the changed word was shall or may or reasonable or best. It reported the substitution identically regardless of the legal or practical stakes of that substitution. That indifference to content is precisely its value.

The next time you paste two texts into a comparison tool and watch the changes appear highlighted, you are using mathematics that began at Bell Labs, was formalized in a 1976 research paper, was refined for speed across four subsequent decades, and was applied to contracts, manuscripts, code, and every other domain where version control is a matter of consequence.

Conclusion

For documents where the difference matters, ToolHQ's Text Diff Checker compares two text blocks and highlights every change -- additions, deletions, and substitutions -- with no upload required.

Frequently Asked Questions

Try These Free Tools