Myers diff algorithm in Python
Computes a shortest edit script in O((n + m) D) time, where D is the edit distance.
- File
myers_diff.py, 66 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/myers-diff/. The authors are listed in prov/245ETE.jsonl.
from collections.abc import Sequence
from typing import TypeVar
T = TypeVar("T")
def furthest_points(a: Sequence[T], b: Sequence[T]) -> list[dict[int, int]]:
"""Return the rows V_0, ..., V_D; V_d[k] is the largest x reached on diagonal k = x - y at cost d."""
m, n = len(a), len(b)
v = {1: 0} # @line L1
rows: list[dict[int, int]] = []
for d in range(m + n + 1): # @line L2
row: dict[int, int] = {}
for k in range(-d, d + 1, 2): # @line L3
if k == -d or (k != d and v[k - 1] < v[k + 1]): # @line L4
x = v[k + 1]
else:
x = v[k - 1] + 1 # @line L5
y = x - k # @line L6
while x < m and y < n and a[x] == b[y]: # @line L7
x, y = x + 1, y + 1
v[k] = x # @line L8
row[k] = x
rows.append(row)
if any(x >= m and x - k >= n for k, x in row.items()): # @line L9
return rows
raise AssertionError("unreachable: d = m + n always reaches (m, n)")
def edit_distance_indel(a: Sequence[T], b: Sequence[T]) -> int:
"""Return D, the least number of insertions and deletions that turn a into b."""
return len(furthest_points(a, b)) - 1
def diff(a: Sequence[T], b: Sequence[T]) -> list[tuple[str, T]]:
"""Return a shortest edit script as a list of ('=', item), ('-', item) and ('+', item)."""
m, n = len(a), len(b)
rows = furthest_points(a, b)
ops: list[tuple[str, T]] = []
x, y = m, n # @line L10
for d in range(len(rows) - 1, 0, -1): # @line L11
prev = rows[d - 1]
k = x - y
if k == -d or (k != d and prev[k - 1] < prev[k + 1]): # @line L12
pk = k + 1
else:
pk = k - 1
px = prev[pk]
py = px - pk
sx, sy = (px, py + 1) if pk == k + 1 else (px + 1, py) # @line L13
while x > sx: # @line L14
x, y = x - 1, y - 1
ops.append(("=", a[x]))
if pk == k + 1: # @line L15
ops.append(("+", b[py]))
else:
ops.append(("-", a[px]))
x, y = px, py
while x > 0: # @line L16
x, y = x - 1, y - 1
ops.append(("=", a[x]))
ops.reverse()
return ops
test_myers_diff.py 62 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/myers-diff/. The authors are listed in prov/245ETE.jsonl.
import random
from myers_diff import diff, edit_distance_indel, furthest_points
def lcs_length(x: str, y: str) -> int:
c = [[0] * (len(y) + 1) for _ in range(len(x) + 1)]
for i in range(1, len(x) + 1):
for j in range(1, len(y) + 1):
if x[i - 1] == y[j - 1]:
c[i][j] = c[i - 1][j - 1] + 1
else:
c[i][j] = max(c[i - 1][j], c[i][j - 1])
return c[len(x)][len(y)]
def apply(ops: list) -> tuple[list, list]:
old = [item for op, item in ops if op in "=-"]
new = [item for op, item in ops if op in "=+"]
return old, new
def test_example() -> None:
a, b = "ABCABBA", "CBABAC"
assert edit_distance_indel(a, b) == 5
assert furthest_points(a, b)[2] == {-2: 2, 0: 2, 2: 3}
ops = diff(a, b)
assert "".join(op for op, _ in ops) == "--=+==-=+"
assert apply(ops) == (list(a), list(b))
def test_edges() -> None:
assert diff("", "") == []
assert diff("abc", "abc") == [("=", "a"), ("=", "b"), ("=", "c")]
assert edit_distance_indel("abc", "") == 3
assert edit_distance_indel("", "abc") == 3
assert edit_distance_indel("abc", "xyz") == 6
assert edit_distance_indel("kitten", "sitting") == 5
def test_lines() -> None:
old = ["def f():", " return 1", ""]
new = ["def f():", " x = 1", " return x", ""]
ops = diff(old, new)
assert apply(ops) == (old, new)
assert sum(op != "=" for op, _ in ops) == 3
def test_random_against_lcs() -> None:
rng = random.Random(1986)
for _ in range(800):
a = "".join(rng.choice("ABC") for _ in range(rng.randrange(14)))
b = "".join(rng.choice("ABC") for _ in range(rng.randrange(14)))
ops = diff(a, b)
dist = len(a) + len(b) - 2 * lcs_length(a, b)
assert edit_distance_indel(a, b) == dist
assert sum(op != "=" for op, _ in ops) == dist
old, new = apply(ops)
assert "".join(old) == a and "".join(new) == b
What the next level needs
- the tests did not run in this build