Code Diff Algorithms: LCS, Myers and Patience

1. Problem: the nature of text diffs and shortest edit script models

Given source text A (N lines) and target text B (M lines), diff tools identify the minimal sequence of edit operations (insertions and deletions) to transform A into B. Mathematically, this equals finding the Longest Common Subsequence (LCS) or solving for the shortest path from (0,0) to (N,M) in a 2D Edit Graph.

2. Minimal reproduction: Myers Edit Graph shortest path construction

This comparison demonstrates how line comparison maps to 2D grid graph traversal and edit script generation:

/* Source Text A: ["A", "B", "C"]

   Target Text B: ["A", "C", "D"] */

/* 2D Edit Graph Traversal (x = Source index, y = Target index):
   - Rightward (+x): Delete A[x]
   - Downward (+y): Insert B[y]
   - Diagonal (+x,+y): Free diagonal walk when A[x] === B[y] (Keep) */

interface DiffOp {
  type: "keep" | "add" | "delete";
  value: string;
}

const expectedDiff: DiffOp[] = [
  { type: "keep", value: "A" },
  { type: "delete", value: "B" },
  { type: "keep", value: "C" },
  { type: "add", value: "D" }
];
console.log("Shortest Edit Operations Count:", expectedDiff.length);

3. Root cause: LCS dynamic programming, O((N+M)D) Myers, and Patience enhancements

1. LCS Dynamic Programming: traditional DP uses an O(N imes M) matrix. For thousand-line files, space complexity scales quadratically, making it unusable. 2. Myers Greedy Diff: Eugene Myers introduced a greedy D-path search in 1986, optimizing time complexity to O((N+M)D) and space to O(N+M) via divide-and-conquer linear space refinement. Since edit distance D ll N+M in typical code edits, Myers runs in near-linear time. 3. Patience Diff: Myers algorithms can misalign block boundaries on repetitive curly braces or empty lines. Patience Diff matches unique anchor lines first (such as distinct function signatures), producing human-friendly diff output.

4. Recommendation: algorithm selection across scenarios

1. Standard Comparison: adopt Myers Diff as default engine (git diff default) for maximum execution speed. 2. Code Review and Refactoring: enable Patience Diff (git diff --patience) or Histogram Diff (git diff --histogram) on refactored codebases containing rearranged functions.

5. Complete code: pure TypeScript implementation of Myers D-path algorithm

This TypeScript snippet demonstrates computing Shortest Edit Scripts for text lines using Myers' greedy 2D grid algorithm.

interface DiffResult {

  operation: "keep" | "insert" | "delete";
  line: string;
}

function computeMyersDiff(src: string[], dst: string[]): DiffResult[] {
  const N = src.length;
  const M = dst.length;
  const maxD = N + M;
  const V: Record<number, number> = { 1: 0 };
  const trace: Record<number, number>[] = [];

  for (let D = 0; D <= maxD; D++) {
    const vCopy = { ...V };
    trace.push(vCopy);

    for (let k = -D; k <= D; k += 2) {
      let x: number;
      if (k === -D || (k !== D && V[k - 1] < V[k + 1])) {
        x = V[k + 1];
      } else {
        x = V[k - 1] + 1;
      }

      let y = x - k;

      while (x < N && y < M && src[x] === dst[y]) {
        x++;
        y++;
      }

      V[k] = x;

      if (x >= N && y >= M) {
        return backtrackMyersPath(trace, src, dst, N, M);
      }
    }
  }

  return [];
}

function backtrackMyersPath(
  trace: Record<number, number>[],
  src: string[],
  dst: string[],
  N: number,
  M: number
): DiffResult[] {
  const result: DiffResult[] = [];
  let x = N;
  let y = M;

  for (let D = trace.length - 1; D >= 0; D--) {
    const V = trace[D];
    const k = x - y;

    let prevK = (k === -D || (k !== D && V[k - 1] < V[k + 1])) ? k + 1 : k - 1;
    const prevX = V[prevK];
    const prevY = prevX - prevK;

    while (x > prevX && y > prevY) {
      result.unshift({ operation: "keep", line: src[x - 1] });
      x--;
      y--;
    }

    if (D > 0) {
      if (x === prevX) {
        result.unshift({ operation: "insert", line: dst[y - 1] });
      } else {
        result.unshift({ operation: "delete", line: src[x - 1] });
      }
    }

    x = prevX;
    y = prevY;
  }

  return result;
}

const fileA = ["function hello() {", "  console.log('hi');", "}"];
const fileB = ["function hello() {", "  console.log('world');", "}"];
console.log("Myers Diff Result:", computeMyersDiff(fileA, fileB));

6. Incorrect approaches

Using O(N^2) brute-force string matching for large file diffs. Confusing line-level text diffs with Abstract Syntax Tree (AST) diffs. Assuming Myers algorithm always produces the most human-readable output on repetitive code block boundaries.

7. Boundaries: pre-processing via Common Prefix/Suffix Stripping

Before invoking the Myers loop, diff engines apply a fast pre-processing pass: stripping identical leading and trailing line blocks (Common Prefix and Common Suffix). This reduces physical sequence lengths by orders of magnitude.

8. Verification

Benchmark execution times and memory usage on multi-thousand-line files. Verify that calculated diff operations satisfy absolute reconstruction correctness (A \xrightarrow{Diff} B).

9. FAQ

Why does Git default to the Myers algorithm? Myers optimizes execution time to O((N+M)D), running in near-linear time for small edit distances D.

How does Patience Diff differ from Myers Diff? Myers minimizes total edit distance, whereas Patience matches unique anchor lines first to produce human-readable diff blocks.

Is character-level diff identical to line-level diff? The core algorithm is identical; only sequence token granularity differs (characters vs. lines).

10. Summary

Diff algorithms evolved from DP LCS to Myers D-path and Patience refinements. Combining pre-processing pruning with efficient graph traversal is essential for building high-performance diff tools.