彻底理解AC多模式匹配算法

发布时间：2017-01-10 11:23:31.44作者：文章转自网络，版权归原作者所有，反馈可立刻删除

一、原理

AC自动机首先将模式组记录为Trie字典树的形式，以节点表示不同状态，边上标以字母表中的字符，表示状态的转移。根节点状态记为0状态，表示起始状态。当一个状态处有一个模式串终结则标记一下。

目前流传较多的讲解多大同小异，尤其是配图，基本采用的是Aho和Corasiek两位巨巨的文章efficient string matching an aid to bibliographic search里的，窃以为那张示意图存在失配点靠前的特点（什么是失配？往下看），看起来稍稍费劲。

我找了样例画了一套新图，主要目标是通过稍微的夸张（失配点远离）让过程更清晰。

photoshop培训,电脑培训,电脑维修培训,移动软件开发培训,网站设计培训,网站建设培训

匹配的过程是：从0状态起点开始，以字符流输入，进行适当的状态转移，如果可以抵达某一标记终结的状态，则成功匹配模式，串值为从0到终结点的路径。

按照传统的说法，状态机有三个主要函数支撑：goto（状态正常转移），fail（状态失配转移），output（传回匹配结果），而我认为与其规定是具体的函数，倒不如说是三个功能的模块，有不同于函数的实现形式。

Trie树的建立是简单的，在此基础上我们要完善更多的数据结构，实现goto的功能。

goto是自动机基本的状态转移过程，很好想，就是在建立Trie树时让每个状态维护一组指针（广义的），使得在每一状态对于输入都可以正确转移，没有对应的则报错（现在回答刚才的问题，什么是失配？失配就是一个状态接受了无法转移的字符，记fail）。除了字典树中的树枝以外，还有一个转移就是在开始节点，对于不能流进自动机的字符，不报错而是再一次转到开始节点（如上图示），很好理解，对于待匹配串λthis，λ为不含t，h的任意串，真正的模式匹配是在去除了它以后开始的。（当然还有其他的用意，坑稍后填）

好了，正常的状态流转已经建立好了，现在看失配时我们的状态流何去何从。举一个栗子，如果输入thip这个串，状态的流转应该如下图：

photoshop培训,电脑培训,电脑维修培训,移动软件开发培训,网站设计培训,网站建设培训

那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，我们都喜欢hip-hop~：

photoshop培训,电脑培训,电脑维修培训,移动软件开发培训,网站设计培训,网站建设培训

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 <cstdlib>  2 #include <set>  3 #include <string>  4 #include <vector>  5 #include <queue>  6 #include <iostream>  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<StateNode *> transition_table_{ vector<StateNode *>(ALPHABET_NUMBER) }; 19 }; 20  21 class ACSM 22 { 23 private: 24     StateNode *start_node_; 25     int state_count_; 26     vector<StateNode *> corresponding_node_; 27     vector<StateNode *> 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<StateNode *> q; 74         fail_ = std::move(vector<StateNode *>(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 matching106     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 }

分类导航

彻底理解AC多模式匹配算法

一、原理

二、关于自动机的数据结构表示

三、完整代码

网友评论

更多精彩分享