Text Diff & Patch: Myers Algorithm and Online Diff Tools

TextText processing tools

Diff: Difference Computation Is Everywhere

From Git version control to code review, from config changes to data synchronization — diffing is a fundamental operation in software development.

Scenario Diff Type Tool
Code changes Line-level diff Git
Config comparison Key-value diff Online diff tools
JSON data Structural diff json-diff
Legal documents Semantic diff Specialized tools
Translation proofreading Character-level diff Online diff tools

1. How the Myers Diff Algorithm Works

The Core Idea

The Myers algorithm finds the Shortest Edit Script (SES) that transforms the source text into the target text — the fewest insertions and deletions.

Source: ABCABBA
Target: CBABAC

Edit script:
- A    (delete A)
  B    (keep B)
- C    (delete C)
  C    (keep C → insert C before it)
  A    (keep A)
  B    (keep B)
- B    (delete B)
  A    (keep A)
+ C    (insert C)

Algorithm Diagram

      0   1   2   3   4   5   6   7
  ┌───┬───┬───┬───┬───┬───┬───┬───┐
0 │ → │ ↘ │   │   │   │   │   │   │  A
  ├───┼───┼───┼───┼───┼───┼───┼───┤
1 │ ↓ │   │ ↘ │   │ → │ ↘ │   │   │  B
  ├───┼───┼───┼───┼───┼───┼───┼───┤
2 │   │ ↓ │   │ ↘ │ ↓ │   │ ↘ │   │  C
  ├───┼───┼───┼───┼───┼───┼───┼───┤
3 │   │   │ ↓ │   │   │ ↓ │   │ ↘ │  A
  ├───┼───┼───┼───┼───┼───┼───┼───┤
4 │   │   │   │ ↓ │ ↘ │   │ ↓ │   │  B
  ├───┼───┼───┼───┼───┼───┼───┼───┤
5 │   │   │   │   │ ↓ │   │   │ ↓ │  B
  ├───┼───┼───┼───┼───┼───┼───┼───┤
6 │   │   │   │   │   │ ↓ │ ↘ │   │  A
  └───┴───┴───┴───┴───┴───┴───┴───┘
    C   B   A   B   A   C   B   A

→ = move right (delete)  ↓ = move down (insert)  ↘ = diagonal (keep)

Time Complexity

Case Complexity Notes
Best O(ND) N = text length, D = number of differences
Worst O((N+M)D) Completely different texts
Typical O(N+D²) Few differences

2. Comparing Text with the Toolbox

Steps

  1. Open the Text Diff Tool
  2. Paste the original text on the left
  3. Paste the modified text on the right
  4. Review the differences:
    • Red: deleted lines
    • Green: added lines
    • Yellow: modified lines
  5. Supports character-level diff highlighting, precise down to every character change

Comparison Modes

Mode Granularity Best For
Line-level Compare by line Code changes
Word-level Compare by word Document revisions
Character-level Compare by character Precise proofreading

3. Special Techniques for JSON Diff

Using the JSON Diff Tool

  1. Open the JSON Diff Tool
  2. Paste two JSON documents
  3. Review the structural differences:
    • Added / removed / modified keys
    • Value changes (including type changes)
    • Nested paths

JSON Diff vs Text Diff

// Original
{ "name": "张三", "age": 25, "tags": ["a", "b"] }

// Modified
{ "name": "张三", "age": 26, "tags": ["a", "c"], "email": "z@test.com" }
Comparison Method Result
Text Diff Shows line-by-line differences — hard to interpret
JSON Diff age: 25→26, tags[1]: "b"→"c", +email: "z@test.com"

4. The Unified Diff Format

Format Specification

--- a/config.json
+++ b/config.json
@@ -1,5 +1,6 @@
 {
   "name": "my-project",
-  "version": "1.0.0",
+  "version": "2.0.0",
   "description": "A tool",
-  "private": true
+  "private": true,
+  "license": "MIT"
 }
Symbol Meaning
--- Original file
+++ Modified file
@@ -a,b +c,d @@ Hunk location (b lines starting at line a in the original, d lines starting at line c in the modified file)
- Deleted line
+ Added line
(space) Context line

5. Generating and Applying Patches

Generating a Patch

import * as Diff from 'diff';

const oldText = 'Hello World\nGoodbye World';
const newText = 'Hello World\nGoodbye Cruel World';

// Generate a patch
const patch = Diff.createPatch('file.txt', oldText, newText, 'old', 'new');
console.log(patch);

Output:

--- old/file.txt
+++ new/file.txt
@@ -1,2 +1,2 @@
 Hello World
-Goodbye World
+Goodbye Cruel World

Applying a Patch

// Apply forward
const result = Diff.applyPatch(oldText, patch);

// Apply in reverse (rollback)
const reversed = Diff.applyPatch(newText, Diff.reversePatch(patch));

Three-Way Merge

const base = 'original text';
const branchA = 'changes from A';
const branchB = 'changes from B';

const merged = Diff.mergeDiff3(base, branchA, branchB);
// Merges automatically; conflicts are marked with <<<<<<< / ======= / >>>>>>>

6. Real-World Use Cases

Config File Change Detection

const oldConfig = JSON.parse(fs.readFileSync('config.old.json', 'utf-8'));
const newConfig = JSON.parse(fs.readFileSync('config.new.json', 'utf-8'));

const diff = Diff.diffJson(oldConfig, newConfig);
diff.forEach(part => {
  if (part.added) console.log('Added:', JSON.stringify(part.value, null, 2));
  if (part.removed) console.log('Removed:', JSON.stringify(part.value, null, 2));
});

Translation File Proofreading

// Check key consistency between Chinese and English translations
const zhKeys = Object.keys(flatten(zhTranslation));
const enKeys = Object.keys(flatten(enTranslation));

const missingInEn = zhKeys.filter(k => !enKeys.includes(k));
const missingInZh = enKeys.filter(k => !zhKeys.includes(k));

API Response Regression Testing

const expected = await fs.readFile('fixtures/expected.json', 'utf-8');
const actual = await fetch('/api/data').then(r => r.json());

const diff = Diff.diffJson(JSON.parse(expected), actual);
if (diff.some(d => d.added || d.removed)) {
  throw new Error('API response does not match expectations');
}

7. Performance Optimization

Strategy Effect Best For
Limit context lines Smaller output Large files
Hash preprocessing Skip identical lines Very large files
Chunked comparison Parallel processing Very long texts
Line-level before character-level Less computation Code files 
// Limit context lines
const patch = Diff.createPatch('file', old, new, '', '', { context: 3 });
#Diff#文本对比#Patch#Myers#代码审查