多模匹配算法-ac算法

《多模匹配算法-ac算法》由会员分享，可在线阅读，更多相关《多模匹配算法-ac算法（28页珍藏版）》请在金锄头文库上搜索。

1、多模匹配算法,,title,Aho-Corasick自动机算法（简称AC自动机）1975年产生于贝尔实验室。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。 该算法的基本思想是这样的： 在预处理阶段，AC自动机算法建立了三个函数，转向函数goto，失效函数failure和输出函数output，由此构造了一个树型有限自动机。 在搜索查找阶段，则通过这三个函数的交叉使用扫描文本，定位出关键字在文本中的所有出现位置。 此算法有两个特点，一个是扫描文本时完全不需要回溯，另一个是时间复杂度为O(n)，时间复杂度与关键字的数目和长度无关。,AC算法-有限自动机的多模式匹配算法,2. 树型有限自动机：

2、 树型有限自动机包含一组状态，每个状态用一个数字代表。状态机读入文本串y中的字符，然后通过产生状态转移或者偶尔发送输出的方式来处理文本。树型有限自动机的行为通过三个函数来指示：转向函数g，失效函数f和输出函数output。,例如：对应模式集he, she, his, hers的树型有限自动机,图1 a） 转向函数g,图1 b） 失效函数f,图1 c） 输出函数output,3. 转向，失效和输出函数的构建 现在说明如何根据一个关键字集建立正确的转向、失效和输出函数。整个构建包含两个部分，在第一部分确定状态和转向函数，在第二部分我们计算失效函数。输出函数的计算则是穿插在第一部分和第二部分中完成。

3、 为了构建转向函数，我们需要建立一个状态转移图。开始，这个图只包含一个代表状态0。然后，通过添加一条从起始状态出发的路径的方式，依次向图中输入每个关键字p。新的顶点和边被加入到图表中，以致于产生了一条能拼写出关键字p的路径。关键字p会被添加到这条路径的终止状态的输出函数中。当然只有必要时才会在图表中增加新的边。,例如: 对关键字集he, she, his, hers建立转向函数。 向图表中添加第一个关键字，得到：,从状态0到状态2的路径拼写出了关键字“he”，我们把输出“he”和状态2相关联。 添加第二个关键字“she”，得到：,输出“she”和状态5相关联。,增加第三个关键字“his”，我们

4、得到了下面这个图。注意到当我们增加关键字“his”时，已经存在一条从状态0到状态1标记着h的边了，所以我们不必另外添加一条同样的边。,输出“his”是和状态7相关联的,添加第四个关键字“hers”，可以得到：,输出“hers”和状态9相关联。 在这里，我们能够使用已有的两条边：一条是从状态0到1标记着h的边；一条是从状态1到2标记着e的边。,这样，图已经成为一棵带根的树。为了完成转向函数的构建，我们对除了h和s外的其他每个字符，都增加一个从状态0到状态0的循环。这样，我们得到了如图1 a) 所示的状态转移图，这个图就代表转向函数。,算法1：建立转向函数g。 输入：关键字集P=p1,p2,p3,

5、pr。 输出：转向函数g和部分的output函数。 方法:,图2 建立转向函数g的伪代码,失效函数是根据转向函数建立的。首先，我们定义状态转移图中状态s的深度为从状态0到状态s的最短路径。 例如图1 a)起始状态的深度是0，状态1和3的深度是1，状态2，4，和6的深度是2，等等。,图1 a) d(0) = 0; d(1) = d(3) = 1; d(2) = d(6) = d(4) = 2 d(8) = d(7) = d(5) = 3; d(9) = 4,计算思路：先计算所有深度是1的状态的失效函数值，然后计算所有深度为2的状态，以此类推，直到所有状态（除了状态0，因为它的深度没有定义）的失效

6、函数值都被计算出。 计算方法：用于计算某个状态失效函数值的算法在概念上是非常简单的。首先，令所有深度为1的状态s的函数值为f(s) = 0。假设所有深度小于d的状态的f值都已经被算出了，那么深度为d的状态的失效函数值将根据深度小于d的状态的失效函数值来计算。,为了计算深度为d状态的失效函数值，我们考虑每个深度为d-1的状态r，执行以下步骤： Step1：如果对所有状态a的g(r, a) = fail，那么什么都不做 Step2：否则，对每个使得g(r, a) = s存在的状态s，执行以下操作 记state = f(r)。 零次或者多次令state = f(state)，直到出现一个状态使得g(

7、state, a) != fail（注意到，因为对任意字符a，g(0, a) != fail，所以这种状态一定能够找到） Step2：记f(s) = g(state, a),以图1 a)为例说明计算的失效函数f； 先令f(1) = f(3) = 0，因为1和3是深度为1的状态。 计算深度为2的状态2，6和4的失效函数。 计算f(2)，令state = f(1) = 0；由于g(0, a) = 0，得到f(2) = 0。 计算f(6)，令state = f(1) = 0；由于g(0, i) = 0，得到f(6) = 0 。 计算f(4)，令state = f(3) = 0； 由于g(0, h)

8、= 1，得到f(4) = 1。 按这种方式继续，最终得到了如图1 b) 所示的失效函数f。 在计算失效函数的过程中，也更新了输出函数。当求出f(s) = s，时，我们把状态s的输出和状态s，的输出合并到一起。对于上文中的例子，从图1 a) 我们求出f(5) = 2。这时，把状态2的输出集，也就是he，增加到状态5的输出集中，这样就得到了新的输出集合he, she。最终各状态的非空输出集如图1 c) 所示。,算法2：建立失效函数f。 输入：转向函数g和部分的输出函数output。 输出：失效函数f和完整的输出函数output。 方法:,图3 建立失效函数f的伪代码,4. 转向函数的构建 图1中树

