AC(Aho—Corasiek) 多模式匹配算法

前端之家收集整理的这篇文章主要介绍了AC(Aho—Corasiek) 多模式匹配算法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

简介:

AC多模式匹配算法产生于1975年的贝尔实验室,最早使用于图书馆的书目查询程序中。该算法以有限状态自动机(FSA),以及KMP前缀算法 为基础.(有说法: ac自动机是KMP的多串形式,是一个有限自动机)

@H_502_9@

AC定义:

AC有限自动机 M 是1个6元组:M =(Q,∑,g,f,qo,F)其中:

1、Q是有限状态集(模式树上的所有节点).

2、∑是有限的输入字符表(模式树所有边上的字符).

3、g是转移函数.

4、f是失效函数,不匹配时自动机的状态转移.

5、qo∈Q是初态(根节点);

6、F量Q是终态集(以模式为标签的节点集).

@H_502_9@

AC有限状态自动机实现:

首先假设模式集合{he,she his,hers},输入字符串"ushers":

@H_502_9@

AC自动机算法主要建立三个函数,转向函数goto,失效函数failure和输出函数output(output 构造间杂在goto 构造以及failure构造中);

@H_502_9@

1、AC有限状态自动机M 操作循环框架:

a> 如果g(s,a) = s',则自动机M 继续调用goto函数,以新状态s',以及新字符x为输入;如果状态s',匹配了某个模式,则输出;

b> 如果f(s,a) = failure,则自动机M 调用failure状态转移f(s) = s',并以状态s',字符a 调用步骤1;

@H_502_9@

构造M伪代码:

@H_502_9@

2、构造goto函数输出函数output:

goto函数: 是一个状态在接受一个字符后转向另一个状态或者失败的函数(对应于FSA里的转移函数);

定义如下:

g(S,a) 其中S ∈ Q,a ∈ Σ :从当前状态S开始,沿着边上标签为a的路径所到的状态。假如状态节点(U,V)边上的标签为a,那么g(U,a)=V;如果根节点上出来的边上的标签没有a,则g(0,a)=O(失败),即如果没有匹配的字符出现,自动机停留在初态;如果不是根节点,且该节点出来的标签没有字符a,则g(U,称为失败;

@H_502_9@

下图(a)是用goto函数以{he,hers}模式集构造的字符串模式匹配机:

状态0是初始状态,在状态0和状态1间的有向边标有字符'h',表示g(0,a) = 1;缺失的有向边表示失败,当任意字符σ != e或i,有g(1,σ) = failure;

注意: 所有字符有 g(0,σ) != failure,状态0的这个属性确保 M 会处理输入的任意字符;任意字符σ不在以状态0开始有向边的字符,有g(0,σ) = 0;同时说明状态0的失效函数(failure) 没有意义,不用计算;

@H_502_9@

构造goto伪代码:

@H_502_9@

3、构造失效函数failure及输出函数output;

失效函数: 指的也是状态和状态之间一种转向关系,在goto失败(failure)的情况下使用的转换关系. 基本原理是KMP 算法的前缀函数

下图(b)是各状态的失效函数值:

下图(c)是各状态i最终的output值:

@H_502_9@

首先,我们定义状态转移图(a)中状态s的深度为从状态0到状态s的最短路径。例如图(a)起始状态的深度是0,状态1和3的深度是1,状态2,4,和6的深度是2,等等。

计算思路:先计算所有深度是1的状态的失效函数值,然后计算所有深度为2的状态,以此类推,直到所有状态(除了状态0,因为它的失效函数没有定义)的失效函数值都被计算出。

计算方法用于计算某个状态失效函数值的算法在概念上是非常简单的。首先,令所有深度为1的状态s的函数值为f(s) = 0。假设所有深度小于d的状态的f值都已经被算出了,那么深度为d的状态的失效函数值将根据深度小于d的状态的失效函数值来计算。

具体步骤:

为了计算深度为d 状态的失效函数值,假设深度为d-1的状态r,执行以下步骤:

Step1: 如果对所有字符a,有g(r,a) = fail,那么什么都不做;(好像是废话,这如果成立,说明状态r节点下面没有节点了,根本不需要计算)

Step2: 否则,对每个使g(r,a) = s成立的字符a,执行以下操作:

a) 记state = f(r);

b) 执行零次或者多次令state = f(state),直到出现一个state使得g(state,a) != fail;(注意到,因为对任意字符a,g(0,a) != fail,所以这种状态一定能够找到);

c) 记f(s) = g(state,a);

