Myers Diff Algorithm

A high-performance, TypeScript implementation of the Myers diff algorithm. This library provides efficient text comparison capabilities with optimal edit distance calculation and multiple output formats. While the implementation is pure TypeScript and can be used in any JavaScript/TypeScript environment, the project uses Deno for benchmarking and testing.

Table of Contents

• Features - Key capabilities and highlights
• Installation - Setup and installation instructions
• Quick Start - Get up and running in minutes
• API Reference - Complete function documentation
• Types - TypeScript interface definitions
• Performance - Benchmarks and performance characteristics
• Real-World Examples - Practical usage scenarios
• Testing - How to run tests and validate functionality
• Benchmarking - Performance testing and analysis
• Algorithm Details - Deep dive into Myers algorithm implementation
• License - MIT license information

Features

• O(ND) Complexity: Implements the optimal Myers diff algorithm
• Multiple Output Formats: Human-readable diff and unified patch format
• Unicode Support: Proper handling of emoji and international characters
• Thorough Testing: 13 test cases covering edge cases and real-world scenarios

Installation

git clone https://github.com/NeaByteLab/Myers-Diff
cd Myers-Diff

Quick Start

import { computeDiff, formatDiff, formatPatch } from './src/index.ts'

// Basic usage
const oldText = 'Hello world'
const newText = 'Hello universe'

const result = computeDiff(oldText, newText)
console.log('Edit distance:', result.editDistance) // 1
console.log('Number of edits:', result.edits.length) // 2

// Format as readable diff
const diff = formatDiff(result)
console.log(diff)
// Output:
//   Hello
// - world
// + universe

// Format as unified patch
const patch = formatPatch(result, 'old.txt', 'new.txt')
console.log(patch)
// Output:
// --- old.txt
// +++ new.txt
// @@ -1,1 +1,1 @@
// -Hello world
// +Hello universe

API Reference

computeDiff(oldText: string, newText: string): DiffOutput

Computes the difference between two text strings using the Myers algorithm.

Parameters:

• oldText - The original text to compare
• newText - The modified text to compare

Returns: DiffOutput containing:

• edits: DiffEdit[] - Array of edit operations
• editDistance: number - Minimum number of operations to transform old to new

Example:

const result = computeDiff('ABCABBA', 'CBABAC')
console.log(result.editDistance) // 2
console.log(result.edits.length) // 2

diffLines(oldLines: DiffLine[], newLines: DiffLine[]): DiffOutput

Computes the difference between two arrays of diff lines. Useful when you have pre-processed line data.

Parameters:

• oldLines - Array of original diff lines
• newLines - Array of modified diff lines

Returns: Same as computeDiff

formatDiff(result: DiffOutput): string

Formats diff output as a human-readable string with +, -, and `` prefixes.

Example:

const result = computeDiff('hello', 'world')
const formatted = formatDiff(result)
// Output:
// - hello
// + world

formatPatch(result: DiffOutput, oldFileName?, newFileName?, oldTimestamp?, newTimestamp?): string

Formats diff output as a unified patch format compatible with git diff and patch tools.

Parameters:

• result - The diff output to format
• oldFileName - Name of the original file (default: 'old')
• newFileName - Name of the modified file (default: 'new')
• oldTimestamp - Timestamp for the original file (optional)
• newTimestamp - Timestamp for the modified file (optional)

Example:

const result = computeDiff('hello', 'world')
const patch = formatPatch(result, 'old.txt', 'new.txt')
// Output:
// --- old.txt
// +++ new.txt
// @@ -1,1 +1,1 @@
// -hello
// +world

Types

interface DiffOutput {
  readonly edits: DiffEdit[]
  readonly editDistance: number
}

interface DiffEdit {
  readonly type: 'equal' | 'delete' | 'insert'
  readonly oldLine: DiffLine | undefined
  readonly newLine: DiffLine | undefined
}

interface DiffLine {
  readonly number: number
  readonly text: string
}

Performance

Based on thorough benchmarks, this implementation provides excellent performance:

Scenario	Performance	Notes
Small changes (100 chars)	~2.5µs	Sub-microsecond for minor changes
Medium changes (1000 chars)	~19µs	Very fast for typical text
Large changes (1000 lines)	~23ms	Handles large files efficiently
Identical content	~791ns	Optimized for no-change scenarios
Unicode content	~273ns	Proper emoji and international support

Performance Characteristics

• Best Case: Identical content (~791ns)
• Average Case: Mixed changes (~86µs)
• Worst Case: Completely different content (~1.4µs)
• Memory Usage: Scales linearly with input size

Real-World Examples

Code Refactoring

const oldCode = `function calculateTotal(items) {
  let total = 0
  for (const item of items) {
    if (item.price > 0) {
      total += item.price * item.quantity
    }
  }
  return total
}`

