Ac算法原理.pptVIP

串匹配（string matching），也叫模式匹配（pattern matching），可以简单地定义为在给定的字符流中查找出满足某些指定属性的字符串。 在网络安全方面，有一个很重要的问题，就是快速发现具有某些特征码的有害信息，及早地防范于未然。病毒和入侵检测NID（Network Intrusion Detection）都可以淋漓尽致地发挥串匹配算法的优势。 文本：由若干个字符组成的有限序列，设为y={y1y2y3…yn},其中n为文本长度，即文本中总的字符个数。 模式：也称为关键字，由若干个字符组成的有限序列p={p1p2p3…pm}，其中m为模式长度，即模式中字符总数。 模式集：指所有需要匹配的模式形成的集合，记为P={p1,p2,p3,…,pr}，其中pi是模式集中第i个模式。记模式集中所有模式长度的总和为|P|。 最小模式长度：假设模式集中各个模式长度分别为l1,l2,…lr,那么最小模式长度是指所有模式长度的最小值，即minlen = min{l1,l2,…lr}。 相关概念 前缀：两个字符串 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(Deterministic finite automata)。 匹配算法的一般步骤 串匹配问题包括单模式，多模式，近似匹配，正则表达式匹配等多个分支，单模式精确匹配最简单的情形是，指在一个长度为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类跳跃，后缀自动机，哈希散列和位并行。 串匹配的多种策略 -确定型有限自动机 有限自动机的定义 确定型有限自动机（DFA），是指一个包括状态集S，输入的字符集Σ，状态转换函数δ，起始状态s0和终止状态集S1的五元组M = {S,Σ,δ,s0,S1}。有限自动机理论在应用科学中使用非常广泛，因为它在描述可计算问题上表达简洁，很有优势。 串匹配的多种策略 -确定型有限自动机 串匹配自动机 能够识别语言*x（在这里是文本x）的串匹配的有限状态自动机DFA A(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的前缀。 串匹配的多种策略 -确定型有限自动机 在预处理阶段，DFA可以在O(m+)时间内被建立起来。如图所示状态转移图。 串匹配的多种策略 -确定型有限自动机 有限自动机被建立起来之后，在文本y中有哪些信誉好的足球投注网站x的工作就变得非常简单了。只需从起始状态q0开始用预处理建立的有限自动机A(x)分析文本y。就可以有哪些信誉好的足球投注网站到x。在某个状态q和输入字符a下，找到状态图中的相应的边，然后进入下一个状态，这就完成一次状态转移。如果遇到的下一个状态是终止状态时，就会报告模式x被匹配上，即x在文本y中出现一次。 Aho-Corasick自动机算法 Aho-Corasick自动机算法（简称AC自动机）1975年产生于贝尔实验室，这种算法最早被使用在图书馆的书目查询程序中，取得了很好的效果 在预处理阶段，AC自动机算法建立了三个函数 转向函数goto 失效函数failure 输出函数output Aho-Corasick自动机算法-数据结构和算法流程 树型有限自动机是一种确定型有限自动机，对应模式串集P的树型有限自动机是一个程序。 把输入文本y作为输入，输出P中关键字在y中作