What does Compliant Rewriting of Absolute Terms conclude, in numbers, about “One Pass for Every Term: the Aho-Corasick Multi-Pattern Automaton”?
Answer: Chapter 2 builds an Aho-Corasick multi-pattern automaton: the illustrative lexicon compiles into 35 states, and as the lexicon grows from 10 to 800 terms the term-by-term search rises to 813.46 comparisons per symbol while the automaton never exceeds 1.998 steps.
Scope of the numbers: Its lexicons, copy, facts and parameters are illustrative; all calculations are generated by its programs; it is not individual legal advice and supplies no way of slipping past platform review. Marked boxes separate published evidence, runnable Python calculations (18 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 1.998, 10, 800, 813.46
| text 4000 symbols, alphabet 60 | ||||||
| K | states | hits | naive comps | per symbol | AC steps | per symbol |
| 10 | 27 | 5 | 40663 | 10.17 | 4597 | 1.149 |
| 50 | 129 | 26 | 203387 | 50.85 | 6258 | 1.565 |
| 200 | 459 | 66 | 813414 | 203.35 | 7723 | 1.931 |
| 800 | 1568 | 307 | 3253824 | 813.46 | 7990 | 1.998 |
| automaton steps per symbol are bounded by 2 for any K; | ||||||
| naive comparisons grow in proportion to K. |
Show the full program
# Chapter 2. p22: scan cost of the automaton against pattern-by-pattern.
# Model: a synthetic alphabet of 60 symbols, lexicons of K random
# patterns of length 2 to 4, and one random text of 4000 symbols
# (fixed seed). The naive checker tries every pattern at every position
# and counts symbol comparisons; the automaton counts goto plus failure
# transitions. Both must report the same number of hits.
import random
from collections import deque
rng = random.Random(20261113)
SIGMA = ["s%02d" % i for i in range(60)]
TEXT = [rng.choice(SIGMA) for _ in range(4000)]
def build(pats):
goto, fail, out = [{}], [0], [0]
for pat in pats:
s = 0
for tok in pat:
if tok not in goto[s]:
goto.append({})
fail.append(0)
out.append(0)
goto[s][tok] = len(goto) - 1
s = goto[s][tok]
out[s] += 1
queue = deque(goto[0].values())
while queue:
r = queue.popleft()
for tok, s in goto[r].items():
queue.append(s)
f = fail[r]
while f and tok not in goto[f]:
f = fail[f]
fail[s] = goto[f].get(tok, 0)
out[s] += out[fail[s]] # step
return goto, fail, out
def ac_scan(text, goto, fail, out):
s, hits, steps = 0, 0, 0
for tok in text:
while s and tok not in goto[s]:
s = fail[s]
steps += 1
s = goto[s].get(tok, 0)
steps += 1
hits += out[s] # step
return hits, steps
def naive_scan(text, pats):
hits, comps = 0, 0
n = len(text)
for i in range(n):
for pat in pats:
ok = True
for j, tok in enumerate(pat):
comps += 1
if i + j >= n or text[i + j] != tok:
ok = False
break
if ok:
hits += 1
return hits, comps
print("text %d symbols, alphabet %d" % (len(TEXT), len(SIGMA)))
print(" K states hits naive comps per symbol AC steps"
" per symbol")
for k in [10, 50, 200, 800]:
pats = []
seen = {}
while len(pats) < k:
p = tuple(rng.choice(SIGMA) for _ in range(rng.randint(2, 4)))
if p not in seen:
seen[p] = 1
pats.append(p)
goto, fail, out = build(pats)
h1, steps = ac_scan(TEXT, goto, fail, out)
h2, comps = naive_scan(TEXT, pats)
assert h1 == h2
print("%5d %7d %6d %12d %11.2f %10d %11.3f"
% (k, len(goto), h1, comps, comps / len(TEXT), steps,
steps / len(TEXT)))
print("automaton steps per symbol are bounded by 2 for any K;")
print("naive comparisons grow in proportion to K.")Single source and citation
Fan, Y. (2026). Compliant Rewriting for Platform-Sensitive Terms: Absolute-Term Automata under the Advertising Law, Meaning-Preserving Rewrites and Conversion Elasticity (Version 1.0.0), Chapter 2: One Pass for Every Term: the Aho-Corasick Multi-Pattern Automaton. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-274 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026274,
author = {Fan, Yafu},
title = {Compliant Rewriting for Platform-Sensitive Terms: Absolute-Term Automata under the Advertising Law, Meaning-Preserving Rewrites and Conversion Elasticity},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Risk Ledger of an Absolute Term: How Much Conversion Must One "Best" Buy?
- Chapter 3 · False Kills and Misses: Exempt Contexts, Audit Additions and Audit Sample Sizes
- Chapter 4 · Choosing Rewrites under Constraints: Evidence, Re-scanning and Title Length
- Chapter 5 · Keeping the Meaning: Why Surface Similarity Rewards the Violation
- Chapter 6 · Conversion Elasticity: How Much Does a Rewrite Move Conversion, and Can a Test Tell?
- Chapter 7 · Eastern and Western Sources: "If Names Are Not Correct" and Orwell's Rules for Writing
- Chapter 8 · Closing the Loop: a Compliant-Rewrite Library for the Persuasive-Copy Checker, and a Non-Inferiority Test