How Diff Algorithms Work: Myers Diff, Shortest Edit Script (SES), and Text Comparison Guide

Every software engineer uses diffing tools dozens of times a day. Whether reviewing pull requests on GitHub, running git diff in your terminal, resolving merge conflicts, or diffing JSON responses in API clients, the ability to find minimal differences between two files is fundamental to modern development.

Yet behind the green and red highlighted lines lies an elegant mathematical problem: how do you transform string $A$ into string $B$ with the absolute minimum number of insertions and deletions?

In this educational guide, you will learn how the Myers Diff Algorithm (the default engine behind Git) works under the hood, explore the relationship between Longest Common Subsequences (LCS) and Edit Graphs, and compare code changes using interactive developer tools.

1. The Edit Graph Mental Model#

Eugene Myers formulated the diff problem as a graph search in his landmark 1986 paper, "An $O(ND)$ Difference Algorithm and Its Variations".

Suppose you want to diff two strings:

• String $A$ (Original): ABCABBA (Length $N = 7$)
• String $B$ (Modified): CBABAC (Length $M = 6$)

We construct a 2D grid where the horizontal axis represents characters of $A$ and the vertical axis represents characters of $B$:

Any valid path from $(0,0)$ to $(N,M)$ represents a sequence of edits. The goal is to find the path with the maximum number of diagonal moves (matches) and the minimum number of non-diagonal moves (edits).

2. How the Myers Algorithm Searches Paths#

Naive Breadth-First Search (BFS) on an $N \times M$ grid would take $O(NM)$ time and memory. Myers improved this dramatically by organizing the search by $D$-paths (paths containing exactly $D$ non-diagonal steps) and tracking diagonals $k = x - y$.

Key Properties:#

1. At step $D$, the search reaches diagonals in the range $[-D, D]$ in steps of 2 ($k \in {-D, -D+2, \dots, D-2, D}$).
2. For each diagonal $k$, the algorithm chooses whether to step down from $k+1$ (insertion) or right from $k-1$ (deletion) to maximize the $x$-coordinate.
3. After taking the step, it greedily slides down any available diagonal matches (called the snake) for free ($O(1)$ cost).

Because real-world code edits are usually small relative to file size ($D \ll N$), Myers searches only a narrow corridor of the graph, completing in milliseconds.

3. Implementing a Basic Diff in TypeScript#

Here is a clean implementation of the forward Myers algorithm calculating the Shortest Edit Script (SES):

interface DiffResult {
  operation: 'equal' | 'insert' | 'delete';
  value: string;
}

function myersDiff(a: string[], b: string[]): DiffResult[] {
  const n = a.length;
  const m = b.length;
  const max = n + m;
  const v: Record<number, number> = { 1: 0 };
  const trace: Record<number, Record<number, number>> = {};

  // 1. Forward search for shortest D-path
  for (let d = 0; d <= max; d++) {
    trace[d] = { ...v };
    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]; // Move down (insertion)
      } else {
        x = v[k - 1] + 1; // Move right (deletion)
      }
      let y = x - k;

      // Greedily follow matching diagonal snake
      while (x < n && y < m && a[x] === b[y]) {
        x++;
        y++;
      }
      v[k] = x;

      if (x >= n && y >= m) {
        return backtrackPath(trace, d, a, b);
      }
    }
  }
  return [];
}

4. Understanding Unified Diff Format#

When you run git diff, Git outputs the unified diff format:

@@ -1,4 +1,4 @@
 import React from 'react';
-const API_URL = 'http://localhost:3000';
+const API_URL = 'https://api.joeyjazwinski.com';
 export default function App() {

Breakdown of Hunk Headers @@ -1,4 +1,4 @@:#

• -1,4: Original file starting at line 1, spanning 4 lines.
• +1,4: New modified file starting at line 1, spanning 4 lines.
• - prefix: Deleted line.
• + prefix: Added line.
• Unprefixed space: Context line kept unchanged.

5. Interactive Developer Tools for Code Diffing#

When inspecting file differences, validating JSON payload changes, or preparing release notes, use the built-in developer tools:

• Interactive Diff & Text Comparator: Compare text and code snippets with side-by-side visual highlights and character-level diffs.
• JSON Prettifier & Formatter: Normalize JSON indentation before running diffs to avoid whitespace noise.
• CSV to Markdown Table Converter: Convert spreadsheet records into clean markdown tables for documentation.

The Myers algorithm bridges graph theory and practical software tooling. Understanding its mechanics helps you write better code reviews, optimize build diffing pipelines, and navigate merge conflicts with confidence.