Text Diffing Algorithms Explained

Text Diffing Algorithms Explained

Diffing — finding the differences between two texts — is fundamental to version control, code review, and document comparison. Understanding how it works helps you interpret diffs and build better tools.

The Problem

Given two sequences (text A and text B), find the minimum set of operations (insertions, deletions) to transform A into B.

Myers' Diff Algorithm

The most widely used diff algorithm, employed by Git and most diff tools. It finds the shortest edit script (SES) — the minimum number of insertions and deletions.

How It Works

Build an edit graph where moving right = delete from A, moving down = insert from B, moving diagonally = match.

Find the shortest path from top-left to bottom-right using BFS.

The path gives you the optimal edit script.

Time Complexity

O(N * D) where N = total length and D = number of differences. Fast when differences are small.

Diff Granularity

Line-Level

What git diff shows by default. Each line is either added, removed, or unchanged.

Word-Level

Highlights changed words within a line. Better for prose and documentation diffs.

Character-Level

Shows exact character changes. Useful for spotting subtle typos or formatting differences.

Diff Output Formats

Unified Diff

--- a/file.txt
+++ b/file.txt
@@ -1,3 +1,3 @@
 unchanged line
-old line
+new line
 unchanged line

Side-by-Side

Shows old and new versions in parallel columns with aligned changes.

Practical Applications

Code review — understand what changed and why. Context lines help. Merge conflicts — three-way diffs show your changes, their changes, and the common ancestor. Content auditing — track document changes over time. Testing — snapshot testing compares rendered output against a baseline.

Try It

Use our Diff Checker tool to compare two texts with line, word, or character-level diffing, in unified or side-by-side view.

Conclusion

Diff algorithms are elegant solutions to a universal problem. Line-level diffs work for code; word-level diffs work for prose. Understanding the output format helps you review changes faster.