一种有效的多模式并行匹配算法

摘要：本文给出了一种新的基于模式树构造的多模式并行匹配算法，算法高效简单且实现了匹配的并行化，特别适合于信息检索，模式识别，入侵检测等的方面的多关键字查找。对比分析表明，新算法有较大的移动步长，能够有效减少了实际匹配的规模，使时间和资源消耗均得到了降低，提高了查找速度。

关键词：多模式匹配；模式树；坏字符；并行匹配

中图分类号：TP301文献标识码：A文章编号：1009-3044(2007)05-11373-03

1 引言

对于信息检索，模式识别，入侵检测等领域而言，模式匹配是这些领域中的基本支撑技术。无论是计算机信息处理中的信息查询，还是入侵检测技术中的入侵特征匹配，以及“防火墙”中的规则匹配等，匹配算法的好坏都直接影响到这些技术的性能。因此，研究高效的模式匹配算法，提高搜索速度，对这些技术的发展都有着十分重要的意义。

2 主要模式匹配算法的分析

模式匹配算法的目的即是在目标文本(Text)中查找出所给模式（Pattern）的出现位置。根据待查找模式数量的不同，模式匹配又可分为单模式匹配和多模式匹配。各种匹配算法在匹配的方法上也是各有千秋。

在进行算法的分析之前，首先做出如下约定：

(1)在单模式匹配下，P表示匹配的模式，模式P的长度为m，第i个元素表示为P[i]，P中m个元素依次表示为P[1..m]；在多模式匹配下，P表示模式集合即P={P1…Pk}，k为模式集合大小，|Pi|表示第i个模式的长度，模式Pi的第j个元素表示为Pi[j]，其|Pi|个元素

依次表示为Pi[1.. |Pi|]。

(2)T表示目标文本(Text)，文本T的长度为n，第i个元素表示为T[i]，T中m个元素依次表示为T[1..m]。

(3)P，T的元素都属于有限字母表∑。

(4)对于位移量s（1≤s≤n-m），若满足T[s+1..s+m]=P[1..m]，则模式P在T中出现且位置为s。

2.1 BM 算法

BM 算法是一个著名的单模式匹配算法，由Boyer和Moore提出。BM 算法最大的特点是匹配从左向右进行，当不匹配情况发生时，利用坏字符启发性方法（Bad-Character Function）和好后缀启发性方法（Good-Suffix Function）各自提供一个位移量，选取两种启发性方法中位移量最大的作为模式的实际位移。

在图1-a中，当字符发生不匹配时，对坏字符‘i’利用坏字符启发性方法，找到模式中字符‘i’的下一个出现位置，得到参考位移值为s+4，如图1-b所示。对好后缀‘ce’利用好后缀启发性方法，找到后缀‘ce’在模式中的下一个最右出现位置，得到参考位移值为s+3，如图1-c所示。结合两种启发性方法，模式实际位移值为s+4，然后又从右到左依次比较对应字符，进行下一轮匹配。

图1 BM 算法中的启发式移动

BM 算法的两种启发性方法的预处理时间为O（2*m+|∑|），在匹配查找过程中，通常情况下所用时间为O（n+r*m），r为Pattern在Text中的出现次数，最坏情况则为O（m*n）。实际应用中，当模式P较长，字母表∑相对较大时，BM 算法能够有效地跳过大量字符具有很高匹配效率。

2.2 AC_BM 算法

AC_BM 算法是AC（Aho-Corasick）算法与BM（Boyer-Moore）的结合算法，由Commentz-Walter首先提出。其中AC算法是同时搜索多个Pattern的经典算法，它运用有限自动机来处理模式集合中的所有字符，构造出模式集中字符的状态转换关系，并借助有限自动机的状态转换机制，一次性查找出多个Pattern的出现位置。AC_BM 算法将BM算法的启发性搜索技术与基于模式集搜索的AC算法有机地集合起来，实现了多个Pattern的跳跃式匹配。

AC_BM 算法的主要思想是：先将模式集中具有相同前缀的不同Pattern组织成一棵模式树，也叫前缀树，图2所示即为模式集合{that，those，team，teach，tested}所构造的模式树。

图2 AC_BM 算法中构造的模式树

然后将模式树从Text的最右边开始向左移动，一旦模式树确定在某个适当的位置时，字符的匹配比较则从左向右执行。在出现不匹配时，AC_BM 算法运用了类似于BM算法的如下两种启发性方法：

(1)坏字符启发性方法（Bad-Character Function）

在目标文本与模式树发生不匹配时，假设目标文本中的失配字符为‘x’，若‘x’不在模式树中，则整个模式树向左移动Lmin（Lmin为最短模式的长度）；若‘x’在模式树中，则将模式树向左移动，使模式树中下次出现的‘x’与目标文本中的‘x’对齐，如果移动距离大于Lmin，则仅移动Lmin位。

