Ac算法原理PPT演示文稿

1、1,关于串匹配的几种算法,2,串匹配（string matching），也叫模式匹配（pattern matching），可以简单地定义为在给定的字符流中查找出满足某些指定属性的字符串。 在网络安全方面，有一个很重要的问题，就是快速发现具有某些特征码的有害信息，及早地防范于未然。病毒和入侵检测NID（Network Intrusion Detection）都可以淋漓尽致地发挥串匹配算法的优势,3,文本：由若干个字符组成的有限序列，设为y=y1y2y3yn,其中n为文本长度，即文本中总的字符个数。 模式：也称为关键字，由若干个字符组成的有限序列p=p1p2p3pm，其中m为模式长度，即模式中字符

2、总数。 模式集：指所有需要匹配的模式形成的集合，记为P=p1,p2,p3,pr，其中pi是模式集中第i个模式。记模式集中所有模式长度的总和为|P|。 最小模式长度：假设模式集中各个模式长度分别为l1,l2,lr,那么最小模式长度是指所有模式长度的最小值，即minlen = minl1,l2,lr,4,相关概念,前缀：两个字符串 p和x，若存在字符串v（v可为空串），使得p=xv成立，称x为p的前缀。 后缀：两个字符串p和x,若存在字符串u（u可为空串），使得p=ux成立x，称为p的后缀。 子串：两个字符串p和x,若存在字符串u,v（u, v可以为空串），使得p=uxv成立，称x为p的子串。 字

