Wu-Manber algorithm in Python
Practical multi-pattern matcher that shifts by blocks of characters using a shift table, fast when patterns are long.
- File
wu_manber.py, 80 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/wu-manber/. The authors are listed in prov/2AQSRW.jsonl.
from collections.abc import Hashable, Sequence
def build_tables(patterns: Sequence[Sequence[Hashable]], block: int):
"""Return (lmin, b, shift, hash_table, prefix) for the nonempty patterns.
lmin is the shortest nonempty length and b = min(block, lmin) the block size. shift maps
a block (a tuple of b characters) to its shift; blocks that are absent have the default
shift lmin - b + 1. hash_table maps the last block of the first lmin characters of a
pattern to the list of its indices, and prefix[j] is the tuple of the first b characters.
"""
lmin = min(len(p) for p in patterns if len(p) > 0)
b = min(block, lmin) # @line L3
shift: dict[tuple, int] = {} # @line L4
for pat in patterns: # @line L5
if len(pat) == 0:
continue
for q in range(b, lmin + 1):
x = tuple(pat[q - b : q])
if lmin - q < shift.get(x, lmin - b + 1):
shift[x] = lmin - q
hash_table: dict[tuple, list[int]] = {}
prefix: dict[int, tuple] = {}
for j, pat in enumerate(patterns): # @line L6
if len(pat) == 0:
continue
hash_table.setdefault(tuple(pat[lmin - b : lmin]), []).append(j)
prefix[j] = tuple(pat[:b])
return lmin, b, shift, hash_table, prefix
def wu_manber(
text: Sequence[Hashable],
patterns: Sequence[Sequence[Hashable]],
block: int = 2,
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). block is the block size B (at least 1;
it is lowered to the shortest pattern length). If stats is a dict, the number of
windows, of windows with shift 0 and of full comparisons are stored in it.
"""
if block < 1:
raise ValueError("the block size must be at least 1")
n = len(text)
res: list[tuple[int, int]] = []
windows = zero = compares = 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
lmin, b, shift, hash_table, prefix = build_tables(patterns, block)
default = lmin - b + 1
pos = lmin - 1 # @line L7
while pos <= n - 1: # @line L8
windows += 1
x = tuple(text[pos - b + 1 : pos + 1]) # @line L9
d = shift.get(x, default)
if d > 0: # @line L10
pos += d
else: # @line L11
zero += 1
s = pos - lmin + 1 # @line L12
for j in hash_table.get(x, ()): # @line L13
pat = patterns[j]
if tuple(text[s : s + b]) == prefix[j] and s + len(pat) <= n: # @line L14
compares += 1
if all(text[s + i] == pat[i] for i in range(len(pat))):
res.append((s, j))
pos += 1 # @line L15
if stats is not None:
stats["windows"] = windows
stats["zero"] = zero
stats["compares"] = compares
res.sort()
return res
test_wu_manber.py 110 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/wu-manber/. The authors are listed in prov/2AQSRW.jsonl.
import random
import pytest
from wu_manber import build_tables, wu_manber
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)
EXAMPLE_TEXT = "fastsearchforpatternsinlongtext"
EXAMPLE_PATTERNS = ["search", "pattern", "tern", "text", "barn"]
def test_example_tables() -> None:
lmin, b, shift, hash_table, prefix = build_tables(EXAMPLE_PATTERNS, 2)
assert (lmin, b) == (4, 2)
want = {"ar": 0, "rn": 0, "tt": 0, "xt": 0, "at": 1, "ea": 1, "er": 1, "ex": 1, "ba": 2, "pa": 2, "se": 2, "te": 2}
assert shift == {tuple(k): v for k, v in want.items()}
assert hash_table == {("a", "r"): [0], ("t", "t"): [1], ("r", "n"): [2, 4], ("x", "t"): [3]}
assert prefix[4] == ("b", "a")
def test_example_search() -> None:
stats: dict[str, int] = {}
got = wu_manber(EXAMPLE_TEXT, EXAMPLE_PATTERNS, 2, stats)
assert got == [(4, 0), (13, 1), (16, 2), (27, 3)]
assert stats == {"windows": 14, "zero": 4, "compares": 4}
def test_small_cases() -> None:
assert wu_manber("", []) == []
assert wu_manber("", [""]) == [(0, 0)]
assert wu_manber("ab", ["", "x", "abc"]) == [(0, 0), (1, 0), (2, 0)]
assert wu_manber("ushers", ["he", "she", "his", "hers"]) == [(1, 1), (2, 0), (2, 3)]
assert wu_manber("aaaa", ["aa", "a", "aa"], 3) == naive("aaaa", ["aa", "a", "aa"])
assert wu_manber([1, 2, 1, 2], [[2, 1], [1, 2, 1]]) == [(0, 1), (1, 0)]
with pytest.raises(ValueError):
wu_manber("abc", ["a"], 0)
def test_shift_is_largest_safe() -> None:
# SHIFT[X] is the smallest distance from the end of a truncated pattern to an end of X.
rng = random.Random(9)
for _ in range(300):
pats = ["".join(rng.choice("abc") for _ in range(rng.randint(1, 6))) for _ in range(rng.randint(1, 4))]
for block in (1, 2, 3):
lmin, b, shift, _, _ = build_tables(pats, block)
for x in {tuple(q[i : i + b]) for q in pats for i in range(len(q) - b + 1)}:
want = lmin - b + 1
for q in pats:
for e in range(b, lmin + 1):
if tuple(q[e - b : e]) == x:
want = min(want, lmin - e)
assert shift.get(x, lmin - b + 1) == 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, 7)])
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, 7)))
return pats
def test_random_against_naive() -> None:
rng = random.Random(20261106)
cases = 0
for sigma in (1, 2, 4):
for _ in range(250):
t = random_text(rng, sigma, rng.randint(0, 40))
pats = random_patterns(rng, t, sigma)
want = naive(t, pats)
for block in (1, 2, 3, 4):
assert wu_manber(t, pats, block) == want
cases += 1
assert cases >= 500
What the next level needs
- the tests did not run in this build