模式匹配：AC自动机

一、概述

AC自动机在1975年产生于贝尔实验室&＃xff0c;是著名的多模匹配算法之一。
之前谈到一种单模式匹配算法&＃xff0c;KMP。与之比较&＃xff0c;KMP是用来在一篇文章中匹配一个模式串&＃xff1b;而假如存在多个模式串&＃xff0c;按照KMP的思路就需要进行多轮重复匹配&＃xff0c;所以这时候就需要一种更加有效率的方式。

AC自动机 &＃61; 字典树 &＃43; KMP


对于字典树和KMP算法不了解的&＃xff0c;可以参考以下两篇博文&＃xff1a;
1、字典树
2、KMP算法

二、基本原理

1、KMP和字典树

之前谈到&＃xff0c;在KMP进行单模式匹配时&＃xff0c;只需要线性的扫描一遍文本串&＃xff0c;在扫描过程中出现匹配失败时&＃xff0c;可以根据失配表&＃xff0c;对移动位置进行确定&＃xff0c;继续进行匹配。
而多模式的匹配需要怎么进行呢&＃xff1f;考虑一下字典树&＃xff0c;这是一种多模式的匹配&＃xff0c;假如将多个模式串组合形成一个字典树&＃xff0c;再结和KMP算法&＃xff0c;这就是一种多模式匹配的思路了。

2、基本构造

按照上面的思路&＃xff0c;将模式串处理称为字典树&＃xff0c;对文本串进行匹配时&＃xff0c;AC自动机应该具有三种状态&＃xff1a;

&＃xff08;1&＃xff09;按字符匹配成功&＃xff0c;继续匹配

从字典树的角度来说&＃xff0c;就是当前节点的字符与文本串的字符相同&＃xff0c;则继续按照字典树路径进行匹配

&＃xff08;2&＃xff09;按字符匹配成功&＃xff0c;到达结尾

同样这里匹配成功后&＃xff0c;但已经达到结尾&＃xff0c;匹配结束

&＃xff08;3&＃xff09;按字符匹配失败

正常字典树匹配失败&＃xff0c;则匹配结束。但结合了KMP算法中的失配表&＃xff0c;AC自动机在匹配失败时&＃xff0c;会进行路径跳转&＃xff0c;通过失配路径进行进行匹配&＃xff0c;直到匹配成功或者回到根节点
这里的失配路径指向&＃xff0c;实际上是在字典树中寻找&＃xff0c;最长的当前字符串的后缀字符串

三、实例

以经典的ushers为例&＃xff0c;模式串是[he、she、shr&＃xff0c;say、her]&＃xff0c;文本串为‘ushers’

1、构建字典树

2、构造失配路径

