Text Diff: The Algorithms Behind Line-by-Line and Word-by-Word Text Comparison

In 1974, Paul Heckel published "A Technique for Isolating Differences Between Files" in Communications of the ACM (CACM, Volume 17, Issue 5, May 1974, pp. 264-268), one of the first published algorithms for file comparison. The diff utility itself originated in 1974 as part of the Unix operating system (AT&T Bell Labs), written by James Hunt, who based it on an algorithm by Harold Stone. The foundational improvement came in 1986 when Eugene Myers published "An O(ND) Difference Algorithm and Its Variations" — a paper that reduced diff's time complexity from O(m·n) to O(ND) and remains the basis for nearly every modern diff implementation. The MyToolsList text-diff tool uses Myers' algorithm in pure JavaScript, running entirely in your browser.

Table of Contents

1. How Text Diff Works: LCS and Myers' Algorithm
2. Side-by-Side vs Unified Diff
3. Line-Level vs Word-Level Diff
4. Use Cases: Code Review, Document Comparison, Plagiarism Detection
5. Frequently Asked Questions

How Text Diff Works: LCS and Myers' Algorithm

The fundamental operation of a text diff tool is to find the minimum number of insertions and deletions needed to transform one text into another. This is known as the edit distance problem.

The LCS Algorithm

The Longest Common Subsequence (LCS) of two sequences is the longest sequence that appears as a subsequence in both. For example, the LCS of "ABCDGH" and "AEDFHR" is "ADH" (length 3). The diff between two texts is derived from the LCS — any character in the first text but not in the LCS is a deletion; any character in the second text but not in the LCS is an insertion.

The standard LCS algorithm uses dynamic programming with O(m·n) time and space:

function lcs(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n]; // length of LCS
}

For text diff, the same algorithm is applied line-by-line (treating each line as a single "character" in the LCS). The dp table tracks the longest matching prefix of lines; reconstructing the path from the bottom-right corner yields the diff: lines that are in the LCS are unchanged, lines missing from the first text are additions, and lines missing from the second text are deletions.

Myers' O(ND) Algorithm

Myers' 1986 algorithm improves on LCS for typical inputs where the edit distance D is small relative to N (the input length). Instead of building the full m·n dp table, Myers works on the edit graph — a 2D grid where moving right represents deletion from text1, moving down represents insertion to text2, and moving diagonally represents a match.

// Simplified Myers' algorithm (sketch)
function myersDiff(a, b) {
  const N = a.length, M = b.length;
  const max = N + M;
  const v = new Array(2 * max + 1).fill(0);
  const trace = [];

  for (let d = 0; d <= max; d++) {
    trace.push([...v]);
    for (let k = -d; k <= d; k += 2) {
      const x = k === -d || (k !== d && v[k - 1] + 1 < v[k + 1])
        ? v[k + 1]
        : v[k - 1] + 1;
      let y = x - k;
      while (x < N && y < M && a[x] === b[y]) { x++; y++; }
      v[k] = x;
      if (x >= N && y >= M) return backtrack(trace, a, b, k, d);
    }
  }
}

The algorithm finds the shortest path from (0,0) to (N,M) through the edit graph, which corresponds to the minimum edit sequence. Time complexity is O(ND) where D is the edit distance — for typical inputs with few changes, D is small and the algorithm runs in near-linear time.

Side-by-Side vs Unified Diff

The two standard diff presentation formats have distinct advantages:

Side-by-side diff displays the two texts in adjacent columns. Lines present in both texts appear on the same row in both columns. Lines present only in text1 (deletions) appear with a red highlight in the left column; lines present only in text2 (additions) appear with a green highlight in the right column.

Unified diff combines both texts into a single column. Lines present in both texts are unmarked (or marked with a space prefix). Lines present only in text1 are marked with - and highlighted red. Lines present only in text2 are marked with + and highlighted green.

Format	Strengths	Weaknesses	Common Uses
Side-by-side	Visual comparison; easy to spot changes	Wider screen required	Document review, content editing
Unified	Compact, patch-compatible	Harder to scan large diffs	Git commits, code review, patch files

The unified diff format was standardized as part of POSIX (IEEE Std 1003.1-2008) for the diff and patch utilities. A unified diff can be applied with patch < changes.diff to transform one file into another — this is the foundation of source-code patch distribution.

Line-Level vs Word-Level Diff

The MyToolsList text-diff tool supports three granularity modes:

1. Line-level (default): The diff highlights entire lines as added, removed, or unchanged. This is the standard for source code comparison where line-by-line changes are the norm.
2. Word-level: Within each changed line, individual words are highlighted as added or removed. Useful for prose where rewording is common.
3. Character-level: Within each changed line, individual characters are highlighted. The most granular mode, useful for detecting small text changes.

Word-level diff uses a second LCS pass over each changed line:

function wordDiff(line1, line2) {
  const words1 = line1.split(/(\s+)/); // split keeping whitespace
  const words2 = line2.split(/(\s+)/);
  const lcsLength = lcs(words1, words2);
  return reconstructDiff(words1, words2, lcsLength);
}

For example, given the lines:

• text1: "The quick brown fox jumps"
• text2: "The slow brown fox leaps"

Word-level diff would highlight "quick" → "slow" (replacement) and "jumps" → "leaps" (replacement) while showing "The", "brown", "fox" as unchanged.

Use Cases: Code Review, Document Comparison, Plagiarism Detection

Code review: Comparing two versions of source code is the original use case for diff tools. Git, GitHub, GitLab, Bitbucket, and Phabricator all use Myers-based diff algorithms for displaying pull-request changes. Line-level diff is standard; word-level diff is occasionally used for prose comments.

Document comparison: Legal contracts, editorial drafts, policy documents. Side-by-side view with word-level granularity makes rewording immediately visible. Microsoft Word's "Compare Documents" feature, Google Docs' "Version history," and macOS Preview's PDF comparison all implement diff algorithms.

Plagiarism detection: Comparing a submission against a reference corpus requires fast pairwise diff. Tools like Turnitin (founded 1998) and Copyscape (founded 2004) use fingerprint-based approaches (shingling, hashing) rather than full diff for performance, but the underlying problem is the same.

Configuration management: Comparing configuration files (JSON, YAML, INI) across environments (dev, staging, production). Tools like kubectl-diff, terraform plan, and ansible --diff use Myers-style diff to highlight configuration drift.