3、符集：在模式或文本中所有可能出现的字符形成的集合，记为，其大小记为|。 自动机（Automata）： 一个包括状态集S，输入的字符集，状态转换函数，起始状态s0和终止状态集S1的五元组M = S,s0,S1，本文主要讨论的是确定型有限自动机DFA(Deterministic finite automata,5,匹配算法的一般步骤,串匹配问题包括单模式，多模式，近似匹配，正则表达式匹配等多个分支，单模式精确匹配最简单的情形是，指在一个长度为n的文本y = y0y1yn-1中查找出关键字x = x0 x1xm-1的全部出现位置。在这里， n，m 0而且m小于n，模式和文本都在相同的字符集上。 一种

4、字符串匹配算法一般由二部分组成：模式x的预处理分阶段和搜索x在y中的位置。在预处理阶段期一般会有一个数据结构X被建造，X通常与模式的长度成正比，当然它的细节在不同的算法里有所变化。搜索阶段使用数据结构X，它努力迅速确定这种模式是否在正文里发生。 按照这两个阶段的差异，主要有6种不同的处理精确串匹配问题的方法：确定型有限自动机，BM类跳跃，后缀自动机，哈希散列和位并行,6,串匹配的多种策略 -确定型有限自动机,有限自动机的定义 确定型有限自动机（DFA），是指一个包括状态集S，输入的字符集，状态转换函数，起始状态s0和终止状态集S1的五元组M = S,s0,S1。有限自动机理论在应用科学中使用非

5、常广泛，因为它在描述可计算问题上表达简洁，很有优势,7,串匹配的多种策略 -确定型有限自动机,串匹配自动机 能够识别语言*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的前缀,8,串匹配的多种策略 -确定型有限自动机,在预处理阶段，DFA可以在O(m+

6、)时间内被建立起来。如图所示状态转移图,9,串匹配的多种策略 -确定型有限自动机,有限自动机被建立起来之后，在文本y中搜索x的工作就变得非常简单了。只需从起始状态q0开始用预处理建立的有限自动机A(x)分析文本y。就可以搜索到x。在某个状态q和输入字符a下，找到状态图中的相应的边，然后进入下一个状态，这就完成一次状态转移。如果遇到的下一个状态是终止状态时，就会报告模式x被匹配上，即x在文本y中出现一次,10,Aho-Corasick自动机算法,Aho-Corasick自动机算法（简称AC自动机）1975年产生于贝尔实验室，这种算法最早被使用在图书馆的书目查询程序中，取得了很好的效果 在预处理阶

7、段，AC自动机算法建立了三个函数 转向函数goto 失效函数failure 输出函数output,11,Aho-Corasick自动机算法-数据结构和算法流程,树型有限自动机是一种确定型有限自动机，对应模式串集P的树型有限自动机是一个程序。 把输入文本y作为输入，输出P中关键字在y中作为子串出现的位置。 树型有限自动机包含一组状态，每个状态用一个数字代表。 状态机读入文本串y中的字符，然后通过产生状态转移或者偶尔发送输出的方式来处理文本,12,Aho-Corasick自动机算法-数据结构和算法流程,转向函数把一个由状态和输入字符组成的二元组映射成另一个状态或者一条失败消息转向函数,对应模式串集

8、he, she, his, hers的树型有限自动机,0,1,2,8,9,6,7,3,4,5,h,s,h,e,r,s,i,s,s,h,e,13,Aho-Corasick自动机算法-数据结构和算法流程,失效函数f ,失效函数把一个状态映射成另一个状态。当转向函数报告失效时，失效函数就会被询问,输出函数output,14,Aho-Corasick自动机工作过程,s为状态机的当前状态， a为输入文本y的当前输入字符 如果g(s, a) = s ，那么树型有限自动机将做一个转向动作。自动机进入状态s，而且y的下一个字符变成当前的输入字符。另外，如果output( s)不为空，那么状态机将输出与当前输入

9、字符位置相对应的一组关键字。 如果g(s, a) = fail，状态机将询问失效函数f并且进行失效转移。 f(s) = s，那么状态机将以s作为当前状态，a为当前输入字符重复这个操作循环,15,0,1,2,8,9,6,7,3,4,5,h,s,h,e,r,s,i,s,s,h,e,G(1,e)=2,G(4,i)=faile,F(4)=1,State=f(4)=1,g(1,i)=6,16,一个例子,举个例子，记树型有限自动机为状态机M。状态机M利用的函数去处理输入文本“ushers”，下图显示了M在处理文本串时产生的状态转移情况,17,一个例子,ushers,0,1,2,8,9,6,7,3,4,5,

10、h,s,h,e,r,s,i,s,s,h,e,u,s,h,e,r,s,Output(5)=she,he,F(5)=2,state=2,F(8)=0 state=0,18,自动机的工作过程,算法1：树型有限状态机。 输入：一个字符串y=y1y2y3yn（其中yi是一个输入字符）；一台 包含上述转向函数g，失效函数f和输出函数output的树型有限自动机。 输出：关键字在y中出现的位置,19,转向函数的构建,为了构建转向函数，我们需要建立一个状态转移图 开始，这个图只包含一个代表状态0的向量。 然后，通过添加一条从起始状态出发的路径的方式，依次向图中输入每个关键字p。 新的顶点和边被加入到图表中，以

11、致于产生了一条能拼写出关键字p的路径。关键字p会被添加到这条路径的终止状态的输出函数中。当然只有必要时才会在图表中增加新的边,20,转向函数的构建,比如，对关键字集he, she, his, hers建立转向函数。向图表中添加第一个关键字，得到,0,1,2,8,9,6,7,3,4,5,h,s,h,e,r,s,i,s,s,h,e,21,失效函数,失效函数是根据转向函数建立的 我们定义状态转移图中状态s的深度为从状态0到状态s的最短路径。 先计算所有深度是1的状态的失效函数值，然后计算所有深度为2的状态，以此类推，直到所有状态的失效函数值都被计算出,22,失效函数,令所有深度为1的状态s的函数值为

12、f(s) = 0 现在假设所有深度小于d的状态的f值都已经被算出了，那么深度为d的状态的失效函数值将根据深度小于d的状态的失效函数值来计算 其中深度为d的状态又是由深度为d-1状态的非失效转向函数值确定得到的。 为了计算深度为d的状态r的失效函数值，我们考虑深度为d-1的状态r,23,0,1,2,8,9,6,7,3,4,5,h,s,h,e,r,s,i,s,s,h,e,24,失效函数,g(r,a)=r state=f(r) f(r)=g(state,a) d=1 1,3 f(1)=0,f(3)=0 d=2 2=g(1,e),state=f(1)=0, f(2)=g(state,e)=0 6=g(

13、1,i),state=f(1)=0, f(6)=g(state,i)=0 4=g(3,h),state=f(3)=0, f(4)=g(state,h)=g(0,h)=1,25,失效函数,g(r,a)=r state=f(r) if g(state,a)=fails state=f(r) f(r)=g(state,a) f(6)=0 f(2)=0 f(4)=1 d=3 8=g(2,r) state=f(2)=0, f(8)=g(state,r)=0 7=g(6,s) state=f(6)=0,f(7)=g(state,s)=g(0,s)=3 5=g(4,e) state=f(4)=1,f(5)=g(1,e)=2 d=4 9=g(8,s) state=f(8