步骤&＃xff08;1&＃xff09;节点&＃39;h&＃39;父节点为root节点&＃xff0c;失配路径直接指向root节点步骤&＃xff08;2&＃xff09;节点&＃39;s&＃39;父节点为root节点&＃xff0c;失配路径直接指向root节点步骤&＃xff08;3&＃xff09;节点&＃39;e&＃39;父节点为&＃39;h&＃39;&＃xff0c;寻找节点&＃39;h&＃39;的前缀指针root节点&＃xff0c;是否有字符为&＃39;e&＃39;的子节点&＃xff0c;没有&＃xff1b;前缀指针已为root节点&＃xff0c;失配路径指向root节点步骤&＃xff08;4&＃xff09;节点&＃39;a&＃39;父节点为&＃39;s&＃39;&＃xff0c;寻找节点&＃39;s&＃39;的前缀指针root节点&＃xff0c;是否有字符为&＃39;a&＃39;的子节点&＃xff0c;没有&＃xff1b;前缀指针已为root节点&＃xff0c;失配路径指向root节点步骤&＃xff08;5&＃xff09;节点&＃39;h&＃39;父节点为&＃39;s&＃39;&＃xff0c;寻找节点&＃39;s&＃39;的前缀指针root节点&＃xff0c;是否有字符为&＃39;h&＃39;的子节点&＃xff0c;有&＃xff1b;失配路径指向该字符为&＃39;h&＃39;的子节点步骤&＃xff08;6&＃xff09;节点&＃39;r&＃39;父节点为&＃39;e&＃39;节点&＃xff0c;寻找节点&＃39;e&＃39;的前缀指针root节点&＃xff0c;是否有字符为&＃39;r&＃39;的子节点&＃xff0c;没有&＃xff1b;前缀指针已为root节点&＃xff0c;失配路径指向root节点步骤&＃xff08;7&＃xff09;节点&＃39;y&＃39;父节点为&＃39;a&＃39;节点&＃xff0c;寻找节点&＃39;a&＃39;的前缀指针root节点&＃xff0c;是否有字符为&＃39;y&＃39;的子节点&＃xff0c;没有&＃xff1b;前缀指针已为root节点&＃xff0c;失配路径指向root节点步骤&＃xff08;8&＃xff09;节点&＃39;e&＃39;父节点为&＃39;h&＃39;节点&＃xff0c;寻找节点&＃39;h&＃39;的前缀指针&＃39;h&＃39;节点&＃xff0c;是否有字符为&＃39;e&＃39;的子节点&＃xff0c;有&＃xff1b;失配路径指向该字符为&＃39;e&＃39;的子节点步骤&＃xff08;9&＃xff09;节点&＃39;r&＃39;父节点为&＃39;h&＃39;节点&＃xff0c;寻找节点&＃39;h&＃39;的前缀指针&＃39;h&＃39;节点&＃xff0c;是否有字符为&＃39;r&＃39;的子节点&＃xff0c;没有&＃xff1b;继续寻找前缀指针节点&＃39;h&＃39;的前缀指针root节点&＃xff0c;是否有字符为&＃39;r&＃39;的子节点&＃xff0c;没有&＃xff1b;


到这里&＃xff0c;AC自动机的整个树就构造完毕了

3、匹配过程

自动从root节点出发&＃xff0c;进行匹配&＃xff0c;对于文本串‘ushers’&＃xff1a;

&＃xff08;1&＃xff09;字符u在root节点的子节点无法找到&＃xff0c;失配路径指向root节点&＃xff08;2&＃xff09;字符s在root节点的子节点中存在&＃xff0c;沿着字典树路径前进&＃xff0c;到达&＃39;s&＃39;节点&＃xff08;3&＃xff09;字符h在&＃39;s&＃39;节点的子节点中存在&＃xff0c;沿着字典树路径前进&＃xff0c;到达&＃39;h&＃39;节点&＃xff08;4&＃xff09;字符e在&＃39;h&＃39;节点的子节点中存在&＃xff0c;沿着字典树路径前进&＃xff0c;到达&＃39;e&＃39;节点&＃xff0c;输出she字符&＃xff08;5&＃xff09;字符r在&＃39;e&＃39;节点的子节点中无法找到&＃xff0c;失配路径指向前缀指针&＃39;e&＃39;节点&＃xff1b;输出he字符字符r在前缀指针&＃39;e&＃39;节点中存在&＃xff0c;沿着字典树路径前进&＃xff0c;到达&＃39;r&＃39;节点&＃xff0c;输出her字符&＃xff08;6&＃xff09;字符s在&＃39;r&＃39;节点的子节点中无法找到&＃xff0c;失配路径指向root节点&＃xff08;7&＃xff09;匹配结束&＃xff0c;输出字符为[she&＃xff0c;he&＃xff0c;her]


在上述步骤可以看到&＃xff0c;算法在步骤5中&＃xff0c;无法在子节点中找到字符r&＃xff0c;此时会自动转向另一条路径&＃xff0c;输出匹配成功的he及her字符&＃xff1b;对于通过失配路径到达当前路径之后&＃xff0c;状态机像从来没有走过之前的路径一样&＃xff08;从字典树上看&＃xff0c;像直接从root节点出发到达&＃xff09;&＃xff0c;这样没有“失败”的从初始路径出发&＃xff0c;直到匹配结束&＃xff0c;体现相当高的效率。