(本文尤其适合遍览网上的讲解而仍百思不得姐的同学)
AC 自动机首先将模式组记录为 Trie 字典树的形式,以节点表示不同状态,边上标以字母表中的字符,表示状态的转移。根节点状态记为 0 状态,表示起始状态。当一个状态处有一个模式串终结则标记一下。
目前流传较多的讲解多大同小异,尤其是配图,基本采用的是 Aho 和 Corasiek 两位巨巨的文章 efficient string matching an aid to bibliographic search 里的,窃以为那张示意图存在失配点靠前的特点(什么是失配?往下看),看起来稍稍费劲。
我找了样例画了一套新图,主要目标是通过稍微的夸张(失配点远离)让过程更清晰。
匹配的过程是:从 0 状态起点开始,以字符流输入,进行适当的状态转移,如果可以抵达某一标记终结的状态,则成功匹配模式,串值为从 0 到终结点的路径。
按照传统的说法,状态机有三个主要函数支撑:goto(状态正常转移),fail(状态失配转移),output(传回匹配结果),而我认为与其规定是具体的函数,倒不如说是三个功能的模块,有不同于函数的实现形式。
Trie 树的建立是简单的,在此基础上我们要完善更多的数据结构,实现 goto 的功能。
goto 是自动机基本的状态转移过程,很好想,就是在建立 Trie 树时让每个状态维护一组指针(广义的),使得在每一状态对于输入都可以正确转移,没有对应的则报错(现在回答刚才的问题,什么是失配?失配就是一个状态接受了无法转移的字符,记 fail)。除了字典树中的树枝以外,还有一个转移就是在开始节点,对于不能流进自动机的字符,不报错而是再一次转到开始节点(如上图示),很好理解,对于待匹配串λthis,λ为不含 t,h 的任意串,真正的模式匹配是在去除了它以后开始的。(当然还有其他的用意,坑稍后填)
好了,正常的状态流转已经建立好了,现在看失配时我们的状态流何去何从。举一个栗子,如果输入 thip 这个串,状态的流转应该如下图:
那 3 状态处报错后应该怎么处理呢?最好想的方法当然是错开一位,再从头开始匹配(这种方法就像一位老人家曾经说过,太年轻太简单,有时还很幼稚),AC 二位的办法是——利用图中的关系计算出一套跳转关系——在 x 点处失配的串不打回开头来过,而是跳到 y 点——继续匹配当前字符。这套规则叫做失配函数,也就是 fail 功能模块。要点在于当前字符不向前回溯,想想着很适合字符流的关键字匹配对不对。
好了,告诉大家 3 状态的失配跳转在 6 状态,先不用管怎么得到的,想想这个过程:3 得到 p 字符,失配,凭 goto 无法转移状态,使用失配时通用的 fail,状态跳至 6,接受 p——还是这个字符,成功匹配到终结状态 7。单趟遍历目标串,cool。
当然这套规则是需要小心计算的。采用的方法很巧妙,在树形结构中很像广度优先搜索 BFS,数学形式又很像动态规划 DP。
正式开始之前请认真思考这个情况:已知 2 状态的失配跳转为 5,怎么求 3 状态的失配跳转?从图中很容易看出,2 通过 i 流向 3,而 5 恰有对 i 的 goto,自然地,3 失配时可以跳转至 6,哒哒
现在我把图小小地改动一下,把 hip 变成 hop:
2 的失配跳转仍然是 5,然而对于所有使 2 不失配的字符,5 都没有合适的 goto——即会在 5 也失配,此种情况怎么求 3 的失配跳转?
请仔细读这两句话:
2 的失配跳转说明不能采用前缀 th
5 的失配跳转说明不能采用前缀 h(现在不要想 2 的事情了,单独想 5)
——失配跳转实际上是一个逐字符推后匹配模式前缀的过程
那么既然 h 开头的也不能匹配模式了,那么对于目标串,要从 i 开始匹配了——下一次状态就是 5 的失配跳转 0!
这是一个向前递归的过程,而前面提到 0 的大量无匹配字符均指回 0 自己则巧妙地保证了这个递归会最不济也在会 0 处停下:这种时候则是放弃之前的全部前缀从当前字符重新开始尝试匹配了,对吧。
我要强调,失配跳转的过程中当前字符是不变的。
至此,我们也完整的构造了 fail 模块的规则。
output 需要做的则是对匹配路径上的每一状态,检查是否为一个模式的终结,如果是,用一种合适的方式传回这个匹配的结果。
Another question!目标串全部模式匹配:在匹配到一个模式后,应当驱动自动机继续无遗漏地匹配下一个出现的模式(这个下一模式也许会和已匹配的部分或全部重叠),我再次重复这句话,失配跳转实际上是一个逐字符推后匹配模式前缀的过程,那么应该很简单了吧,匹配到一个模式后自然一次失配跳转就行了!自动机会把前缀去掉一个字符继续匹配。
我在原理中避开一个一定要解释清楚的问题,就是自动机的数据结构实现。Aho & Corasiek 的论文中称为 goto/fail/output function, 与其理解为函数倒不如说是功能,因为它们的实现不必是有输入输出的函数,而可以是向更直接的数据结构直接查询。
我实践中认为易于实现的写法:goto 功能就可以实现在结点结构中,每个状态维护一个转向结点的指针,无效则置空;fail 即可以是一张自动机维护的表;output 在结点中标记是否终结,如果终结,状态结点存储模式串,检测到终结直接传回。
- 1#include 2#include < set > 3#include < string > 4#include 5#include 6#include 7 8 using namespace std;
- 9 10#define ALPHABET_NUMBER 26 11 12 struct StateNode 13 {
- 14 bool finish_ {
- false
- };
- 15 int state_ {
- 0
- };
- 16 string pattern_ {};
- 17 //goto table
- 18 vector transition_table_ {
- vector(ALPHABET_NUMBER)
- };
- 19
- };
- 20 21 class ACSM 22 {
- 23 private: 24 StateNode * start_node_;
- 25 int state_count_;
- 26 vector corresponding_node_;
- 27 vector fail_;
- 28 public: 29 ACSM() : start_node_ {
- new StateNode()
- },
- state_count_ {
- 0
- }
- 30 {
- 31 //state0 is start_node_
- 32 corresponding_node_.push_back(start_node_);
- 33
- }
- 34 //read all patterns and produce the goto table
- 35 void load_pattern(const vector < string > &_Patterns) 36 {
- 37 int latest_state = 1;
- 38
- for (const auto & pattern: _Patterns) 39 {
- 40 auto * p = start_node_;
- 41
- for (int i = 0; i < pattern.size(); ++i) 42 {
- 43 auto * next_node = p - >transition_table_[pattern[i] - 'a'];
- 44
- if (next_node == nullptr) 45 {
- 46 next_node = new StateNode();
- 47
- }
- 48
- if (next_node - >state_ == 0) 49 {
- 50 next_node - >state_ = latest_state++;
- 51 //update the table
- 52 corresponding_node_.push_back(next_node);
- 53
- }
- 54 //the goto table
- 55 p - >transition_table_[pattern[i] - 'a'] = next_node;
- 56 p = next_node;
- 57
- }
- 58 p - >finish_ = true;
- 59 p - >pattern_ = pattern;
- 60
- }
- 61
- for (int i = 0; i < ALPHABET_NUMBER; ++i) 62 {
- 63
- if (start_node_ - >transition_table_[i] == nullptr) 64 {
- 65 start_node_ - >transition_table_[i] = start_node_;
- 66
- }
- 67
- }
- 68 state_count_ = latest_state;
- 69
- }
- 70 //produce fail function
- 71 void dispose() 72 {
- 73 queue q;
- 74 fail_ = std: :move(vector(state_count_));
- 75
- for (const auto nxt: start_node_ - >transition_table_) 76 {
- 77 //d=1,f=0
- 78
- if (nxt - >state_ != 0) 79 {
- 80 fail_[nxt - >state_] = start_node_;
- 81 q.push(nxt);
- 82
- }
- 83
- }
- 84 //calculate all fail redirection
- 85
- while (!q.empty()) 86 {
- 87 auto known = q.front();
- 88 q.pop();
- 89
- for (int i = 0; i < ALPHABET_NUMBER; ++i) 90 {
- 91 auto nxt = known - >transition_table_[i];
- 92
- if (nxt && nxt - >state_ != 0) 93 {
- 94 auto p = fail_[known - >state_];
- 95
- while (!p - >transition_table_[i]) 96 {
- 97 p = fail_[p - >state_];
- 98
- }
- 99 fail_[nxt - >state_] = p - >transition_table_[i];
- 100 q.push(nxt);
- 101
- }
- 102
- }
- 103
- }
- 104
- }
- 105 //search matching
- 106 void match(const string & _Str, set < string > &_S) 107 {
- 108 auto p = start_node_;
- 109
- for (int i = 0; i < _Str.size(); ++i) 110 {
- 111 int trans = _Str[i] - 'a';
- 112 p = 113 p - >transition_table_[trans] 114 ? p - >transition_table_[trans] 115 : (--i, fail_[p - >state_]);
- 116
- if (p - >finish_) 117 {
- 118 _S.insert(p - >pattern_);
- 119
- }
- 120
- }
- 121
- }
- 122
- };
- 123 124 int main() 125 {
- 126 ACSM acsm;
- 127 vector < string > patterns {
- "his",
- "hers",
- "she",
- "he"
- };
- 128 set < string > matched;
- 129 acsm.load_pattern(patterns);
- 130 acsm.dispose();
- 131 string str {
- "hishers"
- };
- 132 acsm.match(str, matched);
- 133
- for (const auto str: matched) cout << str << endl;
- 134 system("pause");
- 135
- return 0;
- 136
- }
谢谢阅读
来源: