首页 / 算法 / 字符串模式匹配算法2 - AC算法
字符串模式匹配算法2 - AC算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了字符串模式匹配算法2 - AC算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含10172字，纯文字阅读大概需要15分钟。
内容图文
讨论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样东西：
- 状态跳转表goto ：决定对于当前状态S和条件C，如何得到下一状态S‘
- 失配跳转表fail ： 决定goto表得到的下一状态无效时，应该回退到哪一个状态
- 匹配结果输出表output ： 决定在哪个状态时输出哪个恰好匹配的模式
原理比较抽象，下面以一个简单而且经典的例子（来自于AC算法创始人的论文）来演示一下AC算法的原理及goto、fail、output这3个表的构建。设多模式为 {“he”, “she”, “his”, “hers”}。下面来一步一步构建FSA。
首先规定一个初始状态0，接着依次处理多个模式串，首先是he：
每个圆圈代表一个状态(State)，圆圈中的数字表示状态的编号；有向箭头代表状态的转换，它由当前状态指向下一状态，箭头上的字符表示此次状态转换的条件。
接下来是she，注意每处理一个模式串时，都要先回到起始状态0：
注意，如果给定条件C，从当前状态出发能转换到一个有效状态，那么只进行状态转换，而不创建新状态，这一点在处理后面两个模式串时可以看到。接着是his：
最后是hers，而且AC规定，当当前状态为初始状态（0）时，对于任意条件C来，都能转换到有效状态（这也避免了回退的死循环），因此，除了条件h和s外，对其他任意条件，状态0还应转换至状态0：
其实，最后的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形式。
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>
10usingnamespace std;
11 12 13#define AC_FAIL_STATE -1
14#define AC_UNDEF_FAIL -1
15#define AC_CONT_SIZE 256
16 17 18struct ac_transition
19{
20char condition;
21int next;
22};
23 24enum FSAType
25{
26 FSA_NULL = 0,
27 FSA_NFA,
28 FSA_DFA
29};
30 31 32struct ac_state_finder :
33public binary_function<ac_transition, char, bool>
34{
35booloperator() (const ac_transition& t, char c) const 36 {
37return (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 48int ac_goto(int _state, char _cont);
49int ac_creat_goto_table(const vector<string>& _ptns);
50int ac_creat_fail_table();
51int ac_convert_to_DFA();
52int ac_print_goto_table();
53int ac_search(conststring& _txt);
54 55 56int main(int argc, char** argv)
57{
58string ss[4] = {"he", "she", "his", "hers"};
59 vector<string> ptns(ss, ss+4);
60string 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 71return0;
72}
73 74 75int 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));
80if(goto_table[_state].end() == ret)
81 {
82if(0 == _state)
83return0;
84else 85return AC_FAIL_STATE;
86 }
87else 88return ret->next;
89}
90 91 92int ac_creat_goto_table(const vector<string>& _ptns)
93{
94int state = 0;
95int state_id = 0;
96 97 ac_transition t;
98 vector<ac_transition> ts;
99 vector<string> ss;
100101 goto_table.push_back(ts);
102 output_table.push_back(ss);
103 state_id++;
104105for(vector<string>::const_iterator i = _ptns.begin(); i != _ptns.end(); ++i)
106 {
107 state = 0;
108for(string::const_iterator j=i->begin(); j<i->end(); ++j)
109 {
110int next_state = ac_goto(state, *j);
111if(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);
116117 goto_table.push_back(ts);
118 output_table.push_back(ss);
119120 state = t.next;
121 }
122else123 state = next_state;
124 }
125 output_table[state].push_back(*i);
126 }
127128return0;
129}
130131132int ac_creat_fail_table()
133{
134if(goto_table.empty())
135return -1;
136137 fail_table.resize(goto_table.size());
138for(size_t i=0; i<goto_table.size(); ++i)
139 fail_table[i] = AC_UNDEF_FAIL;
140141 queue<int> q;
142for(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 }
148149int state;
150while(!q.empty())
151 {
152 state = q.front(); q.pop();
153154for(vector<ac_transition>::const_iterator i = goto_table[state].begin();
155 i != goto_table[state].end(); ++i)
156 {
157if(AC_UNDEF_FAIL != fail_table[i->next])
158continue;
159160 q.push(i->next);
161162int prev_state = state, ret;
163do164 {
165 prev_state = fail_table[prev_state];
166 ret = ac_goto(prev_state, i->condition);
167 } while (AC_FAIL_STATE == ret);
168169 fail_table[i->next] = ret;
170171for(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);
176if(output_table[i->next].end() == sret)
177 output_table[i->next].push_back(*j);
178 }
179 }
180 }
181182 fsa_type = FSA_NFA;
183184return0;
185}
186187188int ac_convert_to_DFA()
189{
190if(fsa_type != FSA_NFA)
191return -1;
192193if(goto_table.empty() || fail_table.empty())
194return -1;
195196 queue<int> q;
197for(vector<ac_transition>::const_iterator i = goto_table[0].begin();
198 i != goto_table[0].end(); ++i)
199 { q.push(i->next); }
200201int state;
202while(!q.empty())
203 {
204 state = q.front(); q.pop();
205206for(size_t c=0; c<AC_CONT_SIZE; ++c)
207 {
208int next_state = ac_goto(state, c);
209if(next_state != AC_FAIL_STATE && next_state != 0)
210 q.push(next_state);
211else212 {
213 next_state = ac_goto(fail_table[state], c);
214if(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 }
224225 fail_table.clear();
226 fsa_type = FSA_DFA;
227228return0;
229}
230231232void OutputMatch(int _state, size_t _pos)
233{
234for(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}
240241int ac_search(conststring& _txt)
242{
243if(goto_table.empty() || FSA_NULL == fsa_type)
244return -1;
245246int state = 0;
247string::size_type i;
248for(i=0; i<_txt.length(); ++i)
249 {
250char c = _txt[i];
251if(output_table[state].size() > 0)
252 OutputMatch(state, i);
253254if(FSA_NFA == fsa_type)
255 {
256while(AC_FAIL_STATE == ac_goto(state, c))
257 state = fail_table[state];
258 state = ac_goto(state, c);
259 }
260elseif(FSA_DFA == fsa_type)
261 {
262 state = ac_goto(state, c);
263if(AC_FAIL_STATE == state)
264 state = 0;
265 }
266 }
267268if(output_table[state].size() > 0)
269 OutputMatch(state, i);
270271return0;
272}
273274275int ac_print_goto_table()
276{
277if(goto_table.empty())
278return -1;
279280int state_id = 0;
281for(vector<vector<ac_transition>>::const_iterator i = goto_table.begin();
282 i != goto_table.end(); ++i, ++state_id)
283 {
284 printf("%d: ", state_id);
285286if(FSA_NFA == fsa_type)
287 printf("%d ", fail_table[state_id]);
288289for(vector<ac_transition>::const_iterator j = i->begin();
290 j != i->end(); ++j)
291 {
292 printf("%c->%d ", j->condition, j->next);
293 }
294295for(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");
303304return0;
305 }
输出结果：
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
参考资料：
【1】《Efficient String Matching: An Aid to Bibliographic Search》 - Alfred V. Aho & Margaret J. Corasick, 贝尔实验室
原文：http://www.cnblogs.com/zzqcn/p/3525636.html
内容总结
以上是互联网集市为您收集整理的字符串模式匹配算法2 - AC算法全部内容，希望文章能够帮你解决字符串模式匹配算法2 - AC算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。