AC算法—有限自动机的多模式匹配

Aho-Corasick自动机算法,用有限自动机将字符比较转化为状态转移:

①一种树型有限自动机,包含一组状态,每个状态用一个数字代表

②读入文本串中的字符,通过状态转移或偶尔输出的方式处理文本

③利用转向函数Goto、失效函数Fail和输出函数Output

例如:对应模式集{he, she, his, hers}的自动机

Goto函数:

AC算法—有限自动机的多模式匹配

Fail函数:

AC算法—有限自动机的多模式匹配

AC算法的基本思想如下:

预处理:建立函数Goto、Fail和Output,构造树型有限自动机

搜索查找:交叉使用函数扫描文本,定位出关键字的所有出现

此算法有两个特点:

①扫描文本时完全不需要回溯

②时间复杂度为O(n),时间复杂度与关键字的数目和长度无关

———————————————————预处理阶段———————————————————

预处理包含两个部分:

①确定状态和Goto函数,确定Output函数

②计算Fail函数,修正Output函数

现在开始构建转向函数Goto

①建立一个状态转移图,开始包含一个初始状态0

②添加一条从状态0出发的路径,表示输入的每个关键字P

结果是:

新的顶点和边被加入到图中,产生一条能拼写出关键字P的路径

关键字P会被添加到这条路径的终止状态的输出函数中

例如:对关键字集{he, she, his, hers}建立转向函数

①向图中添加第一个关键字"he",得到:(此时Output[2]="he")

AC算法—有限自动机的多模式匹配

②添加第二个关键字"she",得到:(此时Output[5]="she")

AC算法—有限自动机的多模式匹配

③添加第三个关键字“his”,得到:(此时Output[7]=“his”)

AC算法—有限自动机的多模式匹配

④添加第四个关键字“hers”,得到:(此时Output[9]=“hers”)

AC算法—有限自动机的多模式匹配

⑤对除h、s外的每个字符,都增加一个从状态0到状态0的循环:

AC算法—有限自动机的多模式匹配

接下来计算Fail函数,修正Output函数:

①定义状态S的深度:从状态0到状态S的最短路径(如D[1]=D[3]=1)

②令Fail(S)=0,其中D[S]=1(即S的深度为1)

③计算所有深度为2的状态,依此类推,直到所有状态的Fail值都被计算出

计算方法如下:

①已知S=Goto(R,ch),即状态R在输入字符为ch时转向状态S

②则Fail(S)=Goto(Fail(R),ch)

以刚才的图为例:

深度为1时:Fail(1)=0,Fail(3)=0

深度为2时:Fail(2)=Goto(Fail(1),e)=0、Fail(6)=0、Fail(4)=1

深度为3时:Fail(8)=Goto(Fail(2),r)=0、Fail(7)=3、Fail(5)=2

深度为4时:Fail(9)=Goto(Fail(8),s)=3

在计算Fail函数的过程中,也更新Output函数

当求出Fail(S)=S’时,在状态S的输出中加入状态S’的输出(如Fail(5)=2,Output[5]={he, she})

———————————————————搜索查找阶段———————————————————

首先有如下定义:G(R,ch)没有定义时,则认为G(R,ch)=Fail(即缺省箭头表示失败)

注意:对于任意字符ch,G(0,ch)!=Fail,因为它有指向

那么记R为当前状态,ch为输入文本Y的当前输入字符,树型有限自动机的一次操作循环可以定义如下:

①若G(R,ch)=S,则进入状态S,且Y的下一个字符变成当前输入字符

 若Output(R)不为空,那么输出一组关键字

②若G(R,ch)=Fail,那么以Fail(R)为当前状态,ch为当前字符,重复该循环操作

例如:输入为ushers,下方数字代表状态转移(其中G(4,e)=5、G(5,r)=Fail、Fail(5)=2、G(2,r)=8)

AC算法—有限自动机的多模式匹配

