扫一扫下方二维码,关注本站官方公众号
回复:验证码
获取永久解锁本站全部文章的验证码

Aho-Corasick算法实现类-Go语言中文社区

Aho-Corasick算法实现类


刚刚翻Aho-Corasick算法,打算看看具体情况,发现一个有趣的网页,可以提供该算法的可视化,就先占个位置,发个链接(http://blog.ivank.net/aho-corasick-algorithm-in-as3.html),今晚有空再看看。

——————

终于舍得看AC了……囧。

学习AC算法,首先要理解状态机(有限状态机)的概念,然后学会Trie的实现。接着,就可以更好的理解了。

老规矩,拿篇感觉详细的博文(http://blog.csdn.net/ijuliet/article/details/4210858)分析学习。(红色下划线为自己的理解注释)最后贴上自己实现的AC类代码。

——————

(三个方框为标题……无法复制)

今天说说多模式匹配AC算法(Aho and Corasick),感谢追风侠帮忙整理资料,while(1) {Juliet.say("3Q");}。前面学习了BM、Wu-Manber算法,WM由BM派生,不过AC与它们无染,是另外一种匹配思路。

 

1. 初识AC算法

Step1: 将由patterns组成的集合(要同时匹配多个patterns嘛)构成一个有限状态自动机。

Step2: 将要匹配的text作为自动机输入,输出含有哪些patterns及patterns在全文中位置。

 

 

自动机的执行动作由三个部分组成:

(1)       一个goto function

(2)       一个failure function

(3)       一个output function

(解析下作用,goto函数,是用来状态转移的,比如在状态state,输入字符a的下个状态,就可以用goto(state,a)表示。当然,返回fail代表失效。类似Trie树的构建。

然后是failure函数,这个就是当状态转移失效的时候,用来转移状态的。可以理解为状态转移的一种特例。

最后是output函数,就是用来输出某状态下的匹配模式,或者理解output(state)返回state状态下的匹配模式集合,没有匹配模式则集合为空。)

 

我们先通过一个具体实例来了解一下这三个部分,及该自动机的运作方式。先有个大概印象,后面会具体讲解。patterns集合{he, she, his ,hers},我们要在”ushers”中查找并匹配。

goto function 

(1) goto function

 

 

i       1   2   3   4   5   6   7   8   9

f(i)     0   0   0   1   2   0   3   0   3 (发现没?貌似if(i)有相同前缀哦^_^)

(2) failure function

 

 

i           output(i)

2           {he}

5           {she,he}

7           {his}

9           {hers}

(3) output function

 

 

       首先我们从状态0开始,接收匹配字符串的第一个字符u,在goto(简称goto function)中可以看到回到状态0,接着第二个字符s,发现转到状态3,在output中查找一下output(3)为空字符串,说明没有匹配到patterns。继续匹配h,转到状态4,查找output发现仍然没有匹配,继续字符e,状态转到了5,查找output,发现output(5)匹配了两个字符串she和he,并输出在整个字符串中的位置。然后接着匹配r,但发现g(5,r)=fail,这时候我们需要查找failure,发现f(5)=2,所以就转到状态2,并接着匹配r,状态转移到了8,接着匹配s,状态转移到了9,查看output,并输出output(9):hers,记录下匹配位置。至此字符串ushers匹配完毕。

 

具体的匹配算法如下:

算法1. Pattern matching machine

输入:text和M。text是x=a1a2...an,M是模式匹配自动机(包含了goto函数g(),failure函数f(),output函数output())

输出:text中出现的pat以及其位置。

 (匹配,失效的话用失效转移,然后赋值实际状态转移,然后判断是否存在匹配模式)

state←0

for i←1 until n do //吞入text的ai

     while g(state, ai)=fail 

         state←f(state) //直到能走下去,呵呵,至少0那个状态怎么着都能走下去

     state←g(state,ai) //得到下一个状态

     if output(state)≠empty //能输出就输出

         print i;

         print output(state)

 

     AC算法的时间复杂度是O(n),与patterns的个数及长度都没有关系。因为Text中的每个字符都必须输入自动机,所以最好最坏情况下都是O(n),加上预处理时间,那就是O(M+n),M是patterns长度总和。

 

2. 构造三表

OK,下面我们看看如何通过patterns集合构造上面的3个function

这三个function的构造分两个阶段:

(1)       我们决定状态和构造goto function

(2)       我们计算得出failure function

而output function的构造贯穿于这两个阶段中。

 

2.1 goto  ouput填表

(goto函数实现开始)

我们仍然拿实例来一步步构造:patterns集合{he,she,his,hers}

首先我们构造patterns   he

 he构造

然后接着构造she

 she构造

再构造his,由于在构造his的时候状态0接收h已经能到状态1,所以就不用重新建一个状态了,有点像建trie树的过程,共用一段相同的前缀部分

 his构造

最后构造hers

 hers构造

具体构造goto function算法如下:

算法2. Construction of the goto function

输入:patterns集合K={y1,y2,...,yk}

输出:goto function g 和output function output的中间结果

 

/*

We assume output(s) is empty when state s is first created, and g(s,a)=fail if a is

undefined or if g(s,a) has not yet been defined. The procedure enter(y) inserts into

the goto graph a path that spells out y.

*/

 (对每个模式嗲用enter插入trie中,然后设置根(0)的所有失效状态转移都回到自己(0))

newstate←0

fori ← 1until k //对每个模式走一下enter(yi),要插到自动机里来嘛

     enter(yi)

for all a such that g(0,a)=fail

     g(0,a)←0

 

 (先匹配有相同前缀的模式路径,然后增加自己其余路径,最后加入匹配模式)

enter(a1a2...am)

{

     state←0;j←;1

     while g(state,aj)≠fail //能走下去,就尽量延用以前的老路子,走不下去,就走下面的for()拓展新路子

         state←g(state,aj)

         j←j+1

 

     for p←j until m //拓展新路子

         newstate←newstate+1

         g(state,ap)←newstate

         state←newstate

 

     output(state)←{a1a2...am} //此处state为每次构造完一个pat时遇到的那个状态

}

 

2.2  Failure  output填表

Failure function的构造:(这个比较抽象)

(概括为,根0没有失效转移,第一层状态都失效转移到根0上,其余层根据祖先动态计算。用BFS可以实现。)

大家注意状态0不在failure function中,下面开始构造,首先对于所有depth为1的状态s,f(s)=0,然后归纳为所有depth为d的状态的failure值都由depth-1的状态得到。

具体讲,在计算depth为d的所有状态时候,我们会考虑到每一个depth为d-1的状态r

1.       如果对于所有的字符a,g(r,a)=fail,那么什么也不做,我认为这时候r已经是trie树的叶子结点了。

2.       否则的话,如果有g(r,a)=s,那么执行下面三步(不断地调用父亲的失效转移,直至有个最近的状态能匹配a,这里不能找到的话,就回到根0了)

(a)       设置state=f(r) //state记录跟r共前缀的东东

(b)       执行state=f(state)零次或若干次,直到使得g(state,a)!=fail(这个状态一定会有的因为g(0,a)!=fail)//必须找条活路,能走下去的

(c)       设置f(s)=g(state,a),即相当于找到f(s)也是由一个状态匹配a字符转到的状态。

实例分析:

首先我们将depth为1的状态f(1)=f(3)=0,然后考虑depth为2的结点2,6,4

计算f(2)时候,我们设置state=f(1)=0,因为g(0,e)=0,所以f(2)=0;

计算f(6)时候,我们设置state=f(1)=0,因为g(0,i)=0,所以f(6)=0;

计算f(4)时候,我们设置state=f(3)=0,因为g(0,h)=1,所以f(4)=1;

然后考虑depth为3的结点8,7,5

计算f(8)时候,我们设置state=f(2)=0,因为g(0,r)=0,所以f(8)=0;

计算f(7)时候,我们设置state=f(6)=0,因为g(0,s)=3,所以f(7)=3;

计算f(5)时候,我们设置state=f(4)=1,因为g(1,e)=2,所以f(5)=2;

最后考虑depth为4的结点9

计算f(9)时候,我们设置state=f(8)=0,因为g(0,s)=3,所以f(9)=3;

 

具体算法:

算法3. Construction of the failure function

输入:goto function g and output function output from 算法2

输出:failure function f and output function output

 

queue←empty

for each a such that g(0,a)=s≠0//其实这是广搜BFS的过程

     queue←queue∪{s}

     f(s)←0

 

while queue≠empty

     pop();

     for each a such that g(r,a)=s≠fail //r是队列头状态,如果r遇到a能走下去

         queue←queue∪{s} //那就走

         state←f(r) //与r同前缀的state

         while g(state,a)=fail //其实一定能找着不fail的,因为至少g(0,a)不会fail

              state←f(state)

 

         f(s)←g(state,a) //OK,这一步相当于找到了s的同前缀状态,即f(s)

 

         output(s)←output(s)∪output(f(s)) //建议走一下例子中g(4,e)=5的例子,然后ouput(5)∪output(2)={she,he}

 

2.3  output

Output function的构造参见算法2,3

 

3. 算法优化

改进1:观察一下算法3中的failure function还不够优化

 改进1

 

我们可以看到g(4,e)=5,如果现在状态到了4并且当前的字符为t!=e,因为g(4,t)=fail,

所以就根据f(4)=1,跳转到状态1,而之前已经知道t!=e,所以就没必要跳到1,而直接跳到状态f(1)=0。

为了避免不必要的状态迁移,和KMP算法有异曲同工之处。重新定义了一个failure function:f1

 

f1(1)=0,

对于i>1,如果能使状态f(i)转移的所有字符也能使i状态转移,那么f1(i)=f1(f(i)),

否则f1(i)=f(i)。

 

改进2:由于goto function中并不是每个状态对应任何一个字符都有状态迁移的,当迁移为fail的时候,我们就要查failure function,然后换个状态迁移。现在我们根据goto function和failure function来构造一个确定的有限自动机next move function,该自动机的每个状态遇到每个字符都可以进行状态迁移,这样就省略了failure function。

 

构造next move function的算法如下:

算法4:Construction of a deterministic finite automaton

输入:goto functioni g and failure function f

输出:next move function delta

 

queue←empty

for each symbol a

     delta(0,a)←g(0,a)

     if g(0,a)≠0

         queue←queue∪g(0,a)

 

while queue≠empty

     pop()

     for each symbol a

         if g(r,a)=s≠fail

              queue←queue∪{s}

              delta(r,a)←s

else delta(r,a)←delta(f(r),a)

 

Next function delta的计算如下:

 改进2

其中’.’表示除了该状态能识别字符的其他字符。

 

改进2有利有弊:好处是能减少状态转移的次数;坏处是由于状态与状态之间的迁移多了,导致存储的空间比较大。


——————

自己实现的代码如下:(用来辅助理解AC算法,就用了STL)

/*
Author:BetaBin
Date:2012/04/15
Function:Aho-Corasick algorithm
*/

#include <iostream>
#include <set>
#include <cstring>
#include <string>
#include <queue>

using namespace std;

#define CHAR_SIZE 256

//AC状态节点结构
struct acNode
{
	acNode* nextNode[CHAR_SIZE];	//状态转移
	acNode* failureNode;			//失效转移
	set<string> patternSet;			//在此状态匹配的模式集合
	set<char> nextSet;				//辅助变量,用于存放有效转移输入字符

	//初始化全部转移状态设置为失败
	acNode()
	{
		memset(nextNode, NULL, sizeof(nextNode));
		failureNode = NULL;
	}
};


//AC多模式字符串匹配类
class acMatcher
{
public:
	acMatcher();
	~acMatcher();

	void buildTrie();					//读入模式,构建Trie
	void setTransform();				//设置失效转移
	void matche(string text);			//开始AC匹配

	void destroyTrie(acNode* trieRoot);	//销毁以trieRoot为根的Trie

private:
	acNode* root;						//Trie根节点

	void addPattern(string pattern);	//往Trie中添加模式
};

acMatcher::acMatcher()
{
	//根节点的所有失效转移到本身
	root = new acNode();
	root->failureNode = root;
	for (int i = 0; i < CHAR_SIZE; i++)
	{
		root->nextNode[i] = root;
	}
}

acMatcher::~acMatcher()
{
	if (NULL != root)
	{
		destroyTrie(root);
	}
}

void acMatcher::destroyTrie(acNode* trieRoot)
{
	for (int i = 0; i < CHAR_SIZE; i++)
	{
		if (NULL != trieRoot->nextNode[i])
		{
			destroyTrie(trieRoot->nextNode[i]);
		}
	}

	trieRoot->patternSet.clear();
	trieRoot->nextSet.clear();
	delete trieRoot;
}

void acMatcher::buildTrie()
{
	int patterNum;
	string inputPattern;

	cout << "Please input the pattern number: ";
	cin >> patterNum;

	while (patterNum--)
	{
		cin >> inputPattern;
		addPattern(inputPattern);
	}
}

void acMatcher::addPattern(string pattern)
{
	int scanner = 0;
	int patternLen = pattern.size();
	acNode* curNode = root;

	//先匹配已有相同前缀的模式路径
	while (scanner < patternLen && root != curNode->nextNode[pattern[scanner]] && NULL != curNode->nextNode[pattern[scanner]])
	{
		curNode = curNode->nextNode[pattern[scanner]];
		scanner++;
	}

	//再增加自己的模式路径
	while (scanner < patternLen)
	{
		curNode->nextNode[pattern[scanner]] = new acNode();
		curNode->nextSet.insert(pattern[scanner]);
		curNode = curNode->nextNode[pattern[scanner]];
		scanner++;
	}

	curNode->patternSet.insert(pattern);
}

//BFS似的遍历
void acMatcher::setTransform()
{
	queue<acNode*> bfsQueue;
	acNode* curNode;
	acNode* failNode;
	set<char>::iterator charScanner;
	set<string>::iterator stringScanner;

	//第一层状态节点失效转移都转移到根节点上
	for (charScanner = root->nextSet.begin(); charScanner != root->nextSet.end(); charScanner++)
	{
		bfsQueue.push(root->nextNode[*charScanner]);
		root->nextNode[*charScanner]->failureNode = root;
	}

	//BFS遍历其它状态节点
	while (!bfsQueue.empty())
	{
		curNode = bfsQueue.front();
		bfsQueue.pop();

		//对每个状态的所有可能的转移状态设置其失效转移状态
		//寻找路径上加chaScanner字符能够匹配的状态
		for (charScanner = curNode->nextSet.begin(); charScanner != curNode->nextSet.end(); charScanner++)
		{
			bfsQueue.push(curNode->nextNode[*charScanner]);
			failNode = curNode->failureNode;

			while (NULL == failNode->nextNode[*charScanner])
			{
				failNode = failNode->failureNode;
			}

			curNode->nextNode[*charScanner]->failureNode = failNode->nextNode[*charScanner];
			for (stringScanner = failNode->nextNode[*charScanner]->patternSet.begin(); stringScanner != failNode->nextNode[*charScanner]->patternSet.end(); stringScanner++)
			{
				curNode->nextNode[*charScanner]->patternSet.insert(*stringScanner);
			}
		}
	}
}

void acMatcher::matche(string text)
{
	int textLen = text.size();
	acNode* curNode = root;
	set<string>::iterator stringScanner;

	//遍历字符串
	for (int i = 0; i < textLen; i++)
	{
		while (NULL == curNode->nextNode[text[i]])
		{
			curNode = curNode->failureNode;
		}

		curNode = curNode->nextNode[text[i]];

		//判断是否为匹配状态
		if (!curNode->patternSet.empty())
		{
			cout << "No." << i + 1 << ":" << endl;
			for (stringScanner = curNode->patternSet.begin(); stringScanner != curNode->patternSet.end(); stringScanner++)
			{
				cout << "t" << *stringScanner << endl;
			}
		}
	}
}

int main()
{
	acMatcher acDfa;
	string text;

	acDfa.buildTrie();
	acDfa.setTransform();

	cin >> text;
	acDfa.matche(text);

	return 0;
}


版权声明:本文来源CSDN,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/BetaBin/article/details/7423945
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。
  • 发表于 2020-06-30 09:58
  • 阅读 ( 184 )
  • 分类:算法

0 条评论

请先 登录 后评论

官方社群