DFA有限状态自动机.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,字符串模式匹配中,DFA,的应用,本讲义部分改编自北大信息科学技术学院,08,级贺一骏讲义,北京大学信息学院 郭炜,GWPLPKU.EDU.CN,POJ1204 Word Puzzles,题目大意,:,给出一个,N*L,的字符矩阵，再给出,M,个字符串，问这,M,个字符串在这个字符矩阵中出现的位置。,MARGARITA,ALEMA,BARBECUE,数据范围：,N,L=1000,M=1000,时间限制：,5s,将问题抽象,将,N*L,的字符矩阵中的每行、每列、每斜行，单独抽出得到了,N+L+2*(N+L-1),个字符串，加上它们的各自的逆序，则得到的字符串的数目是：,2*(N+L+2*(N+L-1)=6N+6L-2,然后，现在的问题是判断之后给出的,M,个字符串出现在以上的那些字符串的什么位置。这里我们称前面抽象出来的,6N+6L-2,个串为原串，之后给出的,M,个串为模式串。,思考,强行匹配？时间复杂度：,O(NLMlen)(len,是模式串的平均长度）,KMP,？时间复杂度：,O(NLM),O(10,12,),太不靠谱了！,O(10,9,),还是不能忍！,确定性有限状态自动机,DFA(deterministic finite automata),DFA,使用一个五元组,(Q,，,q0,，,A,，,),来描述，这里,Q,为状态集；,q0,为起始状态；,A,为终态集；为字母表，,为转移函数。用一个图来描述一个自动机：,图中圆圈代表状态，箭头代表转移，例如从状态,“,1,”,有一条字符,0,的边指向状态,“,10,”，就是说在状态“,1,”,如果碰到输入是,0,那么就转移到状态“,10,”,。状态,empty,之前有一个,start,标记，我们称,empty,状态为初态；状态“,10,”多加了一个圆圈，我们称他为终态。自动机的初态只有一个而终态可以由若干个。,这是一个字符集为,01,的,DFA,S=“001110”,可以匹配它,确定性有限状态自动机,DFA,是一个图结构的数据结构，每一个节点都有字符集字符数条有向边，并且之所以称之为确定性的，是由于任何一个节点，都不会存在标有相同字符的有向边指向不同的节点。为了更好的理解，我们再给出一个复杂一点的例子，终态为,nano,的自动机如下图所示，能够判断输入串里是否包含“,nano,”,为了解决多串匹配问题，我们下面将介绍一种,DFA,，他是树结构的模型（一般图模型的,DFA,在应用中并不是很多）。,单词前缀树,(trie),这个树有一个性质，那就是,m,个模式串中的前缀所组成的集合,A,与根节点到每一个树中的节点的路径上的字符组成的字符串,S,所组成的集合,B,，是一个满射的关系,即树中任一节点，都对应于某个模式串的前缀。,单词前缀树,(trie),将串,s,插入到,trie,的代码描述如下：,void build(string s),trienode*p=root;,for(int i=0;ichildsi=NULL),new p-childsi;/,初始化新的节点,p=p-childsi;,可以看出将,n,个模式串插入到一棵单词前缀树的时间复杂度为,O(len(i),，其中,len(i),为第,i,个模式串的长度。,Trie,树用途例子：如何求字符串的所有,不同,子串,向大家介绍一个时间复杂度为,O(N,2,),的算法,.,假设当前的字符串为,S,，用,S,的所有后缀作为,len(S),个模式串，插入到一棵单词前缀树中。,单词前缀树中每个节点对应的字符串就是就,S,的一个子串，,S,的子串也一定会对应于前缀树上的某个节点。并且对于前缀树上的任意两个节点，其所对应的字符串肯定是不相同的。因此,S,的不同子串的个数,=trie,中节点的个数,单词前缀树,(trie),DFA,可以由,trie,树为基础构造出来，,对于插入的每个模式串，其插入过程中使用的最后一个节点都作为,DFA,的一个终态节点。,前缀指针,仿照,KMP,算法的,Next,数组，我们也对树上的每一个节点建立一个前缀指针。这个前缀指针的定义和,KMP,算法中的,next,数组相类似，从根节点沿边到节点,p,我们可以得到一个字符串,S,，节点,p,的前缀指针定义为：指向树中出现过的,S,的最长的后缀，换句话说就是在前缀集中出现的最长的,S,的后缀。,如何高效的构造前缀指针,如果采用枚举法求前缀指针，那复杂度可想而知为,O(n,2,),。我们利用当前节点的父节点所求出的前缀指针，来求当前节点的前缀指针，就可以将复杂度降为,O(n),。,步骤为：根据深度一一求出每一个节点的前缀指针。对于当前节点，设他的父节点与他的边上的字符为,Ch,，如果他的父节点的前缀指针所指向的节点的儿子中，有通过,Ch,字符指向的儿子，那么当前节点的前缀指针指向该儿子节点，否则通过当前节点的父节点的前缀指针所指向点的前缀指针，继续向上查找，直到到达根节点为止。,如何高效的构造前缀指针,1,2,3,6,4,5,7,8,A,A,A,B,B,B,B,ROOT1,号节点的前缀指针指向,0,号节点,接下来按照,BFS,顺序构造每个节点的前缀指针,定义虚拟节点,0,号节点，,0,号节点的所有连出的字边都连向,ROOT1,号节点,0,A,、,B,2,号节点：,父亲是,1,号节点，连接字符为,A,，查找父亲的前缀指针,0,号节点，是否有通过,A,连接的儿子。,有！于是,2,号节点的前缀指针指向,1,号节点,3,号节点：,父亲是,1,号节点，连接字符为,B,，查找父亲的前缀指针,0,号节点，是否有通过,B,连接的儿子。,有！于是,3,号节点的前缀指针指向,1,号节点,4,号节点：,父亲是,2,号节点，连接字符为,B,，查找父亲的前缀指针,1,号节点，是否有通过,B,连接的儿子。,有！于是,4,号节点的前缀指针指向,3,号节点,5,号节点：,父亲是,3,号节点，连接字符为,A,，查找父亲的前缀指针,1,号节点，是否有通过,A,连接的儿子。,有！于是,5,号节点的前缀指针指向,2,号节点,8,号节点：,父亲是,7,号节点，连接字符为,B,，查找父亲的前缀指针,5,号节点，是否有通过,B,连接的儿子。,没有，继续查找,5,号节点的前缀指针,2,号节点是否有通过,B,连接的儿子。,有！于是,8,号节点的前缀指针指向,4,号节点,7,号节点：,父亲是,4,号节点，连接字符为,A,，查找父亲的前缀指针,3,号节点，是否有通过,A,连接的儿子。,有！于是,7,号节点的前缀指针指向,5,号节点,6,号节点：,父亲是,3,号节点，连接字符为,B,，查找父亲的前缀指针,1,号节点，是否有通过,B,连接的儿子。,有！于是,6,号节点的前缀指针指向,3,号节点,至此，这棵树的前缀指针我们就设计完成了！,对于一个插入了,n,个模式串的单词前缀树构造其前缀指针的时间复杂度为：,O(len(i),如何在建立好的,DFA,上遍历,以上的单词前缀树,+,前缀指针就是确定性有限状态自动机的树形结构图,(,即,trie,图）的基本构造方式了。,接下来要解决的问题是，已知一个串,S,，如何利用这个串在当前已经建立好的,DFA,上进行遍历，看其是否包含某个模式串，以及其时间复杂度。,遍历的方法如下：从,ROOT,出发，按照当前串的下一个字符,ch,来进行在树上的移动。若当前点,P,不存在通过,ch,连接的儿子，那么考虑,P,的前缀指针指向的节点,Q,，如果还无法找到通过,ch,连接的儿子节点，再考虑,Q,的前缀指针,直到找到通过,ch,连接的儿子，再继续遍历。,如果遍历过程中经过了某个终止节点，则说明,S,包含该终止节点代表的模式串,.,这样遍历一个串,S,的时间复杂度是,O(len(S),回到原问题,下面我们回到原来的那个多串模式匹配问题。,有了,DFA,这个好工具之后，这道题目就可以很简单的解决了。具体步骤如下：,1.,按照,M,个模式串构造出一个单词前缀树,2.,将这个单词前缀树加上前缀指针,3.,将原来,6N+6L-2,个原串在这个建立的,DFA,上进行遍历，将遍历到的终态的位置记录下来，便可以得到每个模式串在原串中出现的位置了。,回到原问题,现在来考虑一下，我们完成这个问题的算法的时间复杂度,(M,个模式串的总长度为,LEN),：,1.O(LEN),2.O(LEN),3.O(6N+6L-2)*len(i)=O(NL),因此总的时间复杂度为,O(LEN+NL),一个很不错的算法！,最纯粹的,Trie,图题目,给,N,个模式串，每个不超过个字符，再给,M,个句子，句子长度,100,判断每个句子里是否包含模式串,N 10,M pChildssi-a=NULL),pRoot-pChildssi-a=,Tree+nNodesCount;,nNodesCount+;,pRoot=pRoot-pChildssi-a;,pRoot-bStopNode=true;,void BuildDfa(),for(int i=0;i LETTERS;i+),Tree0.pChildsi=Tree+1;,Tree0.pPrev=NULL;,Tree1.pPrev=Tree;,deque q;,q.push_back(Tree+1);,while(!q.empty(),CNode*pRoot=q.front();,q.pop_front();,for(int i=0;i pChildsi;,if(p),CNode*pPrev=pRoot-pPrev;,while(pPrev),if(pPrev-pChildsi),p-pPrev=,pPrev-pChildsi;,if(p-pPrev-bStopNode),p-bStopNode=true;,/,自己的,pPrev,指向的节点是危险节点，则自己也是危险节点,break;,else,pPrev=pPrev-pPrev;,q.push_back(p);,/,对应于,while(!q.empty(),bool SearchDfa(char*s),CNode*p=Tree+1;,for(int i=0;si;i+),while(true),if(p-pChildssi-a),p=p-pChildssi-a;,if(p-bStopNode),return true;,break;,else,p=p-pPrev;,return false;,int main(),nNodesCount=2;,int M,N;,scanf(%d%d,/N,个模式串，,M,个句子,for(int i=0;i N;i+),char s20;,scanf(%s,s);,Insert(Tree+1,s);,BuildDfa();,for(int i=0;i M;i+),char s200;,scanf(%s,s);,cout SearchDfa(s)endl;,return 0;,2010,福州赛区题目,Computer Virus on Planet Pandora,有,n,个各不相同的长度不超过,1,000,的模式串（,0n=250,），和一个长度不超过,5,100,000,的母串。如果母串包含某个模式串或其反转（“,ABCD,”的反转是“,DCBA,”），则称母串被模式串感染。问母串一共被多少个模式串感染。,2010,福州赛区题目,Computer Virus on Planet Pandora,1),给模式串编上号，,Trie,图上每个终止节点记下它所对应的模式串的编号。为每个模式串设置一个是否已经被匹配的标记。走到某终止节点，就能知道哪个模式串被匹配，就设置其标记。,2),要注意的是，本题中，模式串里有可能一个串,A,是另一个模式串,B,的子串，在这种情况下，用母串在,Trie,图上跑一遍，就可能会发生走到,B,串的终止节点，即作出,B,被匹配的结论，但是却忽略了匹配,B,的过程中,A,其实也已经能够匹配这个情况。,2010,福州赛区题目,Computer Virus on Planet Pandora,2),的解决办法：,对,Trie,图上的每个节点设置一个“是否计算过”的标记，初始值全部为假。假定在原,Trie,树上的节点,x,所对应的字符串为,s,，那么,x,节点“已计算过”，就意味着,s,的所有模式子串，都已经被标记为“已匹配”。在用母串在,Trie,图上跑的过程中，每到达一个“未计算过”的节点，就将该节点标记为“已计算过”，然后就要将该节点对应的,s,的所有后缀模式串,(,既是,s,的后缀，又是模式串的字符串,),都标记为“已匹配”,(s,的非后缀模式子串在扫描到,s,之前就已经被标记为“已匹配”了。这个标记的过程，就是沿着节点的后缀指针一直走到根节点，将路径上,(,包括起点,),的每个模式串的终止节点所对应的模式串，都标记为“已匹配”。显然，这条路上的每个节点在,Trie,树上对应的字符串，都是,s,的后缀，而且所有既是,s,的后缀，且在,Trie,树上有对应节点的字符串，其对应节点也一定会出现在这条路经上。,小结,KMP,和,DFA,充分利用了当前已知的信息，构造出了,NEXT,数组和前缀指针，避免了比较过程中冗余，从而提高了算法的效率。,以上只是,DFA,很小的一个应用。,DFA,不但可以高效的处理多串模式匹配问题，而且在字符串模式匹配问题上，提供了一个新的数据储存结构，从而可以达到一些意想不到的效果。在,DFA,上进行动归，是常见的做法。,我们接着看下一道题,POI#7,题：病毒,已知若干个,01,串，他们是病毒的特征代码。如果一段程序（由,01,组成）不含有任何病毒特征代码，则称它为安全程序。请判断是否存在无限长的安全程序。,“,无限长”的安全母串，在,Trie,图上，从根节点出发，可以永远不停地走下去，即走无限步，都不会路过“不安全节点”，而,Trie,图节点是有限的,.,模式串对应的终止节点是“不安全”节点，如果有一个节点，它的前缀指针指向的节点是“不安全”节点，那么它也是“不安全节点”。,“,无限长”的安全母串，在,Trie,图上，从根节点出发，可以永远不停地走下去，即走无限步，都不会路过“不安全节点”，而,Trie,图节点是有限的,.,只需判断，,Trie,图上，由安全节点构成的子图上，有没有环即可，有，就能无限走下去,Trie,图上进行动归：,POJ 3691,DNA repair,给定不超过,50,个由 ,A,G,C,，,T.,四个字母组成的模式串，每个模式串长度不超过,20,，再给一个不超过,1000,个字符长的同样由上述字母组成的母串,S,问在,S,中至少要修改多少个字符，才能使其不包含任何模式串,Sample Input,2,AAA,AAG,AAAG,2,A,TG,TGAATG,4,A,G,C,T,AGT,0,Sample Output,Case 1:1,Case 2:4,Case 3:-1,试试,DFA,吧,对于这样的多字符串模式匹配问题，我们想到了,DFA,，那就试试吧。,首先按照给出的,P,个模式串构造一棵,DFA,出来。这时候，我们发现,DFA,给我们创建了一个很好的动态规划的平台。迅速给出状态：,Ansij,表示若要用长度为,i,的母串的前缀遍历,DFA,树，使之达到节点,j,，至少要修改多少个字符。,j,必须不是模式串的终止节点，或者“不安全”节点。,初始情况：,Ans01=0 /1,是,DFA,的初始节点,其他所有,Ansij,为无穷大,问题的答案就是,Min Anslenj|j,是,DFA,的安全节点,len,是母串的长度,试试,DFA,吧,状态转移方程为：,由,Ansij,可以推出：,Ansi+1sonj =min Ansi+1sonj,Ansij+(Char(j,sonj)!=stri),(Char(j,sonj)!=stri),表达式值为,0,或,1,Char(j,sonj),表示从节点,j,走到节点,sonj,所经过的字母,str,是母串,下标从,0,开始算,试试,DFA,吧,Char(j,sonj),表示从,j,到,sonj,经过的字母,假设是,a,。,这里所说的“经过”，不仅指从,j,通过一条字母,a,边直接到达,sonj,也可以是通过若干前缀指针后再通过一个字母,a,边到达,sonj,POJ1625 Censored!,题目大意：,给出一个字符集,V,和,P,个模式串,(,长度小于,10),，问由这个字符集中字符组成的长度为,N,的且不包含任意一个模式串的字符串有多少个？,(,字符集大小,N=50,P=10),样例：,输入：,2 3 1 /N=3 P=1,ab /,字符集为,ab,bb,输出：,5,样例解释：,aaa,aab,aba,baa,bab,以上,5,个,解题思路,这种类型的题目，如果使用搜索算法必然会导致超时的出现。因此，动态规划似乎是一种可行的方案，我们来尝试构造一个状态。,Ansij,表示长度为,i,且能走到节点,j,的字符串个数（节点,j,是安全节点）,初始,Ans01=1,其他,Ansij=0,由,Ansij,可以导出，每个由,j,可以到达的安全节点,sonj,都应执行：,Ansi+1sonj+=Ansij,因为从根走,i,步到达达节点,j,有,n,种走法个，那么走,i+1,步到达,sonj,的走法就要加,n(,因为,j,以外节点也可能通过一步走到,j),这里所说的“到达”，不仅指从,j(,或从其他节点）通过一条字母边直接到达,sonj,也可以是通过若干前缀指针后再通过一个字母边到达,sonj,整个问题最终的答案就是：,AnsNj|j,是安全节点,此题需要高精度计算,总结,像例题的题目还有很多，类似例题,2,的题目还有：,POJ2778 DNA Sequence,