(2)好前缀启发性方法（Good-Prefix Function）

当模式树与目标文本已匹配部分字符时发生不匹配，若已匹配字符串为模式树中某个模式的子串，则将整个模式树向左移至模式树中子串与目标文本子串对齐的位置，如果移动距离大于Lmin，则仅移动Lmin。

AC_BM 算法在移动中，同时利用上述两种启发性方法，选取两者中的最大值作为模式树的实际移动距离，模式树的移动受最短模式长度Lmin的限制。在一般情况下，AC_BM 算法在匹配过程中的时间复杂度为O（n+ k*Lavg）（Lavg为模式的平均长度）。

3 新的多模式并行匹配算法

一般情况下，在海量的数据中所要查找的关键字只是数据中很少的一部分，这就意味着在待搜索的数据中有大量的坏字符。

基于上述事实，可以在进行实际的匹配前，以坏字符为切割点（其中作为切割点的坏字符不同于BM算法中所指的坏字符，而是指模式集中没有的字符），将模式可能出现的那些子串从目标文本中分割出来，过滤掉不可能匹配的无关数据，减小实际匹配的规模。

在进行实际的匹配时，由于目标文本被分割成多个子串，在这种情况下，模式的可能出现次数很少且不存在较多的坏字符，AC_BM算法的所采用的启发性方法发挥作用不大，而且较难实现又消耗预处理时间，因此，需要针对这一特点改进模式树的移动方法。

新算法的基本思想是：在预处理中，将模式集合以模式树的方式进行组织，利用坏字符作为分割点将目标文本分割为若干子串，同时过滤掉大量无关字符串；匹配过程中，利用模式树中字符最早出现函数作为模式树移动的启发性方法，达到模式树的快速移动和并行匹配。

3.1 算法的实现

3.1.1 模式集字符的最早出现函数λ的计算

函数λ记录模式树中每个字符的最早出现位置，其定义为：对任意字符‘x’，若‘x’在模式树中出现，则λ[x]=min{j | Pi[j]=x,1≤i≤k,1≤j≤| Pi |}；若‘x’不在模式树中，则令λ[x]=M（M为某个长度超过所有模式长度的常数）。计算函数λ的伪代码如下：

First-Occurrence-Function ( P, k,∑)

(1)for 每个字符 x∈∑

(2)do λ[x]M //初始化函数λ

(3)for i1 to k

(4)do for j| Pi | to 1//从模式最后的字符开始搜索

(5)do if j

(6)then λ[Pi[j]]j //当模式集中某个模式的字符有更早出现位置时，更新函数λ的值

(7)return λ

λ函数的作用是：一方面判断坏字符，作为目标文本分割的依据；另一方面存放模式树中字符的最早出现位置，实现模式树的启发性移动。利用上述λ函数的计算过程，可得到图2中的模式树各字符的最早出现函数值如下表1所示。

表1 模式树中字符的λ函数值

3.1.2 改进的模式树启发式移动方法

改进方法在模式树的移动上，使用有别于AC_BM算法的启发性移动方法，即当字符不匹配发生时，不是利用失配位置的字符或已匹配的子串作启发式移动，而是考虑目标文本中模式树树根对应位置的前一字符，利用该字符的λ函数值来决定模式树的下一步移动。匹配过程具体实现伪代码如下：

Patten-Matching-Function (T, P, λ)

(1) head Length(T)- Lmin+1, i head, j1

//head为模式树的根指针，i，j分别为目标

(2) while head>0//文本和模式的匹配指针。

(3)do if T[i]与Pt[j]匹配 and j≤Lmax

// Lmax为模式的最大长度，t∈（1,k）。

(4)then i++ , j++

(5)if 某个模式出现

(6)then Print 出现位置head

(7)else if λ[T[head-1]]≤Lmin // Lmin为模式的最小长度。

(8)then headhead-λ[T[head-1]]

//利用最早出现函数λ并结合Lmin值

(9) else headhead- Lmin-1//进行模式树的移动。

(10)ihead, j1

新算法的启发式移动方法比AC_BM算法更简单有效，减少了计算量，且易于实现，由于是利用目标文本中模式树树根对应位置的前一字符来决定模式树的移动，因此模式树的最大跳跃步长可达Lmin+1，比AC_BM算法的模式树移动更快。

3.1.3 目标文本的分割

