文档介绍：多模匹配算法 ******@. title О Aho-Corasick 自动机算法(简称 AC 自动机) 1975 年产生于贝尔实验室。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。О该算法的基本思想是这样的: o 在预处理阶段, AC 自动机算法建立了三个函数,转向函数 goto ,失效函数 failure 和输出函数 output ,由此构造了一个树型有限自动机。 o 在搜索查找阶段,则通过这三个函数的交叉使用扫描文本,定位出关键字在文本中的所有出现位置。О此算法有两个特点,一个是扫描文本时完全不需要回溯, 另一个是时间复杂度为 O(n),时间复杂度与关键字的数目和长度无关。 AC 算法---- 有限自动机的多模式匹配算法 2. 树型有限自动机: 树型有限自动机包含一组状态,每个状态用一个数字代表。状态机读入文本串 y中的字符,然后通过产生状态转移或者偶尔发送输出的方式来处理文本。树型有限自动机的行为通过三个函数来指示:转向函数 g,失效函数 f和输出函数 output 。例如:对应模式集{ he, she, his, hers }的树型有限自动机图1 a )转向函数 g图 1 b)失效函数 f图 1 c)输出函数 output 3. 转向,失效和输出函数的构建现在说明如何根据一个关键字集建立正确的转向、失效和输出函数。整个构建包含两个部分,在第一部分确定状态和转向函数,在第二部分我们计算失效函数。输出函数的计算则是穿插在第一部分和第二部分中完成。为了构建转向函数,我们需要建立一个状态转移图。开始,这个图只包含一个代表状态 0。然后,通过添加一条从起始状态出发的路径的方式,依次向图中输入每个关键字 p。新的顶点和边被加入到图表中,以致于产生了一条能拼写出关键字 p的路径。关键字 p会被添加到这条路径的终止状态的输出函数中。当然只有必要时才会在图表中增加新的边。例如: 对关键字集{ he, she, his, hers }建立转向函数。?向图表中添加第一个关键字,得到: 从状态 0到状态 2的路径拼写出了关键字“ he ”,我们把输出“ he ”和状态 2相关联。?添加第二个关键字“ she ”,得到: 输出“ she ”和状态 5相关联。?增加第三个关键字“ his ”,我们得到了下面这个图。注意到当我们增加关键字“ his ”时,已经存在一条从状态 0到状态1标记着 h的边了,所以我们不必另外添加一条同样的边。输出“ his ”是和状态 7相关联的?添加第四个关键字“ hers ”,可以得到: 输出“ hers ”和状态 9相关联。在这里,我们能够使用已有的两条边:一条是从状态 0到 1标记着 h的边;一条是从状态 1到2标记着 e的边。这样,图已经成为一棵带根的树。为了完成转向函数的构建,我们对除了 h和s外的其他每个字符,都增加一个从状态 0到状态 0的循环。这样,我们得到了如图 1 a) 所示的状态转移图,这个图就代表转向函数。算法 1:建立转向函数 g。输入:关键字集 P ={p 1,p 2,p 3,…,p r}。输出:转向函数 g和部分的 output 函数。方法:图 2 建立转向函数 g的伪代码