欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

多模式匹配算法---AC自动机

程序员文章站 2022-03-12 21:51:50
...

主要是为了记录平时的学习,网上类似的例子也很多。有错误的地方,烦请大家指出,多谢。

一.简单介绍

1.KMP算法和AC自动机都是用于字符串的匹配,KMP算法主要是用于单一模式串的匹配,对于多模式串的匹配目前实际应用中较多的是AC自动机算法,多模式的匹配类似于,求解多个模式串,p1,p2,p3……在一个连续的文本中T1,T2,T3……Tm中的出现的次数和出现的位置。

2.一般的求解步骤是分为以下几步:

(1).待匹配的模式串生成字典树。

(2).给字典树找失败路径指针。

(3).根据AC自动机 搜索字典树,找匹配的字符串。

二.下面结合一个具体的例子来说明下整个过程。

目标:求解字符串{"say","she","her","he"} 在文本字符串"bshasaykheyitj"中出现的位置

1.首先是建立字典树,需要注意的一点是,字典树中某一个节点是待匹配字符串的最后一个字符时,需要做标记,为了搜索字典树匹配时 辨别是否是一个完整的字符串。 

多模式匹配算法---AC自动机

图片中的 画有两个横线标记的表示 该字符是可接受状态,标记一个字符串最后一个字符(如"say"字符串中y 是该字符串的最后一个字符),以便于后面方便的统计是否搜索完一个完整的字符串。

2.为字典树添加失败路径。

添加失败路径的具体的做法:假设当前节点是m,现在需要寻找m的失败路径,沿着m节点的父亲节点的失败指针走,走到下一个节点,如果该节点中的孩子节点也有m字符,那么我们就把当前节点的失败指针指向 现在此时找到的m节点。如果一直递归找到root节点 ,那么当前节点的失败指针直接指向root节点。PS:注意的一点是,寻找失败指针是按照 宽度优先遍历的。另外,root节点的孩子节点的失败指针是指向root节点的。看到这里如果还是不怎么理解,没关系,下面具体的举例子来说明。请看下图。

多模式匹配算法---AC自动机

现在让我们来自己按照建立失败指针的步骤来走一遍整个过程:

(1).字典树已经建立好了,按照宽度优先遍历来构建失败指针,第一层是root节点,第二层是节点s和节点h.第三层节点是a和h和e.

第四层节点是y和e和r.

(2).第二层的节点是root的孩子节点,失败指针直接指向root.第三层的节点a的父亲节点是s,而s的失败指针指向root节点,此时root节点中的孩子节点中没有a,所以此时a的失败指针指向root节点。h节点的父亲是s节点,s的失败指针指向root节点,root的孩子节点中有h ,所以此时h的失败指针 指向的是root 的孩子节点h.

(3).按照上述步骤,依次建立各个节点的失败指针。

3.通过上图的字典树,在文本串中搜索。

       从root节点开始,每次根据读入的字符沿着自动机向下移动。当读入的字符在自动机中不存在时,递归走失败路径。如果此时走失败路径到了root节点,则跳过该字符,处理下一个字符。读取完所有的输入文本后,最后递归的走失败路径,直到到达root节点,这样可以检测出所有的模式串。遇到可接受状态的字符时,表示遍历了一个完整的字符。


三.下面是一个简单的例子:

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


using namespace std;
char input[4][30] ={"say","she","her","it"};//输入待匹配的字符串

typedef struct node
{
	node* next[26]; //节点的下一个节点
	node* parent;  //父亲节点
	node* fail;    //失败指针
	char inputData;
	bool IssubStr; //是否是一个完整的字符串
	int subIndex;  //位置
}* Tree,TreeNode;


Tree getNewNode()   //新建一个节点
{
	TreeNode*  tnode= (TreeNode*)malloc(sizeof(TreeNode));
	tnode ->parent = NULL;
	tnode ->fail = NULL;
	tnode ->IssubStr = false;
	tnode ->subIndex =-1;
	for(int i =0;i< 26;i++)
	{
		tnode->next[i] = NULL;
	}
	return tnode;
}

/*****建立字典树***/

