资源描述：
《多模式匹配快速算法的设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、http://www.paper.edu.cn多模式匹配快速算法的设计李胜才北京航空航天大学北京100083E-mail：buaalsc@163.com摘要：字符串匹配速度是关键字检测和过滤系统的核心。本文在有限状态自动机的AC算法的基础上，综合BM算法的跳跃思想和QS算法的优点，提出了一个快速的多模式字符串匹配算法。该算法能充分利用每次匹配过程中匹配不成功的信息和已经成功的信息，尽可能多地跳过待查文本串中的字符，从而不需要匹配目标文本串的每个字符，而在比较次数最少的情况下，能一次性无须回溯的实现对
2、文本的快速搜索。实验证明在模式串较长和较短的情况下，算法都能有效地改善关键字检测过滤系统的匹配性能。关键词：多模式串匹配；有限自动机；关键字检测过滤；匹配中图分类号：TP301引言在信息检索领域,串匹配问题一直都是研究的焦点之一。在拼写检查、基于字典的语言翻译、WWW搜索引擎、计算机病毒特征码匹配、数据压缩以及DNA序列匹配等应用中也都需要进行串匹配。同时在基于特征匹配的入侵检测系统中，模式匹配的效率直接决定这类入[2][6]侵检测系统的性能。因此字符串匹配速度的提高有着深渊的意义。当前的多模式速度
3、是[3][5]很多系统以及软件的瓶颈。对于单模式匹配问题,有三种经典的匹配算法:①KMP算法,它在最坏情况下也能保持线[1][5]性查找过程,其时间复杂度为Omn(+)，②BM算法,它采用“跳跃式”查找策略,多数情况下无须对文本进行一次完整的扫描,在模式中字符在文本中出现很少时时间复杂度能到最[4][5][6][8]好的Onm(/),平均情况下其时间复杂度为Omn(+)。③QS算法，在那些待匹配模式集中未使用的字符在文本T中大量出现时,可以利用它们的信息加快匹配速度。在最优情况下(模式串较短、模式串
4、中出现的字母数较少)比BM算法更快,其时间复杂度为Onm(/)，最坏[5]情况时为Onm(×)。目前的多模式匹配中没有一个很好的算法能结合以上各个单模式的优点，本文在充分分析各个单模式匹配算法的基础上提出了一个新的多模式匹配的算法。该算[8]法结合了Boyer_Moore(BM)算法从右向左跳跃的思想，以及能实现最大跳跃和尽可能少的比较次数的QuickSearch(QS)算法的优点，能充分利用每次匹配过程中匹配不成功的信息和已经成功的信息，尽可能多地跳过待查文本串中的字符，从而不需要匹配目标文本串的
5、每个字符，而在比较次数最少的情况下，就能一次性无须回溯的实现对文本的快速搜索。1.新算法设计设待查找文本为T[1,2,??n],其定义在一个有限的字母表∑(本文处理背景选择处理ANSI字符集0??256)上。多模式匹配则是从文本T中一次查找多个模式串PPP,,,??P（这里patten_num代表模式串的数目）,最短模式串的长度用minlen123pattennum_表示。算法设计的主要思想在于匹配不成功后充分挖掘已经成功匹配的信息结合当前匹配失-1-http://www.paper.edu.cn败
6、信息得到向后跳跃的距离t_shift[]。整个算法可以分为预处理和搜索两个部分。1.1预处理阶段1.1.1构建模式匹配自动机，即构建状态转移函数state_shift[][],输出函数output[]记录该状态下匹配成功的模式串下标，matched[state]记录当前状态state时已经匹配的字符串。构建多模式匹配自动机，也就是构建多模式下的搜索树。首先用待搜索的模式集构建一棵搜索树，然后将树的节点作为自动机的状态，树的分支作为自动机的状态转换函数。当字符在整个搜索树内进行匹配时，由于搜索树是预先
7、知道的，故可用AC算法预先构造一个包含所有模式信息的反向树型有限自动机。然后再利用BM算法，在文本中用搜索树对文本进行跳跃式的搜索。在构建搜索树时，将模式串的右边对齐，从右向左进行构建，树上相同的分支节点进行合并。这样匹配窗内文本最右面的字符就不需要和搜索树中的每一个字符进行匹配，而是直接将这个字符输入到匹配自动机，得到搜索树的匹配输出。在反向有限自动机的构造中，每个模式串的字符是从后向前输入到反向树型有限自动机的；匹配过程中，目标串的输入也是从后向前进行逆向扫描的。为方便描述本文的有限自动机是通过
8、二维矩阵state_shift[MAXSTATE][M1]来表示的，其中MAXSTATE事先定义，代表最大可能状态数，M1代表模式匹配的文本集合总数（本文限制在0~256之间）。以添加li，sheng，cai为例，介绍反向树的构造过程（如图1）-{i}0i1l2Step1添加liStep2添加sheng图1:Step3添加cai图中灰色状态表示该状态成功匹配模式串。1.1.2计算在扫描阶段可能出现的任何字符可以跳跃的最大距离:要获得更快的匹配算法，关键是在模式串匹配失
