Bit-parallel regex matching in Python
Simulates the Glushkov automaton of a regex on bit vectors, so each text symbol costs a few table lookups and one AND.
- File
bit_parallel_regex_matching.py, 151 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/bit-parallel-regex-matching/. The authors are listed in prov/045TZR.jsonl.
"""Bit-parallel simulation of the Glushkov automaton of a regular expression.
A regular expression is a tuple:
("empty",) for the empty language, ("eps",) for the empty string,
("sym", a) for one symbol, ("alt", r, s), ("cat", r, s) and ("star", r).
A set of Glushkov states 0..k is an integer whose bit p is state p.
"""
from __future__ import annotations
from dataclasses import dataclass
from typing import Any
Regex = tuple[Any, ...]
def _positions(regex: Regex) -> tuple[list[str], list[int], int]:
"""Return sym, the Follow masks (Follow[0] = First) and the accepting mask.
Glushkov's construction on bit masks, in postorder with an explicit stack.
"""
sym = [""]
follow = [0]
done: list[tuple[bool, int, int]] = []
todo: list[tuple[Regex, bool]] = [(regex, False)]
while todo:
node, ready = todo.pop()
tag = node[0]
if not ready and tag in ("alt", "cat", "star"):
todo.append((node, True))
for child in reversed(node[1:]):
todo.append((child, False))
continue
if tag == "empty":
done.append((False, 0, 0))
elif tag == "eps":
done.append((True, 0, 0))
elif tag == "sym":
sym.append(node[1])
follow.append(0)
bit = 1 << (len(sym) - 1)
done.append((False, bit, bit))
elif tag == "alt":
n2, f2, l2 = done.pop()
n1, f1, l1 = done.pop()
done.append((n1 or n2, f1 | f2, l1 | l2))
elif tag == "cat":
n2, f2, l2 = done.pop()
n1, f1, l1 = done.pop()
_add_follow(follow, l1, f2)
done.append((n1 and n2, f1 | f2 if n1 else f1, l1 | l2 if n2 else l2))
elif tag == "star":
n1, f1, l1 = done.pop()
_add_follow(follow, l1, f1)
done.append((True, f1, l1))
else:
raise ValueError(f"unknown node {node!r}")
nullable, first, last = done.pop()
follow[0] = first
return sym, follow, last | (1 if nullable else 0)
def _add_follow(follow: list[int], last: int, first: int) -> None:
while last:
low = last & -last
follow[low.bit_length() - 1] |= first
last ^= low
@dataclass
class BitParallelMatcher:
"""Tables for the update D <- T[D] & B[c] on bit masks of Glushkov states."""
b: int
chunks: int
tables: list[list[int]]
masks: dict[str, int]
final: int
def step(self, d: int, c: str) -> int:
"""One text symbol: OR the chunk tables, then AND the symbol mask."""
e = 0 # @line L8
low = (1 << self.b) - 1
for j in range(self.chunks):
e |= self.tables[j][(d >> (j * self.b)) & low]
return e & self.masks.get(c, 0) # @line L9
def compile_matcher(regex: Regex, chunk_bits: int = 8) -> BitParallelMatcher:
"""Build the masks and the split tables of `regex`.
Cost: O(m k^2) for the Glushkov sets, then O(2^b) table entries for
each of the ceil((k + 1) / b) chunks, each entry a (k + 1)-bit integer.
"""
if chunk_bits < 1:
raise ValueError("chunk_bits must be at least 1")
sym, follow, final = _positions(regex) # @line L1
masks: dict[str, int] = {}
for q in range(1, len(sym)): # @line L2
masks[sym[q]] = masks.get(sym[q], 0) | (1 << q)
states = len(sym) # @line L3
b = chunk_bits
chunks = (states + b - 1) // b # @line L4
tables = []
for j in range(chunks): # @line L5
width = min(b, states - j * b)
table = [0] * (1 << b)
for v in range(1, 1 << width):
low = v & -v
table[v] = table[v ^ low] | follow[j * b + low.bit_length() - 1]
tables.append(table)
return BitParallelMatcher(b, chunks, tables, masks, final)
def run(mt: BitParallelMatcher, word: str) -> bool:
"""Decide whether `word` is accepted, with tables built by compile_matcher.
Cost: ceil((k + 1) / b) table lookups and ORs of (k + 1)-bit masks per symbol.
"""
d = 1 # @line L6
for c in word: # @line L7
d = mt.step(d, c)
if d == 0: # @line L10
return False
return d & mt.final != 0 # @line L11
def bit_parallel_match(regex: Regex, word: str, chunk_bits: int = 8) -> bool:
"""Decide whether `word` is in L(regex): compile_matcher, then run."""
return run(compile_matcher(regex, chunk_bits), word)
def bit_parallel_search(regex: Regex, text: str, chunk_bits: int = 8) -> list[int]:
"""Return every end position e such that some text[s:e] is in L(regex).
The initial state is added again before each symbol, so a match may start
anywhere. Same cost per symbol as bit_parallel_match.
"""
mt = compile_matcher(regex, chunk_bits)
ends = []
d = 1
if d & mt.final:
ends.append(0)
for i, c in enumerate(text):
d = mt.step(d, c) | 1
if d & mt.final:
ends.append(i + 1)
return ends
test_bit_parallel_regex_matching.py 206 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/bit-parallel-regex-matching/. The authors are listed in prov/045TZR.jsonl.
import itertools
import random
from bit_parallel_regex_matching import bit_parallel_match, bit_parallel_search, compile_matcher, run
EMPTY = ("empty",)
EPS = ("eps",)
def parse(text):
"""Parse | , concatenation, *, parentheses, ε and ∅ into the tuple form."""
pos = 0
def peek():
return text[pos] if pos < len(text) else None
def p_alt():
nonlocal pos
r = p_cat()
while peek() == "|":
pos += 1
r = ("alt", r, p_cat())
return r
def p_cat():
items = []
while peek() is not None and peek() not in "|)":
items.append(p_rep())
if not items:
return EPS
r = items[0]
for x in items[1:]:
r = ("cat", r, x)
return r
def p_rep():
nonlocal pos
r = p_atom()
while peek() == "*":
pos += 1
r = ("star", r)
return r
def p_atom():
nonlocal pos
c = peek()
pos += 1
if c == "(":
r = p_alt()
assert peek() == ")"
pos += 1
return r
if c == "ε":
return EPS
if c == "∅":
return EMPTY
return ("sym", c)
r = p_alt()
assert pos == len(text)
return r
def language(r, bound):
"""All strings of L(r) of length at most bound, by enumeration."""
t = r[0]
if t == "empty":
return set()
if t == "eps":
return {""}
if t == "sym":
return {r[1]} if bound >= 1 else set()
if t == "alt":
return language(r[1], bound) | language(r[2], bound)
if t == "cat":
a, b = language(r[1], bound), language(r[2], bound)
return {x + y for x in a for y in b if len(x) + len(y) <= bound}
body = language(r[1], bound) - {""}
result, frontier = {""}, {""}
while frontier:
frontier = {x + y for x in frontier for y in body if len(x) + len(y) <= bound} - result
result |= frontier
return result
def words(alphabet, bound):
for k in range(bound + 1):
for t in itertools.product(alphabet, repeat=k):
yield "".join(t)
def random_regex(rng, alphabet, depth):
if depth == 0 or rng.random() < 0.25:
x = rng.random()
if x < 0.08:
return EMPTY
if x < 0.18:
return EPS
return ("sym", rng.choice(alphabet))
k = rng.random()
if k < 0.35:
return ("alt", random_regex(rng, alphabet, depth - 1), random_regex(rng, alphabet, depth - 1))
if k < 0.75:
return ("cat", random_regex(rng, alphabet, depth - 1), random_regex(rng, alphabet, depth - 1))
return ("star", random_regex(rng, alphabet, depth - 1))
def search_oracle(r, text, bound):
lang = language(r, bound)
return [e for e in range(len(text) + 1) if any(text[s:e] in lang for s in range(e + 1))]
def test_example_page():
mt = compile_matcher(parse("(a|b)*ab"))
assert mt.masks == {"a": 0b01010, "b": 0b10100}
assert mt.final == 0b10000
d, seen = 1, []
for c in "abab":
d = mt.step(d, c)
seen.append(format(d, "05b"))
assert seen == ["01010", "10100", "01010", "10100"]
assert bit_parallel_match(parse("(a|b)*ab"), "abab")
assert not bit_parallel_match(parse("(a|b)*ab"), "aba")
def test_example_search():
assert bit_parallel_search(parse("ab*a"), "babbaa") == [5, 6]
assert bit_parallel_search(parse("a*"), "ba") == [0, 1, 2]
def test_chunk_sizes_agree():
rng = random.Random(3)
for _ in range(200):
r = random_regex(rng, "ab", 4)
mts = [compile_matcher(r, b) for b in (1, 2, 3, 5, 8, 12)]
for w in words("ab", 5):
assert len({run(mt, w) for mt in mts}) == 1
def test_edge_cases():
for text, yes, no in [
("∅", [], ["", "a"]),
("ε", [""], ["a"]),
("∅*", [""], ["a"]),
("ε*", [""], ["b"]),
("((a*)*)*", ["", "aaaa"], ["ab"]),
("(ε|∅)*a", ["a"], ["", "aa"]),
("a∅|∅", [], ["a", ""]),
]:
r = parse(text)
assert all(bit_parallel_match(r, w) for w in yes)
assert not any(bit_parallel_match(r, w) for w in no)
assert not bit_parallel_match(parse("ab"), "ac")
assert bit_parallel_search(parse("∅"), "ab") == []
assert bit_parallel_search(parse("ε"), "ab") == [0, 1, 2]
def test_many_positions_and_long_text():
k = 300
r = ("sym", "a")
for i in range(1, k):
r = ("cat", r, ("sym", "ab"[i % 2]))
target = "".join("ab"[i % 2] for i in range(k))
assert bit_parallel_match(r, target)
assert not bit_parallel_match(r, target[:-1])
assert bit_parallel_search(r, "b" + target + "a") == [k + 1]
star = parse("(a|b)*a(a|b)(a|b)(a|b)")
text = "ab" * 20000 + "abbb"
assert bit_parallel_match(star, text)
assert not bit_parallel_match(star, "ab" * 20000 + "bbbb")
def test_random_against_enumeration():
rng = random.Random(20261106)
for trial in range(900):
alphabet = "ab" if trial % 2 else "abc"
bound = 6 if alphabet == "ab" else 4
r = random_regex(rng, alphabet, rng.randint(0, 5))
mt = compile_matcher(r, rng.choice([1, 2, 3, 4, 8]))
expected = language(r, bound)
for w in words(alphabet, bound):
assert run(mt, w) == (w in expected)
def test_random_search_against_enumeration():
rng = random.Random(11)
for trial in range(500):
alphabet = "ab" if trial % 2 else "abc"
r = random_regex(rng, alphabet, rng.randint(0, 4))
text = "".join(rng.choice(alphabet) for _ in range(rng.randint(0, 7)))
assert bit_parallel_search(r, text, rng.choice([2, 8])) == search_oracle(r, text, len(text))
def test_random_nested_stars():
rng = random.Random(7)
for _ in range(300):
r = random_regex(rng, "ab", 3)
for _ in range(rng.randint(1, 3)):
r = ("star", ("alt", r, EPS)) if rng.random() < 0.5 else ("star", r)
mt = compile_matcher(r)
expected = language(r, 6)
for w in words("ab", 6):
assert run(mt, w) == (w in expected)
What the next level needs
- the tests did not run in this build