文章目錄

• • 1. 多模式串匹配
  • 2. 經(jīng)典多模式串匹配--AC自動(dòng)機(jī)
  • • 2.1 AC自動(dòng)機(jī)構(gòu)建
    • 2.2 在AC自動(dòng)機(jī)上匹配主串
    • 2.3 復(fù)雜度分析
  • 3. python包

1. 多模式串匹配

• 前面學(xué)的BF、RK、BM、KMP都是單模式串匹配算法（一個(gè)模式串，一個(gè)主串）
• 多模式串匹配，即在一個(gè)主串中查找多個(gè)模式串（Trie樹是多模式匹配）
• 比如實(shí)現(xiàn)多個(gè)敏感詞過濾；單模式需要一遍遍的，掃描，過濾，掃描，過濾；多模式掃描一遍，過濾完成

2. 經(jīng)典多模式串匹配–AC自動(dòng)機(jī)

AC自動(dòng)機(jī)算法（Aho-Corasick算法），是在Trie樹之上，加了類似 KMP 的 next 數(shù)組。

class ACNode //AC自動(dòng)機(jī)的Trie樹節(jié)點(diǎn)類,假設(shè)只有26個(gè)字母的數(shù)據(jù)集 { public:char data;ACNode *children[charNum];size_t count; //記錄這個(gè)節(jié)點(diǎn)被多少個(gè)單詞占用bool isEndOfWord;//是否是一個(gè)單詞的結(jié)束字符size_t freq; //單詞插入的頻次int length; //當(dāng)isEndOFWord為True時(shí)，記錄模式串長(zhǎng)度ACNode *fail; //失敗指針ACNode(char ch = '/'):data(ch), isEndOfWord(false),count(0), freq(0),length(-1),fail(NULL){memset(children,0,sizeof(ACNode*) * charNum);}~ACNode(){} };

2.1 AC自動(dòng)機(jī)構(gòu)建

• 1，將多個(gè)模式串插入Trie樹。
• 2，在Trie樹上構(gòu)建失敗指針（相當(dāng)于KMP中的失效函數(shù) next 數(shù)組）

void buildFailPointer() {queue<ACNode*> ACNode_queue;ACNode_queue.push(root);ACNode *p, *pchild, *q, *qchild;int i;while(!ACNode_queue.empty())//用隊(duì)列按層遍歷{p = ACNode_queue.front();//隊(duì)首的節(jié)點(diǎn)pACNode_queue.pop();for(i = 0; i < charNum; ++i){pchild = p->children[i];//找到p的非空子節(jié)點(diǎn)pcif(pchild == NULL)continue;if(p == root)pchild->fail = root;else{q = p->fail; //q為p的失效指針while(q != NULL) //q不為空{qchild = q->children[pchild->data-'a'];//字符等于pc的qcif(qchild != NULL)//qc存在{pchild->fail = qchild;//鏈接pc失敗指針到qcbreak;//找到了就跳出循環(huán)}q = q->fail;//qc不存在，就再去上一個(gè)失效點(diǎn)找}if(q == NULL)//最后找到root處還沒找到pchild->fail = root;//pc的失效指針指向root}ACNode_queue.push(pchild);//把p的非空子節(jié)點(diǎn)pc入隊(duì)}} }

2.2 在AC自動(dòng)機(jī)上匹配主串

void match(const string &maintext) //maintext是主串 {int n = maintext.size();ACNode *p = root, *temp;//模式串從root開始int index, pos;for(int i = 0; i < n; ++i)//主串從i=0開始{index = maintext[i]-'a';//子節(jié)點(diǎn)下標(biāo)while(p->children[index] == NULL && p != root){//p不為root，且 子節(jié)點(diǎn)為空（找不到那個(gè)i對(duì)應(yīng)的字符）p = p->fail; //失敗指針發(fā)揮作用的地方}p = p->children[index];if(p == NULL)p = root; //如果沒有匹配的，從root開始重新匹配temp = p;while(temp != root)//打印出可以匹配的模式串{if(temp->isEndOfWord == true){pos = i-temp->length+1;cout << "Found " << maintext.substr(pos,temp->length) << " at ""position(start from 0) "<< pos << " at " << maintext << endl;}temp = temp->fail;}} }

主程序

Trie textlib; string a("abcd"), b("bcd"), c("c"); textlib.insert(a); textlib.insert(a); textlib.insert(b); textlib.insert(c); textlib.buildFailPointer(); textlib.match("abcdc");

在Trie樹基礎(chǔ)上的AC自動(dòng)機(jī)完整代碼（請(qǐng)點(diǎn)擊查看）

2.3 復(fù)雜度分析

• 構(gòu)建AC自動(dòng)機(jī)

構(gòu)建Trie樹，時(shí)間復(fù)雜度O（m*len），其中l(wèi)en表示敏感詞平均長(zhǎng)度，m 表示敏感詞個(gè)數(shù)

構(gòu)建失敗指針，每個(gè)節(jié)點(diǎn)構(gòu)建失敗指針不會(huì)超過len次（樹的平均高度），整個(gè)失敗指針就是O（k*len）, k 是節(jié)點(diǎn)個(gè)數(shù)

• 匹配復(fù)雜度
  for循環(huán)依次遍歷主串中每個(gè)字符，for循環(huán)內(nèi)部的while復(fù)雜度O（len），總的復(fù)雜度O（n*len），敏感詞不會(huì)很長(zhǎng)，所以近似于O（n）

3. python包

https://pypi.org/project/ahocorasick-python/
https://pypi.org/project/ahocorasick-rs/

總結(jié)

以上是生活随笔為你收集整理的字符串匹配算法（AC自动机 Aho-Corasick）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。