《AC多模匹配算法.ppt

多模匹配算法 title Aho-Corasick自动机算法（简称AC自动机）1975年产生于贝尔实验室。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。 该算法的基本思想是这样的： 在预处理阶段，AC自动机算法建立了三个函数，转向函数goto，失效函数failure和输出函数output，由此构造了一个树型有限自动机。 在有哪些信誉好的足球投注网站查找阶段，则通过这三个函数的交叉使用扫描文本，定位出关键字在文本中的所有出现位置。 此算法有两个特点，一个是扫描文本时完全不需要回溯，另一个是时间复杂度为O(n)，时间复杂度与关键字的数目和长度无关。 2. 树型有限自动机： 树型有限自动机包含一组状态，每个状态用一个数字代表。状态机读入文本串y中的字符，然后通过产生状态转移或者偶尔发送输出的方式来处理文本。树型有限自动机的行为通过三个函数来指示：转向函数g，失效函数f和输出函数output。 3. 转向，失效和输出函数的构建 现在说明如何根据一个关键字集建立正确的转向、失效和输出函数。整个构建包含两个部分，在第一部分确定状态和转向函数，在第二部分我们计算失效函数。输出函数的计算则是穿插在第一部分和第二部分中完成。 为了构建转向函数，我们需要建立一个状态转移图。开始，这个图只包含一个代表状态0。然后，通过添加一条从起始状态出发的路径的方式，依次向图中输入每个关键字p。新的顶点和边被加入到图表中，以致于产生了一条能拼写出关键字p的路径。关键字p会被添加到这条路径的终止状态的输出函数中。当然只有必要时才会在图表中增加新的边。 AC和QS结合的反向自动机 王永成等人受FW92（一种融合了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入侵检测系统 * * wangyao@cs.hit.edu.cn Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. AC算法----有限自动机的多模式匹配算法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例如：对应模式集{he, she, his, hers}的树型有限自动机 图1 a） 转向函数g 图1 b） 失效函数f 图1 c） 输出函数output Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例如: 对关键字集{he, she, his, hers}建立转向函数。