Ukkonen's cutoff algorithm in Python
Computes each column of the Sellers table only down to its last cell with a value at most k, in O(kn) expected time on random text.
- File
ukkonen_cutoff_algorithm.py, 51 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/ukkonen-cutoff-algorithm/. The authors are listed in prov/V58QHM.jsonl.
"""Ukkonen's cut-off algorithm: Sellers' dynamic program restricted to the
active cells, the cells with a value at most k.
Edit model: unit-cost insertion, deletion and substitution (Levenshtein),
no transpositions. Indices are 0-based. The result is the sorted list of end
positions j in 0..len(text) such that some substring text[h:j] has edit
distance at most k to the pattern.
"""
def ukkonen_cutoff(pattern: str, text: str, k: int) -> list[int]:
"""Return the end positions of the approximate matches of pattern in text.
Precondition: k >= 0. Cost: O(m n) time in the worst case, O(k n) expected
time on random text, O(m) extra space.
"""
return ukkonen_cutoff_trace(pattern, text, k)[0]
def ukkonen_cutoff_trace(pattern: str, text: str, k: int) -> tuple[list[int], list[int], int]:
"""Return (ends, lact, cells): the end positions, the last active row of
each column j = 0..n, and the number of cells computed."""
if k < 0:
raise ValueError("k must be at least 0")
m = len(pattern)
col = list(range(m + 1)) # @line L1
lact = min(k, m) # @line L2
ends = [0] if lact == m else [] # @line L3
trace = [lact]
cells = 0
for j in range(1, len(text) + 1): # @line L4
t = text[j - 1]
top = min(lact + 1, m) # @line L5
prev = col[0] # @line L6
for i in range(1, top + 1): # @line L7
c = 0 if pattern[i - 1] == t else 1
new = min(col[i] + 1, col[i - 1] + 1, prev + c) # @line L8
prev, col[i] = col[i], new
cells += top
lact = top # @line L9
while col[lact] > k:
lact -= 1
if lact == m: # @line L10
ends.append(j)
else:
col[lact + 1] = k + 1 # @line L11
trace.append(lact)
return ends, trace, cells
test_ukkonen_cutoff_algorithm.py 71 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/ukkonen-cutoff-algorithm/. The authors are listed in prov/V58QHM.jsonl.
import random
import pytest
from ukkonen_cutoff_algorithm import ukkonen_cutoff, ukkonen_cutoff_trace
def edit_distance(a: str, b: str) -> int:
d = [[i + j if i * j == 0 else 0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + (a[i - 1] != b[j - 1]))
return d[len(a)][len(b)]
def sellers_table(p: str, t: str) -> list[list[int]]:
c = [[i if j == 0 else 0 for j in range(len(t) + 1)] for i in range(len(p) + 1)]
for i in range(1, len(p) + 1):
for j in range(1, len(t) + 1):
c[i][j] = min(c[i - 1][j] + 1, c[i][j - 1] + 1, c[i - 1][j - 1] + (p[i - 1] != t[j - 1]))
return c
def brute(pattern: str, text: str, k: int) -> list[int]:
return [
j for j in range(len(text) + 1)
if min(edit_distance(pattern, text[h:j]) for h in range(j + 1)) <= k
]
def test_example() -> None:
ends, lact, cells = ukkonen_cutoff_trace("survey", "surgery", 2)
assert ends == [5, 6, 7]
assert lact == [2, 3, 4, 5, 5, 6, 6, 6]
assert ukkonen_cutoff("survey", "surgery", 1) == []
def test_edges() -> None:
assert ukkonen_cutoff("", "", 0) == [0]
assert ukkonen_cutoff("", "ab", 0) == [0, 1, 2]
assert ukkonen_cutoff("ab", "", 1) == []
assert ukkonen_cutoff("ab", "", 2) == [0]
assert ukkonen_cutoff("ab", "xyz", 5) == [0, 1, 2, 3]
assert ukkonen_cutoff("abc", "xxabcxx", 0) == [5]
with pytest.raises(ValueError):
ukkonen_cutoff("a", "a", -1)
def test_last_active_row() -> None:
rng = random.Random(1985)
for alphabet in ("ab", "acgt"):
for _ in range(300):
p = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 7)))
t = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 12)))
k = rng.randint(0, 4)
c = sellers_table(p, t)
_, lact, _ = ukkonen_cutoff_trace(p, t, k)
for j in range(len(t) + 1):
assert lact[j] == max(i for i in range(len(p) + 1) if c[i][j] <= k)
def test_random_against_brute_force() -> None:
rng = random.Random(132)
for alphabet in ("ab", "acgt"):
for _ in range(400):
p = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 6)))
t = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 12)))
k = rng.randint(0, 4)
assert ukkonen_cutoff(p, t, k) == brute(p, t, k)
What the next level needs
- the tests did not run in this build