注意: 这里有点拗口,不好理解,一句话来说: 就是看当前状态节点前一个状态节点(父节点)的failure节点是否有当前字符的外向变,如果有,则当前状态failure状态就是对应外向变对应的节点;如果没有,则根据对应failure状态的failure状态;

@H_502_9@

举个例子:求图(a)中状态4 的failure 状态,已知其前一个(父节点)的f(1)= 0,且状态0(根节点)有字符'h'的外向边,该外向边对应状态1,则有f(4) = 1;类似前缀规则:求已经匹配字串"sh" 最大后缀,同时是某个模式串的前缀;

@H_502_9@

failure 函数代码:

@H_502_9@

4最后是遍历搜索:

状态机搜索过程中会有一种特殊情况:如果模式集中某个模式是另一个模式的子串,为了防止这种情况下漏掉子串模式,需要在这种子串的终态添加到长模式中;代码实现中就是某个状态的failure状态是某个终态,则当前状态也是终态,需要输出failure状态匹配的模式;

@H_502_9@

具体实现代码:

#include<iostream>
#include<string.h>
#include<malloc.h>
#include<queue>
usingnamespacestd;


/*reallocationstepforAC_NODE_t.outgoingarray*/
#defineREALLOC_CHUNK_OUTGOING2

structac_edge;

typedefstructnode{
	unsignedintid;		/*NodeID:justfordebuggingpurpose*/
	unsignedshortdepth;	/*depth:distancebetweenthisnodeandtheroot*/
	
	structnode*parent;		/*parentnode,forcomputefailurefunction*/
	structnode*failure_node;	/*Thefailurenodeofthisnode*/

	shortintfinal;		/*0:no;1:yes,itisafinalnode*/
	intpatternNo;		/*Acceptpatternindex:justfordebuggingpurpose*/

	/*OutgoingEdges*/
	structac_edge*outgoing_edge;/*Arrayofoutgoingcharacteredges*/
	unsignedshortoutgoing_num;	/*Numberofoutgoingcharacteredges*/
	unsignedshortoutgoing_max;	/*Maxcapacityofallocatedmemoryforoutgoingcharacteredges*/
}AC_NODE_t;

/*TheOugoingEdgeoftheNode*/
structac_edge
{
charalpha;/*Edgealpha*/
AC_NODE_t*next;	/*Targetoftheedge*/
};


staticvoidnode_assign_id(AC_NODE_t*thiz);
staticAC_NODE_t*node_find_next(AC_NODE_t*pAc_node,charch);


/******************************************************************************
*Createnode
******************************************************************************/
AC_NODE_t*node_create()
{
	AC_NODE_t*pNode=(AC_NODE_t*)malloc(sizeof(AC_NODE_t));

	memset(pNode,sizeof(AC_NODE_t));

	pNode->failure_node=NULL;
	pNode->parent=NULL;
	pNode->final=0;

	/*initoutgoingcharacteredges*/
	pNode->outgoing_max=REALLOC_CHUNK_OUTGOING;
	pNode->outgoing_edge=(structac_edge*)malloc(pNode->outgoing_max*sizeof(structac_edge));

	node_assign_id(pNode);

	returnpNode;
}

/******************************************************************************
*assignauniqueIDtothenode(usedfordebuggingpurpose).
******************************************************************************/
staticvoidnode_assign_id(AC_NODE_t*thiz)
{
	staticintunique_id=0;
	thiz->id=unique_id++;
}

/******************************************************************************
*Establishannewedgebetweentwonodes
******************************************************************************/
voidnode_add_outgoing(AC_NODE_t*thiz,AC_NODE_t*next,charalpha)
{
	if(thiz->outgoing_num>=thiz->outgoing_max)
	{
		thiz->outgoing_max+=REALLOC_CHUNK_OUTGOING;
		thiz->outgoing_edge=(structac_edge*)realloc(thiz->outgoing_edge,thiz->outgoing_max*sizeof(structac_edge));
	}

	thiz->outgoing_edge[thiz->outgoing_num].alpha=alpha;
	thiz->outgoing_edge[thiz->outgoing_num++].next=next;
}

/******************************************************************************
*Createanextnodewiththegivenalpha.
******************************************************************************/
AC_NODE_t*node_create_next(AC_NODE_t*pCur_node,charalpha)
{
	AC_NODE_t*pNext_node=NULL;
	pNext_node=node_find_next(pCur_node,alpha);

	if(pNext_node)
	{
		/*The(labeledalpha)edgealreadyexists*/
		returnNULL;
	}

	/*Otherwiseaddnewedge(node)*/
	pNext_node=node_create();
	node_add_outgoing(pCur_node,pNext_node,alpha);

	returnpNext_node;
}

