BF 算法、RK 算法、BM 算法、KMP 算法,都是单模式串匹配算法。Trie 树是多模式串匹配算法。
- 单模式串匹配算法,就是在一个主串中查找一个模式串。
- 多模式串匹配算法,就是在一个主串中查找多个模式串。
AC 自动机(Aho-Corasick)算法,是基于 Trie 树的一种改进算法,它跟 Trie 树的关系,就像单模式串中,KMP 算法与 BF 算法的关系一样。
如何实现敏感词过滤功能 #
可以针对每个敏感词,通过单模式串匹配算法(比如 KMP 算法)与用户输入的文字内容进行匹配。但是,这样每个匹配过程都需要扫描一遍用户输入的内容。 整个过程下来就要扫描很多遍用户输入的内容。如果敏感词很多,比如几千个,并且用户输入的内容很长,假如有上千个字符,那就需要扫描几千遍这样的 输入内容。很显然,这种处理思路比较低效。
多模式匹配算法要更高效。如何用 Trie 树实现敏感词过滤功能?
把敏感词字典构建成 Trie 树结构。用户输入的内容作为主串,从第一个字符(假设是字符 C)开始,在 Trie 树中匹配。当匹配到 Trie 树的叶子节点, 或者中途遇到不匹配字符的时候,将主串的开始匹配位置后移一位,也就是从字符 C 的下一个字符开始,重新在 Trie 树中匹配。 这种处理方法,有点类似单模式串匹配的 BF 算法。可以借鉴 KMP 算法对多模式串 Trie 树进行改进。这就需要 AC 自动机算法。
AC 自动机实际上就是在 Trie 树之上,加了类似 KMP 的 next 数组,只不过此处的 next 数组是构建在树上。