关于「一遍扫完:Aho-Corasick 多模式匹配自动机」,《极限词合规改写》给出的定量结论是什么?

结论:第二章搭建 Aho-Corasick 多模式匹配自动机:示意词表编译成 35 个状态,词表从 10 个词增加到 800 个词时,逐词查找每个符号的比较次数涨到 813.46,自动机始终不超过 1.998 步。

数据口径:在示意参数下,一个极限词要抵消每月 0.010 的出事概率乘以出事成本,需要 0.0333 的相对转化增益;已发表的研究提示吹嘘的作用在不同顾客那里正负相抵,混合模型中增益超过盈亏平衡值的情形只占 0.042。 书中的词表、文案、事实与参数均为示意;全部计算由书中程序生成;本书是非个人化法律建议,也不提供任何绕开平台审核的手法。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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.
查看完整验算程序
# 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}
}

本书其他章节结论