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
Kstateshitsnaive compsper symbolAC stepsper symbol
102754066310.1745971.149
501292620338750.8562581.565
20045966813414203.3577231.931
80015683073253824813.4679901.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