/******************************************************************************
*FindoutthenextnodeforagivenAlphatomove.thisfunctionisusedin
*thepre-processingstageinwhichedgearrayisnotsorted.soituseslinearsearch.
******************************************************************************/
staticAC_NODE_t*node_find_next(AC_NODE_t*pAc_node,charch)
{
	inti=0;

	if(NULL==pAc_node)
	{
		returnNULL;
	}

	for(i=0;i<pAc_node->outgoing_num;i++)
	{
		if(pAc_node->outgoing_edge[i].alpha==ch)
			return(pAc_node->outgoing_edge[i].next);
	}

	returnNULL;
}

/******************************************************************************
*addparentnode'sallleafnode(outgoingnode)intoqueue
******************************************************************************/
intqueue_add_leaf_node(AC_NODE_t*parent,queue<AC_NODE_t*>&myqueue)
{
	inti;

	for(i=0;i<parent->outgoing_num;i++)
	{
		myqueue.push(parent->outgoing_edge[i].next);
	}

	return0;
}

/******************************************************************************
*Initializeautomata;allocatememoriesandaddpatternsintoautomata
******************************************************************************/
AC_NODE_t*ac_automata_create(charpattern[][255],intpatterns_num)
{
	intiPattern_index,iChar_index;
	AC_NODE_t*root=node_create();
	AC_NODE_t*pCur_node=NULL,*pNext_node=NULL;
	charalpha;

	for(iPattern_index=0;iPattern_index<patterns_num;iPattern_index++)
	{
		pCur_node=root;
		for(iChar_index=0;iChar_index<strlen(pattern[iPattern_index]);iChar_index++)///对每个模式进行处理
		{
			alpha=pattern[iPattern_index][iChar_index];
			pNext_node=node_find_next(pCur_node,alpha);
			if(NULL!=pNext_node)
			{
				pCur_node=pNext_node;
			}
			else
			{
				pNext_node=node_create_next(pCur_node,alpha);
				if(NULL!=pNext_node)
				{
					pNext_node->parent=pCur_node;
					pNext_node->depth=pCur_node->depth+1;

					pCur_node=pNext_node;
				}
			}
		}

		pCur_node->final=1;
		pCur_node->patternNo=iPattern_index;
	}

	returnroot;
}

/******************************************************************************
*findfailurenodeforallnode,actuallyfailurefunctionmapsastateintoanewstate.
*thefailurefunctionisconsultedwheneverthegotofunctionreportsfail;
*specificialycomputethefailuenode,weuseit'sparentnode'sfailurenode
******************************************************************************/
intac_automata_setfailure(AC_NODE_t*root)
{
	inti=0;
	queue<AC_NODE_t*>myqueue;

	charedge_ch='\0';
	AC_NODE_t*pCur_node=NULL,*parent=NULL,*pNext_Node=NULL;

	for(i=0;i<root->outgoing_num;i++)	//f(s)=0forallstatessofdepth1
	{
		root->outgoing_edge[i].next->failure_node=root;
	}

	queue_add_leaf_node(root,myqueue);

	while(!myqueue.empty())
	{
		parent=myqueue.front();
		myqueue.pop();
		queue_add_leaf_node(parent,myqueue);

		for(i=0;i<parent->outgoing_num;i++)
		{
			edge_ch=parent->outgoing_edge[i].alpha;

			pCur_node=parent->outgoing_edge[i].next;

			pNext_Node=node_find_next(parent->failure_node,edge_ch);
			if(NULL==pNext_Node)
			{
				if(parent->failure_node==root)
				{
					pCur_node->failure_node=root;
				}
				else
				{
					parent=parent->failure_node->parent;
				}
			}
			else
			{
				pCur_node->failure_node=pNext_Node;
			}
		}
	}

	return0;
}

/******************************************************************************
*Searchintheinputtextusingthegivenautomata.
******************************************************************************/
intac_automata_search(AC_NODE_t*root,char*text,inttxt_len,charpattern[][255])
{
	AC_NODE_t*pCur_node=root;
	AC_NODE_t*pNext_node=NULL;
	intposition=0;

	while(position<txt_len)
	{
		pNext_node=node_find_next(pCur_node,text[position]);
		if(NULL==pNext_node)
		{
			if(pCur_node==root)
			{
				position++;
			}
			else
			{
				pCur_node=pCur_node->failure_node;
			}
		}
		else
		{
			pCur_node=pNext_node;
			position++;
		}

		if(pCur_node->final==1)///somepatternmatched
		{
			cout<<position-strlen(pattern[pCur_node->patternNo])<<'\t'<<'\t'<<pCur_node->patternNo<<'\t'<<'\t'<<pattern[pCur_node->patternNo]<<endl;
		}
	}

	return0;
}