const newCode = `function calculateTotal(items, taxRate = 0.1) {
  let total = 0
  let tax = 0

  for (const item of items) {
    if (item.price > 0) {
      const subtotal = item.price * item.quantity
      total += subtotal
      tax += subtotal * taxRate
    }
  }

  return {
    subtotal: total,
    tax: tax,
    total: total + tax
  }
}`

const result = computeDiff(oldCode, newCode)
console.log(`Edit distance: ${result.editDistance}`) // 10
console.log(`Number of edits: ${result.edits.length}`) // 15

Documentation Updates

const oldDoc = `# Project Documentation

## Overview
This project implements a simple calculator.`

const newDoc = `# Advanced Calculator Documentation

## Overview
This project implements an advanced calculator with scientific operations.`

const result = computeDiff(oldDoc, newDoc)
const patch = formatPatch(result, 'README.md', 'README.md')
console.log(patch)

Testing

The project includes thorough Deno test coverage:

# Run all tests
deno test --no-check

# Run specific test file
deno test tests/basic.test.ts --no-check
deno test tests/complex.test.ts --no-check

Test Coverage:

• ✅ Basic functionality (8 tests)
• ✅ Complex scenarios (5 tests)
• ✅ Edge cases (empty strings, identical content)
• ✅ Unicode support
• ✅ Performance benchmarks
• ✅ Memory usage validation

Benchmarking

Run Deno performance benchmarks:

# Run all benchmarks
deno bench benchmark/ --no-check

# Run specific benchmark file
deno bench benchmark/basic.bench.ts --no-check
deno bench benchmark/comprehensive.bench.ts --no-check
deno bench benchmark/performance.bench.ts --no-check

Benchmark Categories:

• Basic functionality tests
• Thorough performance analysis
• Memory usage validation
• O(ND) complexity verification

Project Structure

src/
├── index.ts      # Main API exports
├── Types.ts      # TypeScript type definitions
└── Utils.ts      # Core algorithm implementation

tests/
├── basic.test.ts     # Basic functionality tests
└── complex.test.ts   # Complex scenario tests

benchmark/
├── basic.bench.ts           # Basic performance tests
├── comprehensive.bench.ts   # Thorough benchmarks
└── performance.bench.ts     # Performance analysis

Code Quality

This project maintains high code quality standards using Deno's excellent development tooling:

• TypeScript Strict Mode: All strict type checking enabled via Deno
• Thorough Linting: 25+ Deno linting rules enforced
• Code Formatting: Consistent 2-space indentation, single quotes via deno fmt
• Error Handling: Proper error messages and bounds checking
• Documentation: JSDoc comments for all public functions
• Deno Configuration: Proper deno.json with tasks, imports, and compiler options

Algorithm Details

This implementation uses the Myers diff algorithm, a sophisticated dynamic programming approach that finds the shortest edit sequence between two sequences with optimal O(ND) complexity.

Mathematical Foundation

The Myers algorithm operates on the principle of edit graphs and snake detection. Given two sequences A and B of lengths n and m respectively, the algorithm constructs an edit graph where:

• Horizontal edges represent deletions from sequence A
• Vertical edges represent insertions into sequence B
• Diagonal edges represent matches between sequences A and B

The goal is to find the shortest path from (0,0) to (n,m) in this edit graph.

Core Mathematical Concepts

1. Diagonal Representation

The algorithm uses a diagonal coordinate system where:

• k = x - y represents the diagonal number
• x is the position in sequence A
• y is the position in sequence B

This transforms the 2D problem into a 1D problem along diagonals.

2. Dynamic Programming Recurrence

For each diagonal k and edit distance d, the algorithm maintains:

V[k, d] = maximum x such that there exists a path from (0,0) to (x, y)
          with exactly d edits, where y = x - k

The recurrence relation is:

V[k, d] = max(V[k-1, d-1] + 1, V[k+1, d-1])

3. Snake Detection

After computing V[k, d], the algorithm extends along diagonal k to find the longest common subsequence:

while (x < n && y < m && A[x] == B[y]):
    x++, y++

This "snake" represents the longest diagonal path from the current position.

Implementation Details

Bipolar Array Data Structure

The algorithm uses a custom BipolarArray<T> to efficiently handle negative diagonal indices:

// Mathematical mapping: index k maps to array position
if (k < 0) {
  array[capacity + k] = value // Negative indices
} else {
  array[k] = value // Positive indices
}

This allows O(1) access to diagonals k ∈ [-max, +max] where max = n + m.

Algorithm Complexity Analysis

Time Complexity: O(ND) where:

• N = n + m (total sequence length)
• D = edit distance (number of differences)

Space Complexity: O(N) for the bipolar array

Best Case: O(N) when sequences are identical (D = 0) Worst Case: O(N²) when sequences are completely different (D = N)

Mathematical Proof of Optimality

The Myers algorithm is optimal because:

1. Monotonicity: V[k, d] ≤ V[k, d+1] for all k, d
2. Reachability: If a path exists with d edits, it will be found
3. Minimality: The first path found has the minimum edit distance

Step-by-Step Algorithm Execution

