Aho-Corasick 算法：从 Trie 到自动机
来源: compiler.club
概述
这篇文章讲如何构造 Aho-Corasick 自动机，用来在一段序列里同时匹配多个子串。作者喜欢这个算法的原因，是它能以相当令人愉快的方式从一棵已有的树结构里被构造出来：先讲 Trie 如何共享前缀，再讲后缀链接如何从转移失败中恢复，最后讲输出链接如何一次性报出所有匹配。
核心要点
- Trie（前缀树）把有公共前缀的条目共享在同一棵树上：存 {suit, suited, suitable} 时，公共前缀 suit 只会被存一次。
- Aho-Corasick 靠后缀链接从转移失败中恢复，它保留当前节点字符串的最长后缀，且该后缀恰好是树中某个模式的前缀。
- 后缀链接按广度优先遍历计算：看父节点的后缀链接是否有对应字符的出边，没有就继续沿后缀链接上溯，直到根节点为止。
- 例如扫描 suitems 时会走到代表 suit 的节点，发现没有 e 的出边，于是沿后缀链接回到 it 所在的状态继续扫描，最终匹配出 su[item]s。
- 输出链接把「当前匹配的模式」和「它本身也是模式的那些后缀」串成一条链，比如匹配到 spin 时必须同时输出 pin 与 in。
金句
我喜欢这个算法，因为它以一种相当令人愉快的方式，从一棵已有的树结构里构造出一台自动机。
👍 0
👎 0
← 返回 Lobsters 首页