Myers Difference Algorithm Implementation

This repository contains a robust, cross-language implementation of the Myers Difference Algorithm, optimized for calculating, applying, and simulating structural differences between iterables (such as strings or arrays).

It includes identical, drop-in implementations for both JavaScript and Python.

Features

• Efficient Diffing: Uses the classic Myers Shortest Edit Script (SES) algorithm to find the minimum number of insertions and deletions between two sequences.
• Prefix/Suffix Optimization: Automatically strips identical prefixes and suffixes before running the core algorithm, significantly improving performance on long sequences with localized changes.
• Unified Instruction Set: Returns diffs as a flat, easy-to-read list of instructions in the format [startIndex, endIndex, replacement].
• Instruction Application: Includes a utility to apply generated diff instructions to target iterables to reconstruct the new sequence.
• Instruction Simulation (Transformation): Includes an advanced simulate method. This allows you to transform an old diff instruction so that it remains contextually valid after a new set of instructions has been applied to the same sequence (similar to Operational Transformation).
• Cross-Language Compatibility: Both Python and JavaScript versions expose the exact same API and produce identical output arrays/tuples.

Usage

1. Calculating Diffs (diff)

The diff method takes an old iterable and a new iterable and returns a list of instructions required to transform the old into the new.

JavaScript:

const oldStr = "The quick brown fox";
const newStr = "The fast brown ninja";

const instructions = Myers.diff(oldStr, newStr);
// Result: [
//   [4, 9, "fast"], 
//   [15, 19, "ninja"]
// ]

Python

old_str = "The quick brown fox"
new_str = "The fast brown ninja"

instructions = Myers.diff(old_str, new_str)
# Result: [(4, 9, 'fast'), (15, 19, 'ninja')]

2. Applying Instructions (apply)

The apply method takes an iterable and a list of instructions, and applies them sequentially.

JavaScript:

const result = Myers.apply("The quick brown fox", [
    [4, 9, "fast"], 
    [15, 19, "ninja"]
]);
console.log(result); // "The fast brown ninja"

Python

result = Myers.apply("The quick brown fox", [
    (4, 9, 'fast'), 
    (15, 19, 'ninja')
])
print(result) # "The fast brown ninja"

3. Simulating/Transforming Instructions (simulate)

If you have concurrent edits, you can map an old instruction to its new position after another set of instructions has been applied.

JavaScript:

// We want to replace "fox" at index 16
const myOldInstruction = [16, 19, "wolf"]; 

// But someone else already inserted "very " at index 4 (shifting the string by 5)
const priorEdits = [[4, 4, "very "]]; 

const updatedInstruction = Myers.simulate(myOldInstruction, priorEdits);
// Result: [21, 24, "wolf"] (The start and end index shifted by +5)

Python

my_old_instruction = (16, 19, "wolf")
prior_edits = [(4, 4, "very ")]

updated_instruction = Myers.simulate(my_old_instruction, prior_edits)
# Result: (21, 24, "wolf")

API Reference

static diff(oldIterable, newIterable, equals)

• oldIterable: The original string or array.
• newIterable: The new string or array.
• equals: (Optional) A custom equality function (a, b) => boolean. Defaults to strict equality (=== or ==).
• Returns: An array/list of tuples [start, end, replacement]. start is inclusive, end is exclusive.

static apply(iterable, instructions)

• iterable: The starting string or array.
• instructions: An array/list of [start, end, replacement] tuples.
• Returns: A new string or mutated array with the instructions applied.

static simulate(oldInstruction, instructions)

• oldInstruction: A single [start, end, replacement] tuple, or a list of such tuples.
• instructions: A list of [start, end, replacement] tuples representing changes that have already occurred.
• Returns: A new instruction tuple (or list of tuples) mapped to the new coordinate space.