How Diff Algorithms Work — A Visual Guide

Every time you run git diff, compare text online, or review a pull request, a diff algorithm is working behind the scenes. Here's how they actually work.

The Problem: Finding Differences

Given two sequences of text (lines, words, or characters), find the minimum set of changes to transform one into the other. This is fundamentally the Longest Common Subsequence (LCS) problem.

For example, comparing:

Original: "The quick brown fox"
Modified: "The slow brown cat"

The algorithm needs to identify: "quick" → "slow" and "fox" → "cat", while recognizing "The" and "brown" are unchanged.

Approach 1: Naive LCS (O(mn))

The simplest approach uses dynamic programming. Build an m×n matrix where each cell represents whether characters match, then trace back to find the longest common subsequence.

• Time complexity: O(mn) where m and n are the lengths of the two texts
• Space complexity: O(mn) — the full matrix
• Used by: Simple diff tools, educational examples

Approach 2: Myers' Diff Algorithm (O(nd))

Eugene Myers published his seminal algorithm in 1986: "An O(ND) Difference Algorithm and Its Variations." This is what git diff uses.

The key insight: instead of exploring the entire m×n space, only explore paths proportional to the number of differences (d). For similar files (small d), this is dramatically faster.

How it works:

1. Edit graph: Imagine a grid where horizontal moves = delete, vertical moves = insert, diagonal moves = match
2. Greedy search: Extend diagonals as far as possible (matching characters are "free")
3. BFS by edit distance: Search for d=0, then d=1, d=2... until reaching the end

Approach 3: Patience Diff

Used by git diff --patience, this algorithm first finds unique matching lines between the two files, uses those as anchors, then recursively diffs the gaps. It produces more human-readable output, especially for code.

Line vs. Word vs. Character Diff

The algorithm is the same — what changes is the unit of comparison:

• Line diff: Each "token" is a full line. Best for code and structured text.
• Word diff: Tokens are words separated by spaces. Better for prose and documentation.
• Character diff: Every character is a token. Highest granularity, useful for finding typos.

Try all three modes in DiffSnap →

Practical Applications

• Version control: Git, SVN, Mercurial use diff to track changes
• Code review: GitHub, GitLab show diffs in pull requests
• Document comparison: Legal, academic, and editorial workflows
• Testing: Visual regression testing compares screenshots pixel-by-pixel

Try It Yourself

DiffSnap uses the jsdiff library (based on Myers' algorithm) to compute diffs entirely in your browser. Compare text, JSON, CSV, code, or images — all free, all private.