Turbo-BM algorithm in Python
Boyer-Moore variant that remembers the matched segment to avoid rescanning, giving at most 2n comparisons.
- File
turbo_boyer_moore.py, 85 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/turbo-boyer-moore/. The authors are listed in prov/05ED1E.jsonl.
from collections.abc import Hashable, Sequence
def suffixes(p: Sequence[Hashable]) -> list[int]:
"""suff[i] = length of the longest common suffix of p[:i+1] and p."""
m = len(p)
suff = [0] * m
if m == 0:
return suff
suff[m - 1] = m
g = f = m - 1
for i in range(m - 2, -1, -1):
if i > g and suff[i + m - 1 - f] < i - g:
suff[i] = suff[i + m - 1 - f]
else:
g = min(g, i)
f = i
while g >= 0 and p[g] == p[g + m - 1 - f]:
g -= 1
suff[i] = f - g
return suff
def good_suffix(p: Sequence[Hashable]) -> list[int]:
"""Strong good-suffix table; gs[0] is the smallest period of p."""
m = len(p)
suff = suffixes(p)
gs = [m] * m
j = 0
for i in range(m - 1, -1, -1):
if suff[i] == i + 1:
while j < m - 1 - i:
if gs[j] == m:
gs[j] = m - 1 - i
j += 1
for i in range(m - 1):
gs[m - 1 - suff[i]] = m - 1 - i
return gs
def turbo_boyer_moore(text: Sequence[Hashable], pattern: Sequence[Hashable], stats: dict | None = None) -> list[int]:
"""All shifts s with text[s:s+m] == pattern, in increasing order.
If stats is a dict, stats["comparisons"] receives the number of character comparisons.
"""
n, m = len(text), len(pattern) # @line L1
if m == 0: # @line L2
if stats is not None:
stats["comparisons"] = 0
return list(range(n + 1))
gs = good_suffix(pattern) # @line L3
last = {} # last occurrence in pattern[:m-1], as in the Horspool table
for k in range(m - 1):
last[pattern[k]] = k
out, comparisons = [], 0
s, u, shift = 0, 0, m # @line L4
while s <= n - m: # @line L5
i = m - 1 # @line L6
while i >= 0: # @line L7
comparisons += 1
if pattern[i] != text[s + i]:
break
i -= 1
if u != 0 and i == m - 1 - shift: # @line L8
i -= u # jump over the factor known from the last window
if i < 0: # @line L9
out.append(s) # @line L10
shift = gs[0]
u = m - shift # @line L11
else:
v = m - 1 - i # @line L12
turbo = u - v # @line L13
bc = i - last.get(text[s + i], -1) # @line L14
shift = max(turbo, bc, gs[i]) # @line L15
if shift == gs[i]: # @line L16
u = min(m - shift, v) # @line L17
else:
u = 0 # @line L18
s += shift # @line L19
if stats is not None:
stats["comparisons"] = comparisons
return out
test_turbo_boyer_moore.py 55 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/turbo-boyer-moore/. The authors are listed in prov/05ED1E.jsonl.
import itertools
import random
from turbo_boyer_moore import turbo_boyer_moore
def oracle(t: str, p: str) -> list[int]:
return [s for s in range(len(t) - len(p) + 1) if t.startswith(p, s)]
def test_example() -> None:
stats: dict = {}
assert turbo_boyer_moore("gcatcgcagagagtatacagtacg", "gcagagag", stats) == [5]
assert stats["comparisons"] == 15
def test_edges() -> None:
assert turbo_boyer_moore("abc", "") == [0, 1, 2, 3]
assert turbo_boyer_moore("", "") == [0]
assert turbo_boyer_moore("", "a") == []
assert turbo_boyer_moore("ab", "abc") == []
assert turbo_boyer_moore("a" * 10, "a" * 4) == list(range(7))
assert turbo_boyer_moore("a" * 10, "baaa") == []
def test_periodic_input_is_linear() -> None:
stats: dict = {}
assert turbo_boyer_moore("a" * 1000, "a" * 10, stats) == list(range(991))
assert stats["comparisons"] <= 2 * 1000
def test_exhaustive_binary() -> None:
for m in range(1, 5):
for p in itertools.product("ab", repeat=m):
ps = "".join(p)
for n in range(0, 9):
for t in itertools.product("ab", repeat=n):
ts = "".join(t)
stats: dict = {}
assert turbo_boyer_moore(ts, ps, stats) == oracle(ts, ps)
assert stats["comparisons"] <= 2 * n
def test_random_against_oracle() -> None:
rng = random.Random(1994)
for alphabet in ("a", "ab", "abcd"):
for _ in range(700):
t = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 40)))
p = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 7)))
stats: dict = {}
assert turbo_boyer_moore(t, p, stats) == oracle(t, p)
assert stats["comparisons"] <= 2 * len(t)
What the next level needs
- the tests did not run in this build