多模式匹配快速算法的设计.pdf

http://www.paper.edu.cn

多模式匹配快速算法的设计

李胜才

北京航空航天大学北京100083

E-mail：[e-mail]
摘要：字符串匹配速度是关键字检测和过滤系统的核心。本文在有限状态自动机的AC算
法的基础上，综合BM算法的跳跃思想和QS算法的优点，提出了一个快速的多模式字符
串匹配算法。该算法能充分利用每次匹配过程中匹配不成功的信息和已经成功的信息，尽可
能多地跳过待查文本串中的字符，从而不需要匹配目标文本串的每个字符，而在比较次数最
少的情况下，能一次性无须回溯的实现对文本的快速搜索。实验证明在模式串较长和较短的
情况下，算法都能有效地改善关键字检测过滤系统的匹配性能。
关键词：多模式串匹配；有限自动机；关键字检测过滤；匹配
中图分类号：TP301

引言

在信息检索领域,串匹配问题一直都是研究的焦点之一。在拼写检查、基于字典的语言翻
译、WWW搜索引擎、计算机病毒特征码匹配、数据压缩以及DNA序列匹配等应用中也都
需要进行串匹配。同时在基于特征匹配的入侵检测系统中，模式匹配的效率直接决定这类入
侵检测系统的性能[2][6]。因此字符串匹配速度的提高有着深渊的意义。当前的多模式速度是
很多系统以及软件的瓶颈[3][5]。

对于单模式匹配问题,有三种经典的匹配算法:①KMP算法,它在最坏情况下也能保持线
性查找过程,其时间复杂度为Om(+n)[1][5]，②BM算法,它采用“跳跃式”查找策略,多数情
况下无须对文本进行一次完整的扫描,在模式中字符在文本中出现很少时时间复杂度能到最
好的On(/m),平均情况下其时间复杂度为Om(+n)[4][5][6][8]。③QS算法，在那些待匹配模式集
中未使用的字符在文本T中大量出现时,可以利用它们的信息加快匹配速度。在最优情况下
(模式串较短、模式串中出现的字母数较少)比BM算法更快,其时间复杂度为On(/m)，最坏
[5]
情况时为On(×m)。目前的多模式匹配中没有一个很好的算法能结合以上各个单模式的优
点，本文在充分分析各个单模式匹配算法的基础上提出了一个新的多模式匹配的算法。该算
法结合了Boyer_Moore(BM)算法从右向左跳跃的思想[8]，以及能实现最大跳跃和尽可能少的
比较次数的QuickSearch(QS)算法的优点，能充分利用每次匹配过程中匹配不成功的信息
和已经成功的信息，尽可能多地跳过待查文本串中的字符，从而不需要匹配目标文本串的
每个字符，而在比较次数最少的情况下，就能一次性无须回溯的实现对文本的快速搜索。

1.新算法设计
设待查找文本为T[1,2,""n],其定义在一个有限的字母表∑(本文处理背景选择处理ANSI
字符集0""256)上。多模式匹配则是从文本T中一次查找多个模式串

PPP123,,,""Ppatten_num（这里patten_num代表模式串的数目）,最短模式串的长度用minlen
表示。算法设计的主要思想在于匹配不成功后充分挖掘已经成功匹配的信息结合当前匹配失

-1-
http://www.paper.edu.cn

败信息得到向后跳跃的距离t_shift[]。整个算法可以分为预处理和搜索两个部分。

1.1预处理阶段
1.1.1构建模式匹配自动机，即构建状态转移函数state_shift[][],输出函数output[]记录该
状态下匹配成功的模式串下标，matched[state]记录当前状态state时已经匹配的字符串。
构建多模式匹配自动机，也就是构建多模式下的搜索树。首先用待搜索的模式集构建一
棵搜索树，然后将树的节点作为自动机的状态，树的分支作为自动机的状态转换函数。当
字符在整个搜索树内进行匹配时，由于搜索树是预先知道的，故可用AC算法预先构造一
个包含所有模式信息的反向树型有限自动机。然后再利用BM算法，在文本中用搜索树对
文本进行跳跃式的搜索。在构建搜索树时，将模式串的右边对齐，从右向左进行构建，树
上相同的分支节点进行合并。这样匹配窗内文本最右面的字符就不需要和搜索树中的每一
个字符进行匹配，而是直接将这个字符输入到匹配自动机，得到搜索树的匹配输出。在反
向有限自动机的构造中，每个模式串的字符是从后向前输入到反向树型有限自动机的；匹
配过程中，目标串的输入也是从后向前进行逆向扫描的。为方便描述本文的有限自动机是
通过二维矩阵state_shift[MAXSTATE][M1]来表示的，其中MAXSTATE事先定义，代表最
大可能状态数，M1代表模式匹配的文本集合总数（本文限制在0~256之间）。
以添加li，sheng，cai为例，介绍反向树的构造过程（如图1）

-{i}

0i1l2
Step1添加li

Step2添加sheng

图1: