Set Horspool algorithm in Python
Extends Horspool's bad-character shift to a set of patterns using a shared shift table.
- File
set_horspool.py, 77 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/set-horspool/. The authors are listed in prov/3G04XE.jsonl.
from collections.abc import Hashable, Sequence
def build(patterns: Sequence[Sequence[Hashable]]):
"""Return (children, out, lmin, shift) for the nonempty patterns.
children[v] maps a character to the child of node v in the trie of the reversed
patterns, out[v] lists the indices j whose reversed pattern spells node v, lmin is the
shortest nonempty length, and shift maps a character to its shift (lmin if absent).
"""
children: list[dict[Hashable, int]] = [{}]
out: list[list[int]] = [[]]
for j, pat in enumerate(patterns):
if len(pat) == 0:
continue
v = 0
for ch in reversed(pat):
nxt = children[v].get(ch)
if nxt is None:
nxt = len(children)
children[v][ch] = nxt
children.append({})
out.append([])
v = nxt
out[v].append(j)
lmin = min(len(pat) for pat in patterns if len(pat) > 0) # @line L4
shift: dict[Hashable, int] = {} # @line L5
for pat in patterns: # @line L6
if len(pat) == 0:
continue
ell = len(pat)
for i in range(ell - lmin, ell - 1):
d = ell - 1 - i
if d < shift.get(pat[i], lmin):
shift[pat[i]] = d
return children, out, lmin, shift
def set_horspool(
text: Sequence[Hashable],
patterns: Sequence[Sequence[Hashable]],
stats: dict[str, int] | None = None,
) -> list[tuple[int, int]]:
"""Return the sorted pairs (s, j) such that patterns[j] occurs in text at the 0-based position s.
Occurrences may overlap, a pattern listed twice is reported once for each index, and an
empty pattern occurs at every s in 0..len(text). Characters may be any hashable values,
and text and patterns must be indexable sequences such as str, list or tuple. If stats is
a dict, the number of text characters read and the number of windows are stored in it.
"""
n = len(text)
res: list[tuple[int, int]] = []
reads = windows = 0
empty = [j for j, pat in enumerate(patterns) if len(pat) == 0]
res.extend((s, j) for s in range(n + 1) for j in empty) # @line L1
if len(empty) < len(patterns): # @line L2
children, out, lmin, shift = build(patterns) # @line L3
pos = lmin - 1 # @line L7
while pos <= n - 1: # @line L8
windows += 1
v, i = 0, pos # @line L9
while i >= 0 and text[i] in children[v]: # @line L10
v = children[v][text[i]] # @line L11
i -= 1
reads += 1
res.extend((i + 1, j) for j in out[v]) # @line L12
if i >= 0:
reads += 1 # the character that had no child was read too
pos += shift.get(text[pos], lmin) # @line L13
if stats is not None:
stats["reads"] = reads
stats["windows"] = windows
res.sort()
return res
test_set_horspool.py 103 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/set-horspool/. The authors are listed in prov/3G04XE.jsonl.
import random
from set_horspool import build, set_horspool
def naive(t, pats) -> list[tuple[int, int]]:
out = []
for j, q in enumerate(pats):
for s in range(len(t) - len(q) + 1):
if t[s : s + len(q)] == q:
out.append((s, j))
return sorted(out)
def test_example() -> None:
pats = ["aab", "abaa", "bab"]
_, _, lmin, shift = build(pats)
assert lmin == 3 and shift == {"a": 1, "b": 2}
stats: dict[str, int] = {}
got = set_horspool("cabaabcbabaab", pats, stats)
assert got == [(1, 1), (3, 0), (7, 2), (8, 1), (10, 0)]
assert stats == {"reads": 27, "windows": 7}
def test_small_cases() -> None:
assert set_horspool("", []) == []
assert set_horspool("", [""]) == [(0, 0)]
assert set_horspool("ab", ["", "x", "abc"]) == [(0, 0), (1, 0), (2, 0)]
assert set_horspool("ushers", ["he", "she", "his", "hers"]) == [(1, 1), (2, 0), (2, 3)]
assert set_horspool("aaaa", ["aa", "a", "aa"]) == naive("aaaa", ["aa", "a", "aa"])
assert set_horspool([1, 2, 1, 2], [[2, 1], [1]]) == [(0, 1), (1, 0), (2, 1)]
def test_shift_is_largest_safe() -> None:
# The shift of each character is the smallest distance at which some pattern can end.
rng = random.Random(5)
for _ in range(300):
pats = ["".join(rng.choice("abc") for _ in range(rng.randint(1, 6))) for _ in range(rng.randint(1, 4))]
_, _, lmin, shift = build(pats)
for c in "abcd":
want = lmin
for q in pats:
for d in range(1, len(q)):
if q[len(q) - 1 - d] == c:
want = min(want, d)
assert shift.get(c, lmin) == want
def random_text(rng: random.Random, sigma: int, n: int) -> str:
kind = rng.randrange(3)
if kind == 0:
return "".join(rng.choice("abcd"[:sigma]) for _ in range(n))
period = "".join(rng.choice("abcd"[:sigma]) for _ in range(rng.randint(1, 4)))
s = (period * (n // len(period) + 1))[:n]
if kind == 2 and n > 0:
i = rng.randrange(n)
s = s[:i] + rng.choice("abcd"[:sigma]) + s[i + 1 :]
return s
def random_patterns(rng: random.Random, t: str, sigma: int) -> list[str]:
pats: list[str] = []
for _ in range(rng.randint(1, 6)):
kind = rng.randrange(5)
if kind == 0 and t:
i = rng.randrange(len(t))
pats.append(t[i : i + rng.randint(1, 6)])
elif kind == 1 and pats:
q = rng.choice(pats)
pats.append(q[: rng.randint(0, len(q))]) # a prefix of another pattern
elif kind == 2 and pats:
q = rng.choice(pats)
pats.append(q[rng.randint(0, len(q)) :]) # a suffix of another pattern
elif kind == 3 and pats:
pats.append(rng.choice(pats)) # a pattern listed twice
else:
pats.append(random_text(rng, sigma, rng.randint(0, 6)))
return pats
def test_random_against_naive() -> None:
rng = random.Random(20261106)
cases = 0
for sigma in (1, 2, 4):
for _ in range(500):
t = random_text(rng, sigma, rng.randint(0, 40))
pats = random_patterns(rng, t, sigma)
assert set_horspool(t, pats) == naive(t, pats)
cases += 1
assert cases >= 500
def test_worst_case_reads() -> None:
# Text a^n and pattern b a^(L-1) with L >= 3: every window reads L characters
# (L - 1 that match and one that does not) and shifts by 1.
for L in (3, 4, 8):
stats: dict[str, int] = {}
assert set_horspool("a" * 100, ["b" + "a" * (L - 1)], stats) == []
assert stats["windows"] == 100 - L + 1
assert stats["reads"] == (100 - L + 1) * L
What the next level needs
- the tests did not run in this build