Tree buildTree()
{
	Tree root = getNewNode(); //新建立一个节点
	Tree tmp1 = NULL;
	Tree tmp2 = NULL;
	for(int i =0;i<4;i++)
	{
		tmp1 = root;
		for(int j =0;j< strlen(input[i]);j++)  //每一个待匹配的模式串
		{
			if(tmp1->next[input[i][j] - 'a'] != NULL)
			{
				tmp1 = tmp1->next[input[i][j] - 'a'];
			}
			else  //表示没有新的分支,需要新建立分支 
			{
				tmp2 = getNewNode();
				tmp2 ->inputData = input[i][j];
				tmp2 ->parent = tmp1;
				tmp1 ->next[input[i][j]-'a'] = tmp2; //tmp1指针的next指针域存储tmp2指针
				
				tmp1 = tmp2; //向下移动一个指针
			}
		}
		tmp1->IssubStr = true ;// 标志是一个完整的字符串
		tmp1->subIndex = i;  //表示是第几个模式串
	}
	return root;
}

/***宽度遍历字典树**入队列*/

void toNodeQueue(Tree node,queue<Tree>& myqueue)
{

	for(int i=0;i<26;i++)
	{
		if(node->next[i] != NULL) //node 节点的所有的孩子节点插入队列中
		{
			myqueue.push(node->next[i]);
		}
	}

}


int buildFailPath(Tree root)
{
	queue<Tree> myqueue;
	root->fail = root;
	
	for(int i =0;i< 26;i++)
	{
		if(root->next[i] != NULL)
		{
			root->next[i] ->fail = root; //root节点的孩子节点失败指针指向root
			toNodeQueue(root->next[i],myqueue);
		}
	}
	
	Tree tmp1=NULL,parent = NULL;
	char inputData = 0;
	
	while(!myqueue.empty()) //队列不为空的时候
	{
		
		tmp1 = myqueue.front(); //当前节点
		myqueue.pop();
		toNodeQueue(tmp1,myqueue);
		parent = tmp1->parent; //当前节点的父亲节点
		
		inputData = tmp1->inputData;
		while(true)  //递归的寻找失败指针
		{
			if(parent->fail->next[inputData - 'a'] != NULL) //该节点父亲节点的失败指针 是否有与当前节点值一样
			{
				tmp1->fail = parent->fail->next[inputData - 'a'];
				break;
			}
			else
			{
				if(parent->fail == root)
				{
					tmp1->fail = root;
					break;
				}
				else
				{
					parent = parent->fail->parent;
				}
			}
		}
		
	}
	
	return 0;
}

int SearchTree(Tree root,char* str,int len)
{
	TreeNode* tmp = root;
	int i = 0;
	while(i < len)
	{
		int pos = str[i] - 'a';
		if(tmp->next[pos] != NULL)
		{
			tmp = tmp->next[pos];
			if(tmp->IssubStr) //表明一个完整的字符串
			{
				cout << " " << i-strlen(input[tmp->subIndex])+1 << "\t" << tmp->subIndex << "\t"<< input[tmp->subIndex]<<endl; 
			}
		 i++;  //下一个字符	
		}
		else  //下个字符串不在分支中,则跳转到失败指针
		{
			if(tmp == root) //递归找失败指针,直到root 指针 会跳过,继续遍历下一个字符
			{
				i++;
			}
			else
			{
				tmp =tmp->fail; //跳转到失败指针
				if(tmp->IssubStr) //表示一个完整的字符串
				{
					cout << " " << i-strlen(input[tmp->subIndex])+1 << "\t" << tmp->subIndex << "\t"<< input[tmp->subIndex]<<endl;
				}	
			}
		}
	}
	
	while(tmp != root)   //递归走失败路径到达root节点
	{
		tmp = tmp->fail;
		if(tmp->IssubStr) //表示一个完整的字符串
		{
			cout << " " << i-strlen(input[tmp->subIndex])+1 << "\t" << tmp->subIndex << "\t"<< input[tmp->subIndex]<<endl;
		}	
		
	}
	
	return 0;
}

void Destory(Tree node)
{
	if(node == NULL)
		return ;
	queue<Tree> myqueue;
	myqueue.push(node);
	Tree tmp = NULL;
	while(!myqueue.empty())
	{
		tmp = myqueue.front();
		myqueue.pop();
		for(int i =0;i<26;i++)
		{
			if(tmp->next[i] != NULL) //不为空,表示孩子节点
			{
				myqueue.push(tmp->next[i]);
			}
			
		}
		free(tmp);
	}
}

int main()
{
	
	char a[] = "bshasaykheyitj";
	
	Tree root = buildTree();
	buildFailPath(root);
	cout<<"匹配结果如下:"<<endl<<"位置\t"<<"编号\t"<<"模式"<<endl;
	SearchTree(root,a,strlen(a));
	Destory(root);
	return 0;
}

结果如下:

多模式匹配算法---AC自动机