9、型自动机的状态有0, 1, , 9。某个状态（通常是0状态）被指定为起始状态。 转向函数把一个由状态和输入字符组成的二元组映射成另一个状态或者一条失败消息。 图1 a) 的状态图代表转向函数g。比如,从0到1标记着h 的边表示g(0, h) = 1，如果缺省箭头则表示失败。可见，对除e和i之外的其他输入字符，都有g(1, h) = fail。所有的树型有限自动机都有一个共同的特点，即对任何输入字符a, 都有g(0, a) != fail。我们将看到，转向函数在0状态上的这种性质确保每个输入字符都可以在状态机的一个操作循环内被处理。,举个例子，记树型有限自动机为状态机M。状态机M利用图1的函数去

10、处理输入文本“ushers”，图4显示了M在处理文本串时产生的状态转移情况。,考虑M在状态4，且当前输入字符为e时的操作循环。由于g(4, e) = 5，状态机进入状态5，文本指针将前进到下一个输入字符，并且输出output(5)。这个输出表明状态机已经发现输入文本的第四个位置是“she”和“he”出现的结束位置。在状态5上输入字符r，状态机M在此次操作循环中将产生两次状态转移。由于g(5, r) = fail，M进入状态2 = f(5)。然后因为g(2, r) = 8，M进入状态8，同时前进到下一个输入字符。在这次操作循环中没有输出产生。,图4 扫描“ushers”时的状态转换序列,记s为状

11、态机的当前状态，a为输入文本y的当前输入字符。树型有限自动机的一次操作循环可以定义如下： 如果g(s, a) = s，那么树型有限自动机将做一个转向动作。自动机进入状态s，而且y的下一个字符变成当前的输入字符。另外，如果output( s，)不为空，那么状态机将输出与当前输入字符位置相对应的一组关键字。 如果g(s, a) = fail，状态机将询问失效函数f并且进行失效转移。如果 f(s) = s，那么状态机将以s，作为当前状态，a为当前输入字符重复这个操作循环。,算法3：树型有限状态机。 输入：一个字符串y=y1y2y3yn（其中yi是一个输入字符）；一台 包含上述转向函数g，失效函数f和

12、输出函数output的树型有限自动机。 输出：关键字在y中出现的位置。,图5 建立树型有限自动机的算法伪代码,5. AC自动机 预处理阶段： 转向函数把一个由状态和输入字符组成的二元组映射成另一个状态或者一条失败消息。 失效函数把一个状态映射成另一个状态。当转向函数报告失效时，失效函数就会被询问。 输出状态，它们表示已经有一组关键字被发现。输出函数通过把一组关键字集（可能是空集）和每个状态相联系的方法，使得这种输出状态的概念形式化。 搜索查找阶段： 文本扫描开始时，初始状态置为状态机的当前状态，而输入文本y的首字符作为当前输入字符。然后，树型有限自动机通过对每个文本串的字符都做一次操作循环的方

13、式来处理文本。,经典的多模式匹配算法- AC自动机。 在预处理阶段，AC自动机算法建立了三个函数，转向函数goto，失效函数failure和输出函数output，由此构造了一个树型有限自动机。 在搜索查找阶段，则通过这三个函数的交叉使用扫描文本，定位出关键字在文本中的所有出现位置。 此算法有两个特点，一个是扫描文本时完全不需要回溯，另一个是时间复杂度为O(n)，时间复杂度与关键字的数目和长度无关。,1975年，Aho和Corasick提出基于确定性有限自动机(DFA) 理论的模式匹配算法，这又是模式匹配问题中一个经典的算法。实际上，多模式匹配算法中，有很大一部分都是基于自动机理论的，而且有不少

14、都是基于对AC75算法的改进。 1979年，Commentz和Walter.B 发明的算法（简称CW79算法）结合了BM算法，在AC75的自动机算法上实现了跳跃扫描文本。 除了自动机这种主流多模式匹配思想外还有一种很有效的想法。这就是哈希（Hashing），Hashing方法的串查寻最早是在1971年被Harrison介绍，之后得到了充分地分析。1992年到1996年，台湾人Sun Wu和他的导师Udi Manber发表了一系列的论文 ，详细地介绍了他们设计的匹配算法，并用此算法实现了一个Unix下类似fgrep的工具：agrep。,AC和QS结合的反向自动机 王永成等人受FW92（一种融合了

15、BM的自动机算法），提出的相类似的结合QS的反向自动机多模式匹配算法，而且是针对纯中文的处理算法。,Wu.Sum和Udi.manber的agrep 92年台湾学者吴升发明的agrep是多模式中最位著名的快速匹配算法之一，对处理大规模的多关键字匹配问题有很好的效果。,DAWG-MATCH DAWG是一种后缀自动机（Suffix Automaton），是建立在模式集P上，能够辨认出模式集P中所有关键字后缀的确定型自动机。这种思想主要是AC和RF的结合结果。,Raffinot的MultiBDM 在上述的AC和DAWG两种自动机扫描思想上产生的多模匹配算法。根据匹配过程中使用时刻的不同，作者提出了两种改进。在作者的实验中，处理大规模的多关键字匹配问题中有较好的优势。,SumKim99 一种使用HashTable和Bit-Parallel的算法。它的处理过程比较特别，先对模式数值化压缩存储，然后使用HashTable直接定位出当前读入的字符将可能匹配上的关键字的范围，接着再用位运算对可能匹配上的关键字逐个比较，判定文本中是否有关键字出现。,参考文献,1、一种针对网络流式文本数据的匹配算法 2、改进的中文串多模式匹配算法 3、Snort入侵检测系统,