下面给出本人写的C++代码:(编译器为Codeblocks)

1 #include<iostream>
 2 #include<string.h>
 3 #define M 20//State Number
 4 using namespace std;
 5 int Goto[M][28],Fail[M],Top=0;
 6 string Output[M],D[M];
 7 
 8 void Reset();/*初始化*/
 9 void AdGoto(string x);/*更新Goto&&Output&&D*/
10 void AdOutput();/*更新Fail&&Output*/
11 void Recognize(string x);/*匹配*/
12 void PrintGoto();/*输出Goto*/
13 
14 int main()
15 {   Reset();
16     string x;
17     cin>>x;
18     while(x[0]!='#')
19     {   AdGoto(x);
20         cin>>x;}
21     PrintGoto();
22     AdOutput();
23     cout<<"\n\n";
24     cin>>x;
25     Recognize(x);}
26 
27 void Reset()/*初始化*/
28 {   for(int i=0;i<M;i++)
29     {   for(int j=0;j<28;j++)
30             Goto[i][j]=0;
31         Fail[i]=0;
32         Output[i]=D[i]="";}
33     D[0]+='0';}
34 
35 void AdGoto(string x)/*更新Goto&&Output&&D*/
36 {   int len=x.length(),next=0;
37     for(int i=0;i<len;i++)
38     {   int index=x[i]-97;/*char[26]->int[26]*/
39         if(!Goto[next][index])
40         {   Goto[next][index]=++Top;
41             Goto[Top][26]=next;/*前一状态*/
42             Goto[Top][27]=index;/*输入字符*/}
43         next=Goto[next][index];
44         char num=next+48;/*int->(char)int*/
45         if(D[i+1].find(num)==D[i+1].npos)/*记录深度*/
46             {D[i+1]+=num;}}
47     Output[next]+=x;/*更新输出*/}
48 
49 void AdOutput()/*更新Fail&&Output*/
50 {   int k=2,num,prev,in;
51     while(D[k]!="")
52     {   for(int i=0;i<D[k].length();i++)
53         {   num=D[k][i]-48;/*char->int*/
54             prev=Goto[num][26];/*前级状态*/
55             in=Goto[num][27];/*输入字符*/
56             Fail[num]=Goto[Fail[prev]][in];
57             if(Output[Fail[num]]!="")
58                 {Output[num]+=(" "+Output[Fail[num]]);}}
59         k++;}
60     cout<<'\n';
61     for(int i=0;i<=Top;i++)
62         if(Output[i]!="")
63             cout<<'\n'<<i<<'\t'<<Output[i];}
64 
65 void Recognize(string x)/*匹配*/
66 {   int state=0,index,i=0;
67     while(i<x.length())
68     {   index=x[i]-97;/*char[26]->int[26]*/
69         if(Goto[state][index]||!state)
70         {   state=Goto[state][index];
71             if(Output[state]!="")
72                 cout<<i+1<<'\t'<<Output[state]<<'\n';
73             i++;}
74         else
75             {state=Fail[state];}}}
76 
77 void PrintGoto()/*输出Goto*/
78 {   cout<<"\n#\ta b c d e f g h i j k l m n o p q r s t u v w x y z P C";
79     for(int i=0;i<=Top;i++)
80     {   cout<<'\n'<<i<<'\t';
81         for(int j=0;j<26;j++)
82         {   if(Goto[i][j])
83                 cout<<Goto[i][j]<<' ';
84             else
85                 cout<<"  ";}
86             cout<<Goto[i][26]<<' '<<(char)(Goto[i][27]+97);}}

下面是运行示例:(其中P代表前一状态、C代表前一状态的转向字符)

AC算法—有限自动机的多模式匹配

这是本人关于AC算法的Github地址:

https://github.com/XueDingWen/Software-Security/tree/master/AC

其中有CPP源文件和PDF详解

2016-11-24

相关推荐