字符串模式匹配算法2 - AC算法

讨论QQ群:135202158

 

上篇文章(http://www.cnblogs.com/zzqcn/p/3508442.html)里提到的BF和KMP算法都是单模式串匹配算法,也就是说,模式串只有一个。当需要在字符串中搜索多个关键字(模式)时,则需要用到多模式串匹配算法。

AC(Aho-Corasick)算法是一个经典的多模式串匹配算法,它借鉴了KMP算法的思想,可以由有限状态机(Finite State Automata:FSA)来表示。AC算法的基本原理是:

先根据多模式串建立一个有限状态自动机FSA,在进行模式匹配时,设当前状态为Scur,输入串中的当前符号为C,运行FSA,试图得到下一状态Snext。如果Snext无效,即发生失配,则根据规则,将当前状态回退到一个适合的状态Sfail,然后重复上一过程,直到Snext有效或Scur为0。在匹配的过程中,如果当前状态正好匹配了某个模式P,则输出它。

 

由AC算法的原理,我们可以知道,用于匹配的FSA与输入串无关,而只与模式串有关;匹配过程中如果发生失配,则FSA应回退到某一状态,而输入串指针无需回退。这两点都与KMP算法的思想吻合。

要实现基本的AC算法,即实现FSA逻辑,需要构建3样东西:

  1. 状态跳转表goto :决定对于当前状态S和条件C,如何得到下一状态S‘
  2. 失配跳转表fail : 决定goto表得到的下一状态无效时,应该回退到哪一个状态
  3. 匹配结果输出表output : 决定在哪个状态时输出哪个恰好匹配的模式

 

原理比较抽象,下面以一个简单而且经典的例子(来自于AC算法创始人的论文)来演示一下AC算法的原理及goto、fail、output这3个表的构建。设多模式为 {“he”, “she”, “his”, “hers”}。下面来一步一步构建FSA。

首先规定一个初始状态0,接着依次处理多个模式串,首先是he:

 字符串模式匹配算法2 - AC算法

每个圆圈代表一个状态(State),圆圈中的数字表示状态的编号;有向箭头代表状态的转换,它由当前状态指向下一状态,箭头上的字符表示此次状态转换的条件。

接下来是she,注意每处理一个模式串时,都要先回到起始状态0:

 字符串模式匹配算法2 - AC算法

注意,如果给定条件C,从当前状态出发能转换到一个有效状态,那么只进行状态转换,而不创建新状态,这一点在处理后面两个模式串时可以看到。接着是his:

 字符串模式匹配算法2 - AC算法

最后是hers,而且AC规定,当当前状态为初始状态(0)时,对于任意条件C来,都能转换到有效状态(这也避免了回退的死循环),因此,除了条件h和s外,对其他任意条件,状态0还应转换至状态0:

 字符串模式匹配算法2 - AC算法

 

其实,最后的FSA图就表示了goto表,因为上面画的状态及状态转换都是有效的。另外,也可以自然地知道,每处理完一个模式时,FSA的当前状态都对应着此模式。因此,状态2,5,7,8分别对应模式he, she, his, hers,也就是2,5,7,8这4个状态对应的output表中的值。不过,到目前为止output表还未创建完成。

在下面的讨论中,我们用S’ = goto(S,C)表示状态S经由条件C转换到状态S‘,fail(S)表示状态S的fail表值,output(S)表示状态S的output表值。

goto表反映了有效的状态转换。而在fail表反映了转换失败时应回退到的状态。比如,设当前状态为2,当条件不是r时,状态转换就失败,必须回退到某一个合适的状态,这个状态就是状态2的fail值。而fail值的求法呢,和KMP算法中求next函数一样,可以用递推法来进行。

首先规定与状态0距离为1(即深度为1)的所有状态的fail值都为0。然后设当前状态是S1,求fail(S1)。我们知道,S1的前一状态必定是唯一的(从FSA图也可以看出),设S1的前一状态是S2,S2转换到S1的条件为C,测试S3 = goto(fail(S2), C),如果成功,则fail(S1) = goto(fail(S2), C),如果不成功,继续测试S4 = goto(fail(S3), C)是否成功,如此重复,直到转换到某个有效的状态Sn,令fail(S1) = Sn

做为例子,我们来求状态3,4,5的fail值。首先,按照约定fail(3) == 0。接着求fail(4),由于goto(fail(3), h) == goto(0, h) == 1,所以fail(4) == 1。接着求fail(5),由于goto(fail(4), e) == goto(1, e) == 2,所以fail(5) == 2。在这里我们注意到,当FSA的状态转换到状态5时,不仅匹配了she,而且匹配了he,这意味着对两个状态S和S’,S>S’,如果fail(S) == S‘,则output(S)应添加output(S’)。这样一来,output表也构建完整了。fail表如下:

状态

0 1 2 3 4 5 6 7 8 9

fail

N/A 0 0 0 1 2 0 3 0 3

 

3个表构建完成后,就可以对输入串进行模式匹配了。设输入串为“ushers”,则匹配过程如下:

符号

状态转换

输出

u

0->0

 

s

0->3

 

h

3->4

 

e

4->5

she he

r

5->2 2->8

 

s

8->9

hers

 

 注意,虽然扫描到符号r时经历了状态2,但那只是一个中间状态,之后立刻切换到状态8,因此并不输出output(2)的内容{he},这也避免了模式”he”的重复输出。

至此,我们已经构建了goto,fail,output 3个必需的表。这时构建的FSA也叫做非确定性有限状态机(Nondeterministic Finite State Automata: NFA),也就是说,当匹配过程中发生失配时,应根据fail表进行状态回退,但具体回退到哪个状态为止,是不确定的,需要一次或多次循环回溯。可以预见,NFA会影响模式匹配的效率。可以通过构建确定性有限状态机(Deterministic Finite State Automata: DFA)来弥补这个缺陷,它的原理是,在当前状态下,对于任意条件,都可以确定地给出下一状态,而不需要进行循环。

设当前状态是S,条件为C,问题是如何求得下一个确定状态S‘。如果goto(S, C)成功,则S’ = goto(S, C);否则,令S‘ = goto(fail(S), C),如果S’有效且不为0,则S‘就是那个确定状态,此时,应把S’ = goto(S, C)这个关系添加到goto表中。可以预见,DFA会提高匹配速度,但由于向goto表添加了更多的条目,会导致存储消耗增加。

做为例子,我们来求状态1的确定状态{S’}。首先fail(1)==0。当C==e或i时,S‘不变,分别是2,6。当C==h时,由于goto(0,h)==1,所以S’==1。当C==s时,由于goto(0, s)==3,所以S’==3。对于其他条件C,goto(0, C)==0。因此,我们需要往之前构建的goto表添加两项:1=goto(1, h), 3=goto(1,s)。

 

下面,用简单的C++代码来实现前文所述的AC算法,包括NFA和DFA形式。

字符串模式匹配算法2 - AC算法
  1 // Author: 赵子清
  2 // Blog:   http://www.cnblogs.com/zzqcn
  3 
  4 #include <vector>
  5 #include <queue>
  6 #include <algorithm>
  7 #include <functional>
  8 #include <string>
  9 #include <cstdio>
 10 using namespace std;
 11 
 12 
 13 #define AC_FAIL_STATE   -1
 14 #define AC_UNDEF_FAIL   -1
 15 #define AC_CONT_SIZE    256
 16 
 17 
 18 struct  ac_transition
 19 {
 20     char  condition;
 21     int   next;
 22 };
 23 
 24 enum FSAType
 25 {
 26     FSA_NULL = 0,
 27     FSA_NFA,
 28     FSA_DFA
 29 };
 30 
 31 
 32 struct  ac_state_finder :
 33         public binary_function<ac_transition, char, bool>
 34 {
 35     bool  operator() (const ac_transition& t, char c) const
 36     {
 37         return  (t.condition == c);
 38     }
 39 };
 40 
 41 
 42 vector<vector<ac_transition>>   goto_table;
 43 vector<vector<string>>          output_table;
 44 vector<int>                     fail_table;
 45 FSAType  fsa_type = FSA_NULL;
 46 
 47 
 48 int  ac_goto(int _state, char _cont);
 49 int  ac_creat_goto_table(const vector<string>& _ptns);
 50 int  ac_creat_fail_table();
 51 int  ac_convert_to_DFA();
 52 int  ac_print_goto_table();
 53 int  ac_search(const string& _txt);
 54 
 55 
 56 int main(int argc, char** argv)
 57 {
 58     string ss[4] = {"he", "she", "his", "hers"};
 59     vector<string>  ptns(ss, ss+4);
 60     string txt = "ushers";
 61 
 62     ac_creat_goto_table(ptns);
 63     ac_creat_fail_table();
 64     ac_print_goto_table();
 65     ac_search(txt);
 66 
 67     ac_convert_to_DFA();
 68     ac_print_goto_table();
 69     ac_search(txt);
 70 
 71     return 0;
 72 }
 73 
 74 
 75 int  ac_goto(int _state, char _cont)
 76 {
 77     vector<ac_transition>::const_iterator ret = 
 78         find_if(goto_table[_state].begin(), goto_table[_state].end(),
 79         bind2nd(ac_state_finder(), _cont));
 80     if(goto_table[_state].end() == ret)
 81     {
 82         if(0 == _state)
 83             return 0;
 84         else
 85             return AC_FAIL_STATE;
 86     }
 87     else
 88         return ret->next;
 89 }
 90 
 91 
 92 int  ac_creat_goto_table(const vector<string>& _ptns)
 93 {
 94     int state = 0;
 95     int state_id = 0;
 96 
 97     ac_transition t;
 98     vector<ac_transition>  ts;
 99     vector<string>  ss;
100 
101     goto_table.push_back(ts);
102     output_table.push_back(ss);
103     state_id++;
104 
105     for(vector<string>::const_iterator i = _ptns.begin(); i != _ptns.end(); ++i)
106     {
107         state = 0;
108         for(string::const_iterator j=i->begin(); j<i->end(); ++j)
109         {
110             int next_state = ac_goto(state, *j);
111             if(0 == next_state || AC_FAIL_STATE == next_state)
112             {
113                 t.condition = *j;
114                 t.next = state_id++;
115                 goto_table[state].push_back(t);
116 
117                 goto_table.push_back(ts);
118                 output_table.push_back(ss);
119 
120                 state = t.next;
121             }
122             else
123                 state = next_state;
124         }
125         output_table[state].push_back(*i);
126     }
127   
128     return 0;
129 }
130 
131 
132 int  ac_creat_fail_table()
133 {
134     if(goto_table.empty())
135         return -1;
136 
137     fail_table.resize(goto_table.size());
138     for(size_t i=0; i<goto_table.size(); ++i)
139         fail_table[i] = AC_UNDEF_FAIL;
140 
141     queue<int>  q;
142     for(vector<ac_transition>::const_iterator i = goto_table[0].begin();
143         i != goto_table[0].end(); ++i)
144     {
145         fail_table[i->next] = 0;
146         q.push(i->next);
147     }
148 
149     int  state;
150     while(!q.empty())
151     {
152         state = q.front();  q.pop();
153 
154         for(vector<ac_transition>::const_iterator i = goto_table[state].begin();
155             i != goto_table[state].end(); ++i)
156         {
157             if(AC_UNDEF_FAIL != fail_table[i->next])
158                 continue;
159 
160             q.push(i->next);
161 
162             int  prev_state = state, ret;
163             do 
164             {
165                 prev_state = fail_table[prev_state];
166                 ret = ac_goto(prev_state, i->condition);
167             } while (AC_FAIL_STATE == ret);
168 
169             fail_table[i->next] = ret;
170             
171             for(vector<string>::const_iterator j = output_table[ret].begin();
172                 j != output_table[ret].end(); ++j)
173             {
174                 vector<string>::const_iterator sret =
175                     find(output_table[i->next].begin(), output_table[i->next].end(), *j);
176                 if(output_table[i->next].end() == sret)
177                     output_table[i->next].push_back(*j);
178             }
179         }
180     }
181 
182     fsa_type = FSA_NFA;
183 
184     return 0;
185 }
186 
187 
188 int  ac_convert_to_DFA()
189 {
190     if(fsa_type != FSA_NFA)
191         return -1;
192 
193     if(goto_table.empty() || fail_table.empty())
194         return -1;
195 
196     queue<int>  q;
197     for(vector<ac_transition>::const_iterator i = goto_table[0].begin();
198         i != goto_table[0].end(); ++i)
199     { q.push(i->next); }
200 
201     int  state;
202     while(!q.empty())
203     {
204         state = q.front();  q.pop();
205 
206         for(size_t c=0; c<AC_CONT_SIZE; ++c)
207         {
208             int  next_state = ac_goto(state, c);
209             if(next_state != AC_FAIL_STATE && next_state != 0)
210                 q.push(next_state);
211             else
212             {
213                 next_state = ac_goto(fail_table[state], c);
214                 if(next_state != AC_FAIL_STATE && next_state != 0)
215                 {
216                     ac_transition t;
217                     t.condition = c;
218                     t.next = next_state;
219                     goto_table[state].push_back(t);
220                 }
221             }
222         }
223     }
224 
225     fail_table.clear();
226     fsa_type = FSA_DFA;
227 
228     return 0;
229 }
230 
231 
232 void  OutputMatch(int _state, size_t _pos)
233 {
234     for(vector<string>::const_iterator i = output_table[_state].begin();
235         i != output_table[_state].end(); ++i)
236     {
237         printf("%d %s : %d\n", _state, i->c_str(), _pos - i->length());
238     }
239 }
240 
241 int  ac_search(const string& _txt)
242 {
243     if(goto_table.empty() || FSA_NULL == fsa_type)
244         return -1;
245 
246     int  state = 0;
247     string::size_type i;
248     for(i=0; i<_txt.length(); ++i)
249     {
250         char c = _txt[i];
251         if(output_table[state].size() > 0)
252             OutputMatch(state, i);
253 
254         if(FSA_NFA == fsa_type)
255         {
256             while(AC_FAIL_STATE == ac_goto(state, c))
257                 state = fail_table[state];
258             state = ac_goto(state, c);
259         }
260         else if(FSA_DFA == fsa_type)
261         {
262             state = ac_goto(state, c);
263             if(AC_FAIL_STATE == state)
264                 state = 0;
265         }
266     }
267 
268     if(output_table[state].size() > 0)
269         OutputMatch(state, i);
270 
271     return 0;
272 }
273 
274 
275 int  ac_print_goto_table()
276 {
277     if(goto_table.empty())
278         return -1;
279 
280     int  state_id = 0;
281     for(vector<vector<ac_transition>>::const_iterator i = goto_table.begin();
282         i != goto_table.end(); ++i, ++state_id)
283     {
284         printf("%d: ", state_id);
285 
286         if(FSA_NFA == fsa_type)
287             printf("%d ", fail_table[state_id]);
288 
289         for(vector<ac_transition>::const_iterator j = i->begin();
290             j != i->end(); ++j)
291         {
292             printf("%c->%d ", j->condition, j->next);
293         }
294 
295         for(vector<string>::const_iterator j = output_table[state_id].begin();
296             j != output_table[state_id].end(); ++j)
297         {
298             printf("(%s) ", j->c_str());
299         }
300         printf("\n");
301     }
302     printf("\n");
303 
304     return 0;
305 }
字符串模式匹配算法2 - AC算法

 


输出结果:

字符串模式匹配算法2 - AC算法
0: -1 h->1 s->3
1: 0 e->2 i->6
2: 0 r->8 (he)
3: 0 h->4
4: 1 e->5
5: 2 (she) (he)
6: 0 s->7
7: 3 (his)
8: 0 s->9
9: 3 (hers)

5 she : 1
5 he : 2
9 hers : 2

0: h->1 s->3 1: e->2 i->6 h->1 s->3 2: r->8 h->1 s->3 (he) 3: h->4 s->3 4: e->5 h->1 i->6 s->3 5: h->1 r->8 s->3 (she) (he) 6: s->7 h->1 7: h->4 s->3 (his) 8: s->9 h->1 9: h->4 s->3 (hers) 5 she : 1 5 he : 2 9 hers : 2
字符串模式匹配算法2 - AC算法

 

参考资料:

【1】《Efficient String Matching: An Aid to Bibliographic Search》 - Alfred V. Aho & Margaret J. Corasick, 贝尔实验室

字符串模式匹配算法2 - AC算法

上一篇:切换日志是否更新检查点?


下一篇:HDU 1073