关于「一遍扫完:Aho-Corasick 多模式匹配自动机」,《极限词合规改写》给出的定量结论是什么?
结论:第二章搭建 Aho-Corasick 多模式匹配自动机:示意词表编译成 35 个状态,词表从 10 个词增加到 800 个词时,逐词查找每个符号的比较次数涨到 813.46,自动机始终不超过 1.998 步。
数据口径:在示意参数下,一个极限词要抵消每月 0.010 的出事概率乘以出事成本,需要 0.0333 的相对转化增益;已发表的研究提示吹嘘的作用在不同顾客那里正负相抵,混合模型中增益超过盈亏平衡值的情形只占 0.042。 书中的词表、文案、事实与参数均为示意;全部计算由书中程序生成;本书是非个人化法律建议,也不提供任何绕开平台审核的手法。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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. |
查看完整验算程序
# 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.")唯一数据源与引用
范雅福(Fan, Y.). (2026). 《平台敏感词合规改写、广告法极限词自动机与语义保真转化弹性母典》第 2 章「一遍扫完:Aho-Corasick 多模式匹配自动机」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}