dfa 标签归档

共 3 篇文章 · 返回首页

AC 自动机：失败链接、输出链接与转移表布局

从 Aho–Corasick 原文出发讲清 goto、失败与输出函数、2n 转移界和输出爆炸，用可复现程序对比满表 DFA、稀疏 NFA、位图 NFA、字节类 DFA 的内存与扫描代价，并核对 grep、Snort、Suricata、Hyperscan 与 Rust crate 的实际选择。

UTF-8 的位布局、合法序列与最大子部分替换，Hoehrmann DFA 与 Keiser–Lemire SIMD 验证，再到规范化、字素簇、大小写折叠和 Trojan Source；编解码器经全部 2^32 个四字节串穷举测试。

每个正则表达式引擎背后，都有一个 DFA 最小化算法在工作。