/******************************************************************************
*Printstheautomatatooutputinhumanreadableform.
******************************************************************************/
voidac_automata_display(AC_NODE_t*root)
{
	unsignedinti;
	AC_NODE_t*pCur_node=root;
	structac_edge*pEdge=NULL;

	if(root==NULL)
	{
		return;
	}

	printf("---------------------------------\n");

	queue<AC_NODE_t*>myqueue;
	myqueue.push(pCur_node);

	while(!myqueue.empty())
	{
		pCur_node=myqueue.front();
		myqueue.pop();

		printf("NODE(%3d)/----fail---->NODE(%3d)\n",pCur_node->id,(pCur_node->failure_node)?pCur_node->failure_node->id:0);

		for(i=0;i<pCur_node->outgoing_num;i++)
		{
			myqueue.push(pCur_node->outgoing_edge[i].next);

			pEdge=&pCur_node->outgoing_edge[i];
			printf("|----(");
			if(isgraph(pEdge->alpha))
				printf("%c)---",pEdge->alpha);
			else
				printf("0x%x)",pEdge->alpha);
			printf("-->NODE(%3d)\n",pEdge->next->id);
		}
		printf("---------------------------------\n");
	}
}

/******************************************************************************
*Releaseallallocatedmemoriestotheautomata
******************************************************************************/
intac_automata_release(AC_NODE_t*root)
{
	if(root==NULL)
	{
		return0;
	}

	queue<AC_NODE_t*>myqueue;
	AC_NODE_t*pCur_node=NULL;

	myqueue.push(root);
	root=NULL;

	while(!myqueue.empty())
	{
		pCur_node=myqueue.front();
		myqueue.pop();

		for(inti=0;i<pCur_node->outgoing_num;i++)
		{
			myqueue.push(pCur_node->outgoing_edge[i].next);
		}
		free(pCur_node);
	}

	return0;
}

intmain()
{
	unsignedinti=0;
	charhaystack[]="ushers";
	charneedle[4][255]={"he","she","his","hers"};

	/*1.createacfinitestateautomatamatchmachine,computegotoandoutputfunc*/

	AC_NODE_t*root=ac_automata_create(needle,sizeof(needle)/sizeof(needle[0]));

	/*2.computefailurefunction*/

	ac_automata_setfailure(root);

	/*3.Displayautomata(ifyouareinterested)*/

	ac_automata_display(root);

	cout<<endl<<"haystack:"<<haystack<<endl;
	cout<<"needles:";
	for(i=0;i<sizeof(needle)/sizeof(needle[0]);i++)
	{
		cout<<needle[i]<<"";
	}
	cout<<endl<<endl;
	cout<<"matchresult:"<<endl<<"position\t"<<"node_id\t\t"<<"pattern"<<endl;

	/*3.seachingmultipatternsuseautomata*/

	ac_automata_search(root,haystack,strlen(haystack),needle);

	/*4.Releasetheautomata*/

	ac_automata_release(root);

	return0;
}

@H_502_9@

后记:

根据不同的AC_NODE结构设计,实现会有些不同,但原理一样;

可以改进的地方:

1、可以把同深度节点排序,后面查找某状态的指定字符外向边状态,可以使用二分查找,加快速度;

2、这里的AC_NODE 里面每个节点只对应一个匹配模式(patternNo),理论上是有多个的匹配模式的,有待完善;

3、已知g(4,e) = 5; 假设M 当前状态为4,且下一个字符不是'e',这时候M 会调用f(4)=1,其实这时候我们已经不需要去查找状态1以'e'为外向边的状态了,因为下一个字符确定不是'e';如果没有"his"模式,我们可以直接从状态1跳到状态0;而现在代码是会去做这个多余查找动作的。这个可以用确定有限自动机来避免,下篇文章我会详细和大家讨论下.

有任何问题,还请不吝赐教~

@H_502_9@

references:

<1>、Efficient String Matching: An Aid to Bibliographic Search.pdf(june 1975)

<2>、http://blog.csdn.net/sunnianzhong/article/details/8832496

<3>、http://blog.csdn.net/sealyao/article/details/4560427

<4>、http://www.it165.net/pro/html/201311/7860.html

<5>、http://sourceforge.net/projects/multifast/

<6>、多模式匹配算法的研究.pdf

<7>、模式匹配算法在网络入侵系统中的应用研究.pdf

猜你在找的正则表达式相关文章