首页 > 代码库 > Aho-Corasick 算法
Aho-Corasick 算法
最近在研究一些字符串匹配算法，也是由于工作上的需要，强力推荐一本书《柔性字符串匹配》，一本很好的书。网上可以随时搜索到。还是说正题吧。我的前几天研究了一下多模式匹配算法，选了Aho-Corasick算法，因为这个比较基础，相比其他多模式匹配算法其要容易理解的多。所以，现在简单总结一下书上的内容，加深自己的理解。
首先了解一下多模式匹配，就是同时搜索多个模式串。其实都是基于单模式串扩展而来的。所以其也有三种匹配模式。
第一：基于前缀搜索模式，代表有mutilple shift-and 算法和我前几天研究的Aho-Corasick 算法，
第二：基于后缀搜索模式，代表有Commentz-Walter算法，set Horspool 算法和他的改进Wu-Manber算法，有兴趣和时间的话，可以研究研究，可以查阅《柔性字符串匹配》这本书和其他参考文献。
第三：基于子串的搜索模式，代表有MultiBDM,SBDM算法，还有SBOM算法（在模式串集合越大效率越高），自己研究过了解一些基本的机制和原理，但是据说代码实现很麻烦，也迟迟没有动手（感觉是在为自己找借口了）。但是如果我近期的任务要是完成的话，一定实现，从细节来理解SBOM算法。
介绍了大概情况，开始总结自己所看的Aho-Corasick算法吧，搜索过程，对于它的原理做简单的介绍。我们主要的问题就是要找在读入文本串t1t2...ti后，找既是t1t2...ti后缀，同时也是某个模式串的前缀的最长字符串。为了解决这个问题，书本引入了Aho-Corasick自动机，为了实现自动机，又引入了Trie树结构（后面再来说明，其具体的内容）。自动机对应的是状态的转化，其实对Trie树的扩展，用q表示模式串P对应的Trie状态，用L（q）表示从初始状态到q的路径上的标号组成的字符串。SA(q)定义为自动机的另一个状态q´，是的L（q´）是L（q）最长后缀（注意理解这句话）。我们将开始状态置为θ（我们可以认为它是空的状态），我们举一个书上的例子，假设已经读入了t1t2...ti后，现在记这个串的最长后缀v=L（Current）,它的状态为为SA（Current），已经建好了，现在当读入一个新的ti+1并计算t1t2...titi+1最长后缀u。这时会出现两种情况：
第一：如果Current存在的ti+1的转移，到目的状态f，这表明uti+1为t1t2...titi+1的最长后缀，也是某一个模式串的前缀。我们处理时，只需要将f状态变成Current状态。
第二：如果Current不存在的ti+1的转移（Trie树上无法继续识别ti+1）我们就沿着SA（Current）回溯，直到：
1：找到一个q状态，它存在ti+1的转移，那么我们认为L（q）u是t1t2...titi+1的最长后缀。我们将q的ti+1转移的目的状态f成新的状态，并且u=L（f）即L（q）u。
2：如果到达了θ，那么我们要找的t1t2...titi+1的最长后缀为空ε，我们可以从Current状态跳到开始状态。
下面给一个书上的图来描述自动机的功能比较清晰有助于理解搜索匹配：
我们发现如果L（ACGATA）,假设：P={ATATATA, TATAT, ACGATAT}.如果我们匹配到L（15），发现既是它的最长后缀，又是某个模式串的前缀的串是ATA。对应的状态为7。
构建自动机是将Trie树按层次遍历来的，下面是书本上根据上面理论写搜索匹配算法的伪代码：
现在要回来介绍一下Trie树，即它的构造。准确来说它只是个数据结构，而且是多叉树。每个节点的孩子节点数为∑（字符表系统中的字符种类）个，这个很好构建，给出书上的伪代码为：
自动机构建，和搜索类似，上面也提到了一些关于自动机的功能和其基本的原理，我们现在只需要对SA(Current)进行构建了，我们构建自动机，是将Trie树按层次遍历而来的，其过程，假设Current的父节点Parent。Parent到Current的标号为σ，即Current=δAC（Parent，σ）。因为是层次遍历，SAC（Parent）已经算出来了，要搜索v=L（Current）的最长后缀u，它同时也是某个模式串的前缀，。v可以写成v´σ的形式，如果u不是空字符，那么u（已经是v的后缀了）一定是u´σ，并且u´一定是v´后缀。
如果SAC（Parent）的标号为σ的转移，并且目标状态的转移为h，则w=L（SAC（Parent））是v´的最长后缀，并且wσ就是更新的最长路径u，这样可以SA(Current)指向h。
如果SAC（Parent）的标号为没有σ的转移，那就考虑SAC（SAC（Parent）），依次类推。
下面给书上的伪代码可以助于理解：
下面是自己写的源代码，这是头文件，供参考：
1 #ifndef AHOCORASICK_H 2 #define AHOCORASICK_H 3 4 #include<string> 5 #include<vector> 6 #include<queue> 7 8 #define KINDOFALPHABET 256 9 10 class CAcMatchString11 {12 private:13 struct SAcNode14 {15 SAcNode *pParent;16 SAcNode *pBack;17 std::vector<unsigned int> WordTag;18 SAcNode *child[KINDOFALPHABET];19 SAcNode()20 {21 pParent = NULL;22 pBack = NULL;23 memset(child, NULL, sizeof(child));24 }25 ~SAcNode(){}26 };27 28 SAcNode *m_pRoot;29 30 void __createTrie(const std::vector<std::string>& vPatternStrVec, SAcNode *voRoot);31 void __traverseLevel(SAcNode *pRoot, std::vector<SAcNode*>& voAlphabet) const;32 void __buildAhoCroasickAutomaton(SAcNode *vRoot);33 void __delTrie(SAcNode* vRoot);34 void __markOcurrence(const SAcNode *pOcurrence, unsigned int vPos, std::vector<std::vector<unsigned int> >& voMatchPosVec, unsigned int vState) const;35 36 public:37 CAcMatchString();38 ~CAcMatchString();39 void matchString(const std::string& vSrcStr, const std::vector<std::string>& vPatternStrVec, std::vector<std::vector<unsigned int> >& voMatchPosVec);40 41 };42 43 #endif
建立一个cpp文件：
1 #include<iostream> 2 #include"AhoCorasick.h" 3 4 CAcMatchString::CAcMatchString() 5 { 6 m_pRoot = new SAcNode(); 7 } 8 9 CAcMatchString::~CAcMatchString() 10 { 11 __delTrie(m_pRoot); 12 } 13 14 //******************************* 15 //FUNCTION: 16 void CAcMatchString::__createTrie(const std::vector<std::string>& vPatternStrVec, SAcNode *voRoot) 17 { 18 SAcNode *pStringTemp = voRoot; 19 unsigned int AlphabetIndex; 20 21 for(std::vector<std::string>::size_type i=0; i!=vPatternStrVec.size(); ++i) 22 { 23 pStringTemp = voRoot; 24 for(std::string::size_type k=0; k!=vPatternStrVec[i].size(); ++k) 25 { 26 AlphabetIndex = unsigned int ((vPatternStrVec[i])[k]); 27 if(pStringTemp->child[AlphabetIndex] == NULL) 28 { 29 pStringTemp->child[AlphabetIndex] = new SAcNode(); 30 pStringTemp->child[AlphabetIndex]->pParent = pStringTemp; 31 } 32 pStringTemp = pStringTemp->child[AlphabetIndex]; 33 } 34 pStringTemp->WordTag.push_back(i); 35 } 36 } 37 38 //******************************* 39 //FUNCTION: 40 void CAcMatchString::__traverseLevel(SAcNode *pRoot, std::vector<SAcNode*>& voAlphabet) const 41 { 42 std::queue<SAcNode*> AlphabetQueue; 43 SAcNode *pStringTempSearch = pRoot; 44 AlphabetQueue.push(pStringTempSearch); 45 while(!AlphabetQueue.empty()) 46 { 47 pStringTempSearch = AlphabetQueue.front(); 48 AlphabetQueue.pop(); 49 voAlphabet.push_back(pStringTempSearch); 50 for(unsigned int i=0; i<KINDOFALPHABET; i++) 51 { 52 if(pStringTempSearch->child[i] != NULL) 53 AlphabetQueue.push(pStringTempSearch->child[i]); 54 } 55 } 56 } 57 58 //******************************* 59 //FUNCTION: 60 void CAcMatchString::__buildAhoCroasickAutomaton(SAcNode *vRoot) 61 { 62 std::vector<SAcNode*> AutomatonInLevelOrder; 63 vRoot->pBack = NULL; 64 __traverseLevel(vRoot, AutomatonInLevelOrder); 65 std::vector<SAcNode*>::iterator IterAcNode = AutomatonInLevelOrder.begin(); 66 while(IterAcNode != AutomatonInLevelOrder.end()) 67 { 68 SAcNode *pParent = (*IterAcNode)->pParent; 69 if(pParent == NULL) 70 { 71 IterAcNode++; 72 continue; 73 } 74 unsigned int Index = 0; 75 for( ; Index<=KINDOFALPHABET; Index++) 76 { 77 if(pParent->child[Index] == (*IterAcNode)) 78 break; 79 } 80 SAcNode* pRecall = pParent->pBack; 81 while(pRecall != vRoot && pRecall != NULL && pRecall->child[Index] == NULL) 82 pRecall = pRecall->pBack; 83 if(pRecall != NULL && pRecall->child[Index] != NULL) 84 { 85 (*IterAcNode)->pBack = pRecall->child[Index]; 86 if(pRecall->child[Index]->WordTag.size() != 0) 87 { 88 std::vector<unsigned int>::iterator IterCopy = pRecall->child[Index]->WordTag.begin(); 89 while(IterCopy != pRecall->child[Index]->WordTag.end()) 90 { 91 (*IterAcNode)->WordTag.push_back(*IterCopy); 92 IterCopy++; 93 } 94 } 95 } 96 else 97 { 98 if((*IterAcNode) != vRoot) 99 (*IterAcNode)->pBack = vRoot;100 }101 IterAcNode++;102 }103 }104 105 //*******************************106 //FUNCTION:107 void CAcMatchString::__delTrie(SAcNode* vRoot)108 {109 for(unsigned int i=0; i<KINDOFALPHABET; i++)110 {111 if(vRoot->child[i] != NULL)112 __delTrie(vRoot->child[i]);113 }114 delete vRoot;115 }116 117 //*******************************118 //FUNCTION:119 void CAcMatchString::__markOcurrence(const SAcNode *pOcurrence, unsigned int vPos, std::vector<std::vector<unsigned int> >& voMatchPosVec, unsigned int vState) const120 {121 unsigned int StringIndex = (unsigned int) (pOcurrence->WordTag[vState]);122 (voMatchPosVec[StringIndex]).push_back(vPos);123 }124 125 //*******************************126 //FUNCTION:127 void CAcMatchString::matchString(const std::string& vSrcStr, const std::vector<std::string>& vPatternStrVec, std::vector<std::vector<unsigned int> >& voMatchPosVec)128 {129 __createTrie(vPatternStrVec, m_pRoot);130 __buildAhoCroasickAutomaton(m_pRoot);131 SAcNode *pCurrent = m_pRoot;132 133 unsigned int NumString = (unsigned int) vPatternStrVec.size();134 voMatchPosVec.resize(NumString);135 136 for(std::string::size_type StrPos=0; StrPos!=vSrcStr.size(); StrPos++)137 {138 unsigned int IndexOfChar = (unsigned int) (vSrcStr[StrPos]);139 while(pCurrent != NULL && pCurrent->child[IndexOfChar] == NULL && pCurrent->pBack != NULL)140 pCurrent = pCurrent->pBack;141 142 if(pCurrent != NULL && pCurrent->child[IndexOfChar] != NULL)143 {144 pCurrent = pCurrent->child[IndexOfChar];145 }146 else147 {148 pCurrent = m_pRoot;149 }150 151 if(pCurrent->WordTag.size() != 0)152 {153 std::vector<unsigned int>::size_type State = 0;154 while(State != pCurrent->WordTag.size())155 {156 unsigned int StatePos = pCurrent->WordTag[State];157 unsigned int CurrentSize = vPatternStrVec[StatePos].size();158 __markOcurrence(pCurrent, StrPos-CurrentSize+1, voMatchPosVec, State);159 State++;160 }161 }162 }163 }164 165 //*******************************166 //FUNCTION:167 int main(void)168 {169 std::string SrcStr = "AAAAAAA";170 std::string PatternStrF = "AAAAAA";171 std::string PatternStrS = "AAAA";172 std::string PatternStrT = "AAA";173 174 std::vector<std::string> PatternStrVec;175 PatternStrVec.push_back(PatternStrF);176 PatternStrVec.push_back(PatternStrS);177 PatternStrVec.push_back(PatternStrT);178 179 std::vector<std::vector<unsigned int> > MatchPosVec;180 CAcMatchString StringMatch;181 StringMatch.matchString(SrcStr, PatternStrVec, MatchPosVec);182 for(unsigned int NumString=0; NumString!=MatchPosVec.size(); NumString++)183 {184 std::cout<<"the "<<(NumString+1)<<"th string position are: ";185 if((unsigned int)MatchPosVec[NumString].size() == 0)186 {187 std::cout<<"None";188 std::cout<<std::endl;189 std::cout<<std::endl;190 continue;191 }192 for(unsigned int NumPos=0; NumPos!=MatchPosVec[NumString].size(); NumPos++)193 {194 std::cout<<MatchPosVec[NumString][NumPos]<<" ";195 }196 std::cout<<std::endl;197 std::cout<<std::endl;198 }199 200 system("pause");201 return 0;202 }
Aho-Corasick 算法