Wagner-Fischer algorithm in Python
O(nm) dynamic program filling the edit-distance table row by row.
- File
wagner_fischer_algorithm.py, 70 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/wagner-fischer-algorithm/. The authors are listed in prov/ZX8DFX.jsonl.
"""Levenshtein distance by the Wagner-Fischer dynamic program.
The edit model is unit cost: insertion, deletion and substitution each cost 1,
and there are no transpositions. Indices are 0-based.
"""
def edit_table(x: str, y: str) -> list[list[int]]:
"""Return the table D with D[i][j] = distance of x[:i] and y[:j].
Precondition: none. Cost: Theta(len(x) * len(y)) time and space.
"""
m, n = len(x), len(y)
d = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): # @line L1
d[i][0] = i
for j in range(n + 1): # @line L2
d[0][j] = j
for i in range(1, m + 1): # @line L3
for j in range(1, n + 1): # @line L4
c = 0 if x[i - 1] == y[j - 1] else 1 # @line L5
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + c) # @line L6
return d
def edit_distance(x: str, y: str) -> int:
"""Return the Levenshtein distance of x and y.
Keeps two rows over the shorter string. Cost: Theta(len(x) * len(y))
time and O(min(len(x), len(y))) extra space.
"""
if len(y) > len(x):
x, y = y, x
n = len(y)
prev = list(range(n + 1))
for i in range(1, len(x) + 1):
cur = [i] + [0] * n
xi = x[i - 1]
for j in range(1, n + 1):
c = 0 if xi == y[j - 1] else 1
cur[j] = min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + c)
prev = cur
return prev[n] # @line L7
def alignment(x: str, y: str) -> list[tuple[str, str]]:
"""Return an optimal alignment of x and y as a list of columns (a, b).
A column ("a", "b") is a match when a == b and a substitution when a != b,
("a", "") is a deletion and ("", "b") is an insertion. The number of
columns with a != b is the distance. Cost: Theta(len(x) * len(y)).
"""
d = edit_table(x, y)
i, j = len(x), len(y) # @line L8
cols: list[tuple[str, str]] = []
while i > 0 or j > 0: # @line L9
if i > 0 and j > 0 and d[i][j] == d[i - 1][j - 1] + (x[i - 1] != y[j - 1]): # @line L10
cols.append((x[i - 1], y[j - 1]))
i, j = i - 1, j - 1
elif i > 0 and d[i][j] == d[i - 1][j] + 1: # @line L11
cols.append((x[i - 1], ""))
i -= 1
else: # @line L12
cols.append(("", y[j - 1]))
j -= 1
cols.reverse()
return cols # @line L13
test_wagner_fischer_algorithm.py 90 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/wagner-fischer-algorithm/. The authors are listed in prov/ZX8DFX.jsonl.
import random
from collections import deque
from wagner_fischer_algorithm import alignment, edit_distance, edit_table
def bfs_distance(x: str, y: str, alphabet: str) -> int:
"""Shortest number of unit edit operations from x to y, by breadth-first search."""
limit = max(len(x), len(y)) + 1
seen = {x: 0}
queue = deque([x])
while queue:
s = queue.popleft()
if s == y:
return seen[s]
nxt = []
for i in range(len(s)):
nxt.append(s[:i] + s[i + 1 :])
for c in alphabet:
if c != s[i]:
nxt.append(s[:i] + c + s[i + 1 :])
if len(s) < limit:
for i in range(len(s) + 1):
for c in alphabet:
nxt.append(s[:i] + c + s[i:])
for t in nxt:
if t not in seen:
seen[t] = seen[s] + 1
queue.append(t)
raise AssertionError("unreachable")
def check_alignment(x: str, y: str) -> None:
cols = alignment(x, y)
assert "".join(a for a, _ in cols) == x
assert "".join(b for _, b in cols) == y
assert all(a != "" or b != "" for a, b in cols)
assert sum(a != b for a, b in cols) == edit_distance(x, y)
def test_example() -> None:
d = edit_table("kitten", "sitting")
assert d[6] == [6, 6, 5, 4, 3, 3, 2, 3]
assert d[3] == [3, 3, 2, 1, 2, 3, 4, 5]
assert edit_distance("kitten", "sitting") == 3
assert alignment("kitten", "sitting") == [
("k", "s"), ("i", "i"), ("t", "t"), ("t", "t"), ("e", "i"), ("n", "n"), ("", "g"),
]
def test_edges() -> None:
assert edit_distance("", "") == 0
assert edit_distance("", "abc") == 3
assert edit_distance("abc", "") == 3
assert edit_distance("abc", "abc") == 0
assert edit_distance("ab", "ba") == 2
assert edit_distance("sunday", "saturday") == 3
assert edit_distance("intention", "execution") == 5
assert alignment("", "") == []
for x, y in [("", "ab"), ("ab", ""), ("a", "b"), ("abc", "abc")]:
check_alignment(x, y)
def test_random_against_bfs() -> None:
rng = random.Random(1974)
for alphabet in ("ab", "acgt"):
for _ in range(300):
top = 5 if alphabet == "ab" else 4
x = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, top)))
y = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, top)))
d = edit_distance(x, y)
assert d == bfs_distance(x, y, alphabet)
assert d == edit_table(x, y)[len(x)][len(y)] == edit_distance(y, x)
check_alignment(x, y)
def test_random_longer() -> None:
rng = random.Random(7)
for alphabet in ("ab", "acgt"):
for _ in range(300):
x = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 20)))
y = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 20)))
d = edit_distance(x, y)
assert abs(len(x) - len(y)) <= d <= max(len(x), len(y))
check_alignment(x, y)
z = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 20)))
assert edit_distance(x, z) <= d + edit_distance(y, z)
What the next level needs
- the tests did not run in this build