《Ac算法原理PPT演示文稿》由会员分享，可在线阅读，更多相关《Ac算法原理PPT演示文稿（27页珍藏版）》请在金锄头文库上搜索。
1、哈尔滨工业大学 计算机学院1哈尔滨工业大学 计算机学院4串匹配（串匹配（string matching），也叫模式匹配），也叫模式匹配（pattern matching），可以简单地定义为在），可以简单地定义为在给定的字符流中查找出满足某些指定属性的字给定的字符流中查找出满足某些指定属性的字符串。符串。4在网络安全方面，有一个很重要的问题，就是在网络安全方面，有一个很重要的问题，就是快速发现具有某些特征码的有害信息，及早地快速发现具有某些特征码的有害信息，及早地防范于未然。病毒和入侵检测防范于未然。病毒和入侵检测NID（Network Intrusion Detection）都可以淋漓尽致地发
2、挥串）都可以淋漓尽致地发挥串匹配算法的优势。匹配算法的优势。 2哈尔滨工业大学 计算机学院4文本：由若干个字符组成的有限序列，设为文本：由若干个字符组成的有限序列，设为y=y1y2y3yn,其中其中n为文本长度，即文本中总的字符为文本长度，即文本中总的字符个数。个数。4模式：也称为关键字，由若干个字符组成的有限序列模式：也称为关键字，由若干个字符组成的有限序列p=p1p2p3pm，其中，其中m为模式长度，即模式中字符为模式长度，即模式中字符总数。总数。4模式集：指所有需要匹配的模式形成的集合，记为模式集：指所有需要匹配的模式形成的集合，记为P=p1,p2,p3,pr，其中，其中pi是模式集中第
3、是模式集中第i个模式。记个模式。记模式集中所有模式长度的总和为模式集中所有模式长度的总和为|P|。4最小模式长度：假设模式集中各个模式长度分别为最小模式长度：假设模式集中各个模式长度分别为l1,l2,lr,那么最小模式长度是指所有模式长度的最小那么最小模式长度是指所有模式长度的最小值，即值，即minlen = minl1,l2,lr。3哈尔滨工业大学 计算机学院相关概念相关概念4前缀：两个字符串前缀：两个字符串 p和和x，若存在字符串，若存在字符串v（v可为空串）可为空串），使得，使得p=xv成立，称成立，称x为为p的前缀。的前缀。4后缀：两个字符串后缀：两个字符串p和和x,若存在字符串若存在
4、字符串u（u可为空串），可为空串），使得使得p=ux成立成立x，称为，称为p的后缀。的后缀。4子串：两个字符串子串：两个字符串p和和x,若存在字符串若存在字符串u,v（u, v可以为可以为空串），使得空串），使得p=uxv成立，称成立，称x为为p的子串。的子串。4字符集：在模式或文本中所有可能出现的字符形成的字符集：在模式或文本中所有可能出现的字符形成的集合集合，记为，其大小记为，记为，其大小记为|。4自动机（自动机（Automata）：）： 一个包括状态集一个包括状态集S，输入的字，输入的字符集符集，状态转换函数，状态转换函数，起始状态，起始状态s0和终止状态集和终止状态集S1的五元组的五元
5、组M = S,s0,S1，本文主要讨论的是确定型，本文主要讨论的是确定型有限自动机有限自动机DFA(Deterministic finite automata)。4哈尔滨工业大学 计算机学院匹配算法的一般步骤匹配算法的一般步骤 4串匹配问题包括单模式，多模式，近似匹配，正则表串匹配问题包括单模式，多模式，近似匹配，正则表达式匹配等多个分支，单模式精确匹配最简单的情形达式匹配等多个分支，单模式精确匹配最简单的情形是，指在一个长度为是，指在一个长度为n的文本的文本y = y0y1yn-1中查中查找出关键字找出关键字x = x0x1xm-1的全部出现位置。在这的全部出现位置。在这里，里， n，m 0
6、而且而且m小于小于n，模式和文本都在相同的字，模式和文本都在相同的字符集上。符集上。4一种字符串匹配算法一般由二部分组成：模式一种字符串匹配算法一般由二部分组成：模式x的预处的预处理分阶段和搜索理分阶段和搜索x在在y中的位置。在预处理阶段期一般中的位置。在预处理阶段期一般会有一个数据结构会有一个数据结构X被建造，被建造，X通常与模式的长度成正通常与模式的长度成正比，当然它的细节在不同的算法里有所变化。搜索阶比，当然它的细节在不同的算法里有所变化。搜索阶段使用数据结构段使用数据结构X，它努力迅速确定这种模式是否在正，它努力迅速确定这种模式是否在正文里发生。文里发生。4按照这两个阶段的差异，主要有
7、按照这两个阶段的差异，主要有6种不同的处理精确串种不同的处理精确串匹配问题的方法：确定型有限自动机，匹配问题的方法：确定型有限自动机，BM类跳跃，后类跳跃，后缀自动机，哈希散列和位并行。缀自动机，哈希散列和位并行。5哈尔滨工业大学 计算机学院串匹配的多种策略串匹配的多种策略 -确定型有限自动机确定型有限自动机 4有限自动机的定义有限自动机的定义 确定型有限自动机（DFA），是指一个包括状态集S，输入的字符集，状态转换函数，起始状态s0和终止状态集S1的五元组M = S,s0,S1。有限自动机理论在应用科学中使用非常广泛，因为它在描述可计算问题上表达简洁，很有优势。 6哈尔滨工业大学 计算机学院
8、串匹配的多种策略串匹配的多种策略 -确定型有限自动机确定型有限自动机4串匹配自动机串匹配自动机 能够识别语言*x（在这里是文本x）的串匹配的有限状态自动机DFA A(x) =(Q, q0, T, E) 形式化定义如下：（表示空字符串）Q 是x所有前缀的集合，即Q=, x0, x0 . 1, . , x0 . m-2, x； q0=；T=x；如果q Q (q是x的前缀)且a ，那么(q, a, qa) E当且仅当qa 也是x的前缀，否则(q, a, p) E ，其中p是qa的最长后缀而且p也是x的前缀。7哈尔滨工业大学 计算机学院串匹配的多种策略串匹配的多种策略 -确定型有限自动机确定型有限自动
9、机4在预处理阶段，在预处理阶段，DFA可以在可以在O(m+)时间内被建时间内被建立起来。如图所示状态转移图。立起来。如图所示状态转移图。8哈尔滨工业大学 计算机学院串匹配的多种策略串匹配的多种策略 -确定型有限自动机确定型有限自动机4有限自动机被建立起来之后，在文本有限自动机被建立起来之后，在文本y中搜索中搜索x的工作就变得非常简单了。只需从起始状态的工作就变得非常简单了。只需从起始状态q0开始用预处理建立的有限自动机开始用预处理建立的有限自动机A(x)分析文本分析文本y。就可以搜索到就可以搜索到x。在某个状态。在某个状态q和输入字符和输入字符a下，下，找到状态图中的相应的边，然后进入下一个状
10、找到状态图中的相应的边，然后进入下一个状态，这就完成一次状态转移。如果遇到的下一态，这就完成一次状态转移。如果遇到的下一个状态是终止状态时，就会报告模式个状态是终止状态时，就会报告模式x被匹配被匹配上，即上，即x在文本在文本y中出现一次。中出现一次。9哈尔滨工业大学 计算机学院Aho-Corasick自动机算法自动机算法 4Aho-Corasick自动机算法（简称自动机算法（简称AC自动机）自动机）1975年产生于贝尔实验室，这种算法最早被使年产生于贝尔实验室，这种算法最早被使用在图书馆的书目查询程序中，取得了很好的用在图书馆的书目查询程序中，取得了很好的效果效果 4在预处理阶段，在预处理阶段
11、，AC自动机算法建立了三个函自动机算法建立了三个函数数 转向函数goto 失效函数failure 输出函数output 10哈尔滨工业大学 计算机学院Aho-Corasick自动机算法自动机算法-数据结构和算法流程数据结构和算法流程 4树型有限自动机是一种确定型有限自动机，对树型有限自动机是一种确定型有限自动机，对应模式串集应模式串集P的树型有限自动机是一个程序。的树型有限自动机是一个程序。 4把输入文本把输入文本y作为输入，输出作为输入，输出P中关键字在中关键字在y中中作为子串出现的位置。作为子串出现的位置。 4树型有限自动机包含一组状态，每个状态用一树型有限自动机包含一组状态，每个状态用一
12、个数字代表。个数字代表。 4状态机读入文本串状态机读入文本串y中的字符，然后通过产生中的字符，然后通过产生状态转移或者偶尔发送输出的方式来处理文本。状态转移或者偶尔发送输出的方式来处理文本。 11哈尔滨工业大学 计算机学院Aho-Corasick自动机算法自动机算法-数据结构和算法流程数据结构和算法流程转向函数把一个由状态和输入字符组成的二元组映射成另转向函数把一个由状态和输入字符组成的二元组映射成另一个状态或者一条失败消息转向函数一个状态或者一条失败消息转向函数 对应模式串集对应模式串集he, she, his, hers的树型有限自动机的树型有限自动机 0128967345h,shersi
13、sshe12哈尔滨工业大学 计算机学院Aho-Corasick自动机算法自动机算法-数据结构和算法流程数据结构和算法流程失效函数失效函数f ,失效函数把一个状态映射成另一个状态。失效函数把一个状态映射成另一个状态。当转向函数报告失效时，失效函数就会被询问当转向函数报告失效时，失效函数就会被询问 输出函数output 13哈尔滨工业大学 计算机学院Aho-Corasick自动机工作过程自动机工作过程4s为状态机的当前状态，为状态机的当前状态， a为输入文本为输入文本y的当前的当前输入字符输入字符 4如果如果g(s, a) = s ，那么树型有限自动机将做一，那么树型有限自动机将做一个转向动作。自
14、动机进入状态个转向动作。自动机进入状态s，而且，而且y的下的下一个字符变成当前的输入字符。另外，如果一个字符变成当前的输入字符。另外，如果output( s)不为空，那么状态机将输出与当前输入不为空，那么状态机将输出与当前输入字符位置相对应的一组关键字。字符位置相对应的一组关键字。4如果如果g(s, a) = fail，状态机将询问失效函数，状态机将询问失效函数f并并且进行失效转移。且进行失效转移。 4 f(s) = s，那么状态机将以，那么状态机将以s作为当前状态，作为当前状态，a为当前输入字符重复这个操作循环。为当前输入字符重复这个操作循环。 14哈尔滨工业大学 计算机学院01289673
15、45h,shersissheG(1,e)=2G(4,i)=faileF(4)=1State=f(4)=1,g(1,i)=615哈尔滨工业大学 计算机学院一个例子一个例子4举个例子，记树型有限自动机为状态机举个例子，记树型有限自动机为状态机M。状态机状态机M利用的函数去处理输入文本利用的函数去处理输入文本“ushers”，下图显示了，下图显示了M在处理文本串时产在处理文本串时产生的状态转移情况。生的状态转移情况。16哈尔滨工业大学 计算机学院一个例子一个例子ushers0128967345h,shersissheu s h e r sOutput(5)=she,heF(5)=2,state=2F
16、(8)=0 state=017哈尔滨工业大学 计算机学院自动机的工作过程自动机的工作过程算法算法1：树型有限状态机。：树型有限状态机。输入：一个字符串输入：一个字符串y=y1y2y3yn（其中（其中yi是一个输入字符）；一台是一个输入字符）；一台 包含包含上述转向函数上述转向函数g，失效函数，失效函数f和输出函数和输出函数output的树型有限自动机。的树型有限自动机。输出：关键字在输出：关键字在y中出现的位置。中出现的位置。18哈尔滨工业大学 计算机学院转向函数的构建转向函数的构建 4为了构建转向函数，我们需要建立一个状态转为了构建转向函数，我们需要建立一个状态转移图移图 4开始，这个图只包
17、含一个代表状态开始，这个图只包含一个代表状态0的向量。的向量。 4然后，通过添加一条从起始状态出发的路径的然后，通过添加一条从起始状态出发的路径的方式，依次向图中输入每个关键字方式，依次向图中输入每个关键字p。 4新的顶点和边被加入到图表中，以致于产生了新的顶点和边被加入到图表中，以致于产生了一条能拼写出关键字一条能拼写出关键字p的路径。关键字的路径。关键字p会被添会被添加到这条路径的终止状态的输出函数中。当然加到这条路径的终止状态的输出函数中。当然只有必要时才会在图表中增加新的边。只有必要时才会在图表中增加新的边。 19哈尔滨工业大学 计算机学院转向函数的构建转向函数的构建4比如，对关键字集
18、比如，对关键字集he, she, his, hers建立建立转向函数。向图表中添加第一个关键字，转向函数。向图表中添加第一个关键字，得到：得到：0128967345h,shersisshe20哈尔滨工业大学 计算机学院失效函数失效函数 4失效函数是根据转向函数建立的失效函数是根据转向函数建立的 4我们定义状态转移图中状态我们定义状态转移图中状态s的深度为从的深度为从状态状态0到状态到状态s的最短路径。的最短路径。4先计算所有深度是先计算所有深度是1的状态的失效函数值，的状态的失效函数值，然后计算所有深度为然后计算所有深度为2的状态，以此类推，的状态，以此类推，直到所有状态的失效函数值都被计算出
19、。直到所有状态的失效函数值都被计算出。 21哈尔滨工业大学 计算机学院失效函数失效函数4令所有深度为令所有深度为1的状态的状态s的函数值为的函数值为f(s) = 0 4现在假设所有深度小于现在假设所有深度小于d的状态的的状态的f值都已经被值都已经被算出了，那么深度为算出了，那么深度为d的状态的失效函数值将的状态的失效函数值将根据深度小于根据深度小于d的状态的失效函数值来计算的状态的失效函数值来计算 4其中深度为其中深度为d的状态又是由深度为的状态又是由深度为d-1状态的非状态的非失效转向函数值确定得到的。失效转向函数值确定得到的。4为了计算深度为为了计算深度为d的状态的状态r的失效函数值，我们
20、的失效函数值，我们考虑深度为考虑深度为d-1的状态的状态r 22哈尔滨工业大学 计算机学院0128967345h,shersisshe23哈尔滨工业大学 计算机学院失效函数失效函数4g(r,a)=r4state=f(r)4f(r)=g(state,a)4d=1 41,34f(1)=0,f(3)=04d=242=g(1,e),state=f(1)=0, f(2)=g(state,e)=046=g(1,i),state=f(1)=0, f(6)=g(state,i)=044=g(3,h),state=f(3)=0, f(4)=g(state,h)=g(0,h)=124哈尔滨工业大学 计算机学院失效
21、函数失效函数4g(r,a)=r4state=f(r) if g(state,a)=fails state=f(r)4f(r)=g(state,a)4f(6)=0 f(2)=0 f(4)=14d=348=g(2,r) state=f(2)=0, f(8)=g(state,r)=047=g(6,s) state=f(6)=0,f(7)=g(state,s)=g(0,s)=345=g(4,e) state=f(4)=1,f(5)=g(1,e)=24d=449=g(8,s) state=f(8)=0,f(9)=g(0,s)=325哈尔滨工业大学 计算机学院输出函数输出函数4在计算失效函数的过程中，也更
22、新了输在计算失效函数的过程中，也更新了输出函数。当求出出函数。当求出f(s) = s时，我们把状态时，我们把状态s的输出和状态的输出和状态s的输出合并到一起。的输出合并到一起。4对于上面的例子，对于上面的例子，f(5) = 2。这时，把状。这时，把状态态2的输出集，也就是的输出集，也就是he，增加到状态，增加到状态5的输出集中，这样就得到了的输出集中，这样就得到了5的新的输出的新的输出集合集合he, she。26哈尔滨工业大学 计算机学院4建立转向建立转向函数函数g。4输入：关输入：关键字集键字集P=p1,p2,p3,pr。4输出：转输出：转向函数向函数g和部和部分的分的output函数函数 27
