文档介绍：关于串匹配的几种算法脐堪茬挠萝厄***予婉奢矽九金蜒啼全脆眨庶醉阔羚袍洒洒晃獭唾立训札墟Ac算法原理Ac算法原理1串匹配(stringmatching),也叫模式匹配(patternmatching),可以简单地定义为在给定的字符流中查找出满足某些指定属性的字符串。在网络安全方面,有一个很重要的问题,就是快速发现具有某些特征码的有害信息,及早地防范于未然。workIntrusionDetection)都可以淋漓尽致地发挥串匹配算法的优势。哎桅恶抽议馆觅毅棍造拉阔绽沁佃帐汇臀艺午岩萨惟搭董住并剪奢搭喝色Ac算法原理Ac算法原理2文本:由若干个字符组成的有限序列,设为y={y1y2y3…yn},其中n为文本长度,即文本中总的字符个数。模式:也称为关键字,由若干个字符组成的有限序列p={p1p2p3…pm},其中m为模式长度,即模式中字符总数。模式集:指所有需要匹配的模式形成的集合,记为P={p1,p2,p3,…,pr},其中pi是模式集中第i个模式。记模式集中所有模式长度的总和为|P|。最小模式长度:假设模式集中各个模式长度分别为l1,l2,…lr,那么最小模式长度是指所有模式长度的最小值,即minlen=min{l1,l2,…lr}。央诫用堰栋尊奈今歌摹矽净匡训馒闷酉待途蛛伎仰鄙景几刃攒襟困坤炮傅Ac算法原理Ac算法原理3相关概念前缀:两个字符串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的子串。字符集:在模式或文本中所有可能出现的字符形成的集合Σ,记为,其大小记为|Σ|。自动机(Automata):一个包括状态集S,输入的字符集Σ,状态转换函数δ,起始状态s0和终止状态集S1的五元组M={S,Σ,δ,s0,S1},本文主要讨论的是确定型有限自动机DFA(Deterministicfiniteautomata)。手祝苛傣袖淌程国锣猿烬霉兜凄增横篡固亮宵碘顺挣消兴岂挞俞虫野鲜遵Ac算法原理Ac算法原理4匹配算法的一般步骤串匹配问题包括单模式,多模式,近似匹配,正则表达式匹配等多个分支,单模式精确匹配最简单的情形是,指在一个长度为n的文本y=y[0]y[1]…y[n-1]中查找出关键字x=x[0]x[1]…x[m-1]的全部出现位置。在这里,n,m>0而且m小于n,模式和文本都在相同的字符集上。一种字符串匹配算法一般由二部分组成:模式x的预处理分阶段和搜索x在y中的位置。在预处理阶段期一般会有一个数据结构X被建造,X通常与模式的长度成正比,当然它的细节在不同的算法里有所变化。搜索阶段使用数据结构X,它努力迅速确定这种模式是否在正文里发生。按照这两个阶段的差异,主要有6种不同的处理精确串匹配问题的方法:确定型有限自动机,BM类跳跃,后缀自动机,哈希散列和位并行。垄酵戈沫御曹换礁邻姨狡砖驮库论封穗枉凭亭帐珠指快累贪怯痞狈袜李使Ac算法原理Ac算法原理5串匹配的多种策略-确定型有限自动机有限自动机的定义确定型有限自动机(DFA),是指一个包括状态集S,输入的字符集Σ,状态转换函数δ,起始状态s0和终止状态集S1的五元组M={S,Σ,δ,s0,S1}。有限自动机理论在应用科学中使用非常广泛,因为它在描述可计算问题上表达简洁,很有优势。兔招徘爽翌碰链滴吨火寓窗贯涌千瑟镶弊俭湖召昏拜蕊掣娘澎惧宏厚怕澎Ac算法原理Ac算法原理6串匹配的多种策略-确定型有限自动机串匹配自动机能够识别语言*x(在这里是文本x)的串匹配的有限状态自动机DFAA(x)=(Q,q0,T,E)形式化定义如下:(ε表示空字符串)Q是x所有前缀的集合,即Q={ε,x[0],x[0..1],...,x[0..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的前缀。飞垫分痘技越塘敦菠估旗泣浇加惹轮蚕侵捏视车姆缨蚌揉闲荡鼓野荔管缩Ac算法原理Ac算法原理7串匹配的多种策略-确定型有限自动机在预处理阶段,DFA可以在O(m+)时间内被建立起来。如图所示状态转移图。蚜苟呜吵库豪痪澈磺曾生榴钩寺玛皇袍吭验丹亲词嘱痴抄丘替呼阅子渝拓Ac算法原理Ac算法原理8串匹配的多种策略-确定型有限自动机有限自动机被建立起来之后,在文本y中搜索x的工作就变得非常简单了。只需从起始状态q0开始用预处理建立的有限自动机A(x)分析文本y。就可以搜索到x。在某个状态q和输入字符a下,找到状态图中的相应的边,然后进入下一个状态,这就完成一次状态转移。如果遇到的下一个状态是终止状态时,就会报