Implementing the Myers Diff Algorithm in TypeScript — Character-Level Precision

While developers regularly use git diff, few understand the underlying algorithm. I built a browser-based text comparison tool using the Myers diff algorithm with character-level highlighting within changed lines for precise difference visualization.

Try it at devprix.dev/tools/diff-checker.

The Problem

Find the minimum set of insertions and deletions to transform one text into another, then display the differences in a way that's immediately understandable.

Naive approaches produce technically correct but confusing diffs. Myers' algorithm, published in 1986, solves this optimally by finding the "shortest edit script" while preferring diagonal moves (matching lines), producing results that align with human intuition.

The Myers Algorithm

The Edit Graph

The algorithm visualizes differences on a 2D grid where the X-axis represents lines from the old text and the Y-axis represents lines from the new text. Rightward movement means deletion, downward movement means insertion, and diagonal movement (when lines match) means retention.

D-Path Exploration

The algorithm explores paths by edit distance d. At d = 0, it follows diagonals (matching lines) as far as possible. At d = 1, it tries one insertion or deletion, then follows diagonals. This continues incrementally until reaching the bottom-right corner.

The core data structure uses v — a map from diagonal index k to the furthest x coordinate reached:

const n = oldLines.length;
const m = newLines.length;
const max = n + m;

const vHistory: Map<number, number>[] = [];
const v = new Map<number, number>();
v.set(1, 0);

for (let d = 0; d <= max; d++) {
  vHistory.push(new Map(v));

  for (let k = -d; k <= d; k += 2) {
    let x: number;
    if (k === -d || (k !== d && (v.get(k - 1) ?? 0) < (v.get(k + 1) ?? 0))) {
      x = v.get(k + 1) ?? 0;
    } else {
      x = (v.get(k - 1) ?? 0) + 1;
    }
    let y = x - k;

    while (x < n && y < m && oldLines[x] === newLines[y]) {
      x++;
      y++;
    }

    v.set(k, x);

    if (x >= n && y >= m) {
      return backtrack(vHistory, d, n, m);
    }
  }
}

Why Diagonals Matter

The while loop performs greedy diagonal extension. When lines match, movement is "free" with no edit cost. This approach maximizes unchanged lines, making diffs feel natural and intuitive.

Backtracking

The algorithm stores the entire v map at each depth in vHistory. After finding the endpoint, it backtracks from (n, m) through the history to reconstruct the edit path.

Beyond Line Diffs: Character-Level Highlighting

Line-level diffs show which lines changed but not what changed within them. For "modified" lines (deleted then replaced), the implementation uses a second pass with LCS (Longest Common Subsequence) for character-level precision.

Pairing Modified Lines

Consecutive deletions followed by consecutive insertions are paired as modified lines:

- const x = 42;      -> modified (old)
+ const x = 99;      -> modified (new)

LCS for Character Diffing

For each modified pair, the algorithm computes LCS character-by-character:

function charDiff(oldStr: string, newStr: string): CharDiff[] {
  const oldChars = Array.from(oldStr);
  const newChars = Array.from(newStr);
  const n = oldChars.length;
  const m = newChars.length;

  const dp: number[][] = Array.from({ length: n + 1 }, () =>
    Array(m + 1).fill(0)
  );

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (oldChars[i - 1] === newChars[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]);
      }
    }
  }

  const lcs: [number, number][] = [];
  let i = n, j = m;
  while (i > 0 && j > 0) {
    if (oldChars[i - 1] === newChars[j - 1]) {
      lcs.unshift([i - 1, j - 1]);
      i--; j--;
    } else if (dp[i - 1][j] >= dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  return lcs;
}

Characters in the LCS are unchanged, those in the old string but not in LCS are removed, and characters in the new string but not in LCS are added.

Merging Consecutive Segments

Raw character diffs produce one segment per character. To avoid excessive span elements, consecutive segments of the same type are merged:

function mergeSegments(segments: CharDiff[]): CharDiff[] {
  const merged: CharDiff[] = [];
  for (const seg of segments) {
    if (merged.length > 0 && merged[merged.length - 1].type === seg.type) {
      merged[merged.length - 1].text += seg.text;
    } else {
      merged.push({ ...seg });
    }
  }
  return merged;
}

Preprocessing Without Losing Context

The tool supports filtering modes for whitespace, case sensitivity, and trailing whitespace. The key is preprocessing for comparison while displaying original content:

function preprocessLine(line: string, options: Options): string {
  let processed = line;
  if (options.trimTrailing) processed = processed.replace(/\s+$/, "");
  if (options.ignoreWhitespace) processed = processed.replace(/\s+/g, " ").trim();
  if (options.ignoreCase) processed = processed.toLowerCase();
  return processed;
}

Myers runs on preprocessed lines, but the displayed diff shows original text.

Unified Diff Export

The tool exports standard unified diff format compatible with git apply:

--- a/original
+++ b/modified
@@ -1,7 +1,6 @@
 unchanged line
-removed line
+added line
 unchanged line

Hunks are grouped with three lines of context around changes, matching git's default behavior.

Rendering: Side-by-Side vs Unified

Side-by-side uses CSS Grid with three columns: 1fr 1px 1fr, with a vertical divider. Modified lines display on both sides with character highlighting — red for removed characters, green for added.

Unified view shows a single column with +/- prefixes, matching git diff format.

What I Learned

Diagonal preference is essential. Greedy diagonal extension produces readable diffs that feel natural to humans.

Two-level diffing is critical. Line-level changes show locations; character-level shows content modifications. Without the second pass, single-character changes appear as complete line replacements.

Separation of concerns matters. Comparing normalized text while displaying originals applies broadly to fuzzy matching scenarios.

---

This is part of DevPrix — 63 free developer tools that run entirely in your browser. No sign-up, no tracking, no server calls.