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