以坏字符分割目标文本的过程中，利用BeginPoint和EndPoint作为标示分割子串位置的指针，s表示指针的跳跃步长，在进行多模式匹配的情况下，s为最短模式的长度。初始状态时，BeginPoint和EndPoint都指向一个空位置，然后EndPoint以步长s向右进行一次跳跃，并判断跳跃处字符的λ函数值。分下面两种情况移动BeginPoint和EndPoint指针：(1)若λ函数值为M，说明字符不在模式集中，则该段字符串直接跳过；(2)若λ函数值小于M，则字符在模式集中出现，则EndPoint向右逐个移动直至所指字符的λ函数值为M。BeginPoint和EndPoint以上述方式跳跃直至目标文本末尾。在移动过程中，将模式可能出现的子串的首尾位置标记放入一个队列中，实现对目标文本的分割，等待下一步匹配的处理。分割过程的伪代码实现为：

Text-Cut-Function(T, λ, s)

(1)BeginPoint 0, EndPoint 0

(2)while EndPoint ≤ Length(T)

(3)do EndPoint EndPoint+s

(4)if λ[T[EndPoint]] = M

(5)then BeginPoint EndPoint

(6)else while λ[T[EndPoint]] ≠M and EndPoint < Length(T)

(7)do EndPoint EndPoint+1 //移动EndPoint指针，直至遇到坏字符。

(8)BeginPoint，EndPoint进入队列CutQueue

(9)BeginPoint EndPoint

(10) return CutQueue

在上述的分割处理过程中，返回了一个队列CutQueue，在CutQueue中每两个元素构成了一个对目标文本的分割。

3.1.4 模式匹配的并行化

目标文本被分割的子串位置放入CutQueue队列中后，便可以对CutQueue队列进行操作，将子串的对应起始位置从CutQueue队列中取出，分别进行模式的匹配。

经过上述处理后，可以很容易地利用不同的并行机制实现匹配的并行化。目标文本的分割和对子串的匹配也可以同时协调进行，在此种方式下，匹配速度将进一步加快。

3.2 新算法的性能分析及测试

(1)算法的性能分析

最早出现函数λ的计算由模式集P和字母表∑的规模决定，其时间复杂度为O（|P|+|∑|）。目标文本的分割只涉及对最早出现函数λ进行相应数值的比较操作，因此分割时间极快，在最好的情况下所用时间为O（n/Lmin），最坏情况下为O（n），整个算法的预处理时为O（|P| +|∑|+n）。

匹配过程中，结合分割后的子串的特点，改进的启发式移动方法利用字符的最早出现函数不仅简单高效，且具有优于AC_BM算法的平均跳跃步长。一般情况下，单次匹配中所需时间为O（lavg+ k*（Lavg－1））（其中Lavg为模式的平均长度，k为模式数量，lavg为待匹配子串的平均长度），在最坏情况下为O（k*（Lavg－1）* lavg）。

假设有t台处理机并行地执行匹配任务的情况下，匹配过程所需时间为O（（r*lavg+ k*（Lavg－1））/t），最坏情况下为O（k*r*lavg*（Lavg－1）/t），因此，借助并行处理技术，模式的匹配速度会更快。

(2)测试比较

随机生成约176M的文本数据，分别用AC_BM算法和新的并行匹配算法对不同大小的模式集合匹配目标文本，其中并行匹配利用MPI机制实现，采用两个处理进程模拟匹配的并行化。

表2 算法匹配时间对比（单位：秒）

对比结果中，新的并行匹配算法在匹配处理时间上约为AC_BM算法的50%，进一步分析可知，坏字符越多，目标文本的分割越均匀，并行匹配的效率就越高。

4 总结

在实际情况中，待检测的数据中坏字符出现频率很高，若假设目标文本中坏字符出现频率为ν，且在目标文本呈均匀分布，可以得出lavg和r满足如下条件：(1)m≤lavg＜1/ν；(2)r≤min{n*ν+1,n/Lmin}。由此可见，当坏字符的出现频率ν较高时，新算法可以将目标文本快速有效地分割成相对较小的子串，使得实际的匹配规模降低；此外，在模式树的启发式移动方法上，新算法实现简单且具有较大的移动步长，减少了系统的资源消耗和匹配时间。总的而言，新算法在实际应用中具有很好的平均性能。

参考文献：

[1]Gusfield D.Algorithms on Strings,Trees,and Sequences:Computer Science and Computational Biology[M].University of California Press,CA,1997.

[2]Boyer R S, Moore J S. A fast searching algorithm [J].Communication of the ACM, 1977, 20(10):762-772.

[3]Commentz-Walter B. A String Matching Algorithm Fast on the Average. Proc. 6th International Colloquium on Automata, Languages,and Programming,1979.

[4]Baeza-Yates R A. Improved String Searching. Software-Practice and Experience 19, 1989.

[5]潘金贵,顾铁成,曾俭,滕远方,等. 现代计算机常用算法及数据结构[M].南京：南京大学出版社,1994.

[6]李雪莹,刘宝旭,许榕生.等.字符串匹配技术研究[J].计算机工程,2004,30(22):24-26.

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。