1. Initialization:

   V[0, 0] = 0
   max = n + m
   

2. For each edit distance d from 0 to max:

   For k = -d to +d (step 2):
       Compute V[k, d] using recurrence
       Extend snake along diagonal k
       If (x ≥ n and y ≥ m): return trace
   

3. Backtracking: Reconstruct the optimal edit sequence by tracing back through the V array

Mathematical Example

Consider sequences A = "ABCABBA" and B = "CBABAC":

Edit Graph Visualization:
     C  B  A  B  A  C
   ┌─────────────────
 A │ ↘ ↘ ↘ ↘ ↘ ↘ ↘
 B │ ↘ ↘ ↘ ↘ ↘ ↘ ↘
 C │ ↘ ↘ ↘ ↘ ↘ ↘ ↘
 A │ ↘ ↘ ↘ ↘ ↘ ↘ ↘
 B │ ↘ ↘ ↘ ↘ ↘ ↘ ↘
 B │ ↘ ↘ ↘ ↘ ↘ ↘ ↘
 A │ ↘ ↘ ↘ ↘ ↘ ↘ ↘

The algorithm finds the optimal path with edit distance 2, representing:

• Delete "A" from position 0
• Insert "C" at position 0

Implementation Walkthrough

The mathematical concepts are implemented in the following key functions:

findShortestEdit() - Core Algorithm Implementation

export function findShortestEdit(oldLines: DiffLine[], newLines: DiffLine[]): AlgorithmState[] {
  const n = oldLines.length // Length of sequence A
  const m = newLines.length // Length of sequence B
  const max = n + m // Maximum possible edit distance

  // Bipolar array for diagonal storage: V[k, d] = max x on diagonal k with d edits
  const v = new BipolarArray<number>(2 * max + 1, 0)
  const trace: AlgorithmState[] = []

  for (let d = 0; d <= max; d++) { // Try edit distances 0 to max
    trace.push({ v: v.copy(), d }) // Save state for backtracking

    for (let k = -d; k <= d; k += 2) { // Diagonals k = -d to +d
      let x: number

      // Recurrence relation: V[k, d] = max(V[k-1, d-1] + 1, V[k+1, d-1])
      if (k === -d || (k !== d && v.get(k - 1) < v.get(k + 1))) {
        x = v.get(k + 1) // From diagonal k+1
      } else {
        x = v.get(k - 1) + 1 // From diagonal k-1
      }

      let y = x - k // y = x - k (diagonal constraint)

      // Snake detection: extend along diagonal while characters match
      while (x < n && y < m && oldLines[x]?.text === newLines[y]?.text) {
        x += 1
        y += 1
      }

      v.set(k, x) // Store maximum x reached

      // Termination condition: reached end of both sequences
      if (x >= n && y >= m) {
        return trace
      }
    }
  }
}

findBacktrack() - Optimal Path Reconstruction

export function findBacktrack(
  oldLines: DiffLine[],
  newLines: DiffLine[],
  trace: AlgorithmState[]
): DiffEdit[] {
  let x = oldLines.length // Start from end of sequence A
  let y = newLines.length // Start from end of sequence B
  const edits: DiffEdit[] = []

  // Trace backwards through the algorithm states
  for (let i = trace.length - 1; i >= 0; i--) {
    const { v, d } = trace[i]
    const k = x - y // Current diagonal

    // Determine which diagonal we came from
    let prevK: number
    if (k === -d || (k !== d && v.get(k - 1) < v.get(k + 1))) {
      prevK = k + 1 // Came from diagonal k+1
    } else {
      prevK = k - 1 // Came from diagonal k-1
    }

    const prevX = v.get(prevK)
    const prevY = prevX - prevK

    // Add equal operations for the snake portion
    while (x > prevX && y > prevY) {
      x -= 1
      y -= 1
      edits.push(createEdit('equal', oldLines[x], newLines[y]))
    }

    // Add the edit operation (insert or delete)
    if (d > 0) {
      if (x === prevX) {
        edits.push(createEdit('insert', undefined, newLines[prevY]))
      } else if (y === prevY) {
        edits.push(createEdit('delete', oldLines[prevX], undefined))
      }
      x = prevX
      y = prevY
    }
  }

  return edits.reverse() // Reverse to get correct order
}

Mathematical Complexity Analysis

The implementation achieves optimal complexity through:

1. Bipolar Array: O(1) access to diagonals k ∈ [-max, +max]
2. Snake Detection: O(min(n,m)) per diagonal, but amortized O(1) in practice
3. Early Termination: Stops as soon as optimal path is found
4. Space Optimization: Only stores necessary diagonal values

Actual Performance: The implementation often performs better than theoretical O(ND) due to:

• Snake detection reducing effective search space
• Early termination when sequences are similar
• Efficient memory access patterns

This mathematical foundation ensures the algorithm finds the shortest edit sequence efficiently, making it ideal for version control, text editing, and change detection applications.

License

MIT License - see LICENSE file for details.