论文部分内容阅读
摘要：模式匹配算法是入侵防御系统中检测引擎的核心算法，模式匹配算法的效率决定了入侵防御系统的性能。本文对模式匹配算法进行了研究，重点分析了多模式匹配算法Wu-Manber算法，并针对Wu-Manber算法存在的不足，提出了Wu-Manber算法的改进算法。
关键词：入侵防御系统；多模式匹配；Wu-Manber算法
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)12-2pppp-0c
Research on Wu-Manber Algorithm for Intrusion Detection
(1.Department of Computer Science and Technology,Huaihua University,Huaihua 418008,China；2.School of Software .uestc,Chengdu 610054,China)
Abstract:Pattern matching algorithm is one of the core algorithms in the detection engine of the intrusion prevention system. Efficiency of the intrusion prevention system is determined by pattern matching algorithm. A survey of the pattern matching algorithm is described in this thesis. The Wu-Manber algorithm which is one of the multi-pattern matching algorithm is explained in detail, and the improvement of the the Wu-Manber algorithm is presented to improve the efficiency.
Key words:intrusion prevention system; multi-pattern matching; Wu-Manber algorithm
网络入侵检测系统(NIDS)作为提高网络系统安全性的重要技术之一,已经得到了广泛应用。典型的NIDS是用一系列的规则(特征)来描述已知的攻击行为。一条规则包含了一个或多个用以识别某种攻击行为的模式串[1]。随着网络速度和入侵检测规则的持续增长,模式匹配正在成为网络入侵检测系统的性能瓶颈。因此有必要对现有的多模式匹配算法进行改进，提高检测速度。
本文对多模式匹配算法Wu-Manber算法进行了研究，针对Wu-Manber算法存在的不足，提出了Wu-Manber算法的改进算法。通过实验证明了改进算法相对于原算法具有较高的性能。
1 Wu-Manber算法
Wu-Manber算法是BM算法的扩展算法，是一种实用的多模式匹配算法。它的主要特点是采用了BM算法的不良字符转移机制,利用块字符扩展了不良字符转移的效果,同时使用散列表来筛选匹配阶段应进行匹配的模式串,减少匹配计算量。Wu-Manber算法的执行时间不会随着模式集的增加而成比例增长，而且要远少于使用每一个模式串和BM算法对文本进行匹配的时间总和[2]。Wu-Manber算法是应用中平均性能最好的一个算法。
在介绍Wu-Manber算法前首先定义以下一些变量：
包含r个模式的模式集 P={p1,p2,…pr}；
文本串T=t1t2…tn；
B:块字符长度；
m:模式集中最短模式串的长度；
n：文本长度；
hash：块字符散列函数；
|P|：模式集中模式数量；
∑：字符集。
Wu-Manber算法采用了跳跃不可能匹配字符的策略和hash散列的方法,以加速匹配的进行。算法需要对所有模式进行预处理,预处理需构建SHIFT,HASH 和PREFIX 3个表。SHIFT表用于在扫描文本串的时候,根据读入字符串决定可以跳过的字符数。HASH表用来存放指针，此指针指向后缀散列值相同的所有模式串的模式串链表。PREFIX表存储每个模式串的前B个字符的字符块的散列值。扫描时如果SHIFT表中相应的跳跃值为0,则说明可能产生匹配,就要用到HASH表和PREFIX表做进一步判断,找出有哪些匹配候选模式串,并验证是哪个或者哪些候选模式与文本完全匹配[3]。
1.1 算法预处理
(1)首先计算模式集P中最小模式串的长度m，并且只考虑每个模式串的前m个字符，即要求所有的模式串有相同的长度m。
(2)以长度为B的块字符作为比较的基本单位，而不是以单个字符作为比较的基本单位。B的取值为log∑(2*m*r),通常B的值为2或3。
(3)构建SHIFT表：SHIFT表中存储字符集中所有快字符在文本中出现时的转移距离。假设S是当前正在处理的字符集中长度为B个字符的字符块，计算其散列值为h，作为SHIFT表的索引。如果字符块S不出现在任何模式串中，则在SHIFT[h]中存放m-B 1。如果S在某些模式串中出现，查看模式串中S出现的最右位置。假设S在pi中的q位出现，并且在其他模式串中出现S的位置都不大于q。那么在SHIFT[h]中存放m-q。
(4)构建HASH表：计算每个模式串的后B个字符的字符块的散列值h，后B个字符散列值相同的所有模式串组成一个模式串链表。在HASH[h]中存放指向此链表的指针。
(5)构建PREFIX表：存储每个模式串的前B个字符的字符块的散列值[4]。
1.2 算法扫描
匹配从文本的第m个字符开始，对模式的匹配从右向左进行，每次扫描B个字符：
(1)对文本中的当前长度为B的块字符计算其hash值h。
(2)检查SHIFT[h]是否为0。如果大于0，移动文本并返回(1),否则进入第(3)步。
(3)计算当前文本窗口的前缀hash值，记为text_prefix。
(4)检查满足HASH[h]≤p
2 改进的Wu-Manber算法
2.1 Wu-ManberM算法的不足
假如文本串T为：“Natural language texts are not random”；
模式串为：texts、language、maxts和boxts；
HASH表和PREFIX表如图1和图2所示。
HASH表第一项中的指针p1指向了具有三个元素的模式串链表。
当匹配过程进行到第6步时，即SHIFT（hash(ts)）=0。计算文本窗口的B个字符前缀的hash值text_prefix，并转入HASH表。此时HASH表所对应的项存储的是指向以ts为尾块的模式串链表的指针。需查找PREFIX表，对模式串链表的每一项考察其前缀hash值是否与text_prefix相等[5]。
本例中对于此种情况需进行三次比较。从上面的实例可以总结出Wu-Manber算法具有这样的不足：随着模式串的增加，多个模式串拥有相同后缀的情况也会增加，即所构建的HASH表相应表项内的指针所指向的模式串链表长度增加，从而增加查找PREFIX表的次数，并导致PREFIX表内容和当前文本窗口的前缀hash值比较次数。这样必然使匹配过程需要更多的比较次数，影响算法性能。
2.2 改进算法的设计思想
根据上面讨论的Wu-Manber算法中存在的不足，提出算法改进思想：
(1)修改HASH表的结构，使它不再以模式串的后缀hash值作为入口。在算法的预处理阶段，对每个模式串计算其前缀和后缀所组成字符块的hash值，以此作为HASH表的入口。
因为通常情况下不同的模式串，同时具有相同的后缀和前缀的情况非常少，因而这样处理可以减少HASH表中指向的模式链表的模式串数量，从而减少文本窗口前缀hash值和PREFIX表项的比较次数，提高算法匹配效率。
(2)由于将每个模式串的前缀和后缀组成的字符块hash值作为HASH表的入口，即将模式串的前缀信息加入到了HASH表中，而原算法中PREFIX表中存储的正是模式串前缀hash值，在这种情况下PREFIX表与HASH表功能发生了冲突，因而在改进的Wu-Manber算法中取消PREFIX表的构建。
2.3 改进算法的设计
(1)算法预处理阶段
①首先计算模式集P中最小模式串的长度m。并且只考虑每个模式串的前m个字符。即要求所有的模式串具有相同的长度m。
②确定B的值，B的值取2或3。
③构建SHIFT表：与Wu-Manber算法的SHIFT表构建方法相同。
④构建HASH表：计算每个模式串的后B个字符和前B个字符组成的字符块的散列值h1，散列值相同的所有模式串组成一个模式串链表。在HASH[h1]中存放指向此链表的指针。
(2)扫描阶段
匹配从文本的第m个字符开始，对模式的匹配从右向左进行，每次扫描B个字符：
①对文本中的当前长度为B的块字符计算其hash值。
②检查SHIFT[h]是否为0。如果大于0，移动文本并返回(1),否则进入第③步。
③计算当前文本窗口的前缀，并与后缀组成新的块字符，并计算其hash值，记为h1。
④检查满足HASH[h1]项是否为存在。如过存在，即HASH[h1]=p，则将p指向的模式链表中的每个模式串和当前文本比较。如匹配，将其记录。文本窗口后移一位，返回第①步，直到比较结束。如HASH[h1]项不存在，说明没有模式串满足这样的条件，返回第①步，直到比较结束。
2.4 改进的Wu-Manber算法描述
while (text <= textend) {
h=hashBlock(text) /*计算当前文本块hash值*/
shift=SHIFT[h]; /*查看跳跃距离*/
if(shift==0){
h1=hashBlock(text text_prefix); /*计算文本前缀和后缀组成
的字符块的hash值*/
p=HASH[h1];/*得到可能与当前文本匹配
的模式串链表入口*/
while(p){
进行完全匹配。如发现匹配，报告结果
}
shift=1;
}
text = shift;
}
2.5 改进的Wu-Manber算法实例
文本串T为：“Natural language texts are not random”；
模式串为：texts、language、maxts和boxts；
最短模式长度：m=5。
(1)计算SHIFT表
这里取B=2。
计算每个块字符的散列值和块字符与模式串串尾的距离。此即为当该字符块在文本中出现时的跳转距离，参见表1。
(3)匹配过程
①Natural language texts are not random
pos = 5,B = 2,所以tpos-B 1…tpos即为t4t5 = ur
SHIFT(hash(ur))=4 不等于0，下次开始搜寻Text的位置pos = 5 4=9
②Natural language texts are not random
pos = 9,B = 2,所以tpos-B 1…tpos即为t8t9 =l
SHIFT(hash( l))=4不等于0，下次开始搜寻Text的位置pos = 9 4=13
③Natural language texts are not random
pos = 13,B = 2,所以tpos-B 1…tpos即为t12t13 = gu
SHIFT(hash(gu))=0,h1=hash(lagu)=13,HASH(13)=p2,比较language与Text。发现相等,标记language出现过。pos=pos 1=14
④Natural language texts are not random
pos = 14,B = 2,所以tpos-B 1…tpos即为t13t14 = ua
SHIFT(hash(ua))=4不等于0，所以下次开始搜寻Text的位置pos = 14 4=18
⑤Natural language texts are not random
pos = 18,B = 2,所以tpos-B 1…tpos即为t17t18 =t
SHIFT(hash( t))=4不等于0，下次开始搜寻Text的位置pos = 18 4=22
⑥Natural language texts are not random
pos = 22,B = 2,所以tpos-B 1…tpos即为t21t22 = ts
SHIFT(hash(ts))=0,h1=hash(tets)=13,HASH(13))=p1,比较texts与Text。发现相等,标记texts出现过。pos=pos 1=23
⑦Natural language texts are random
pos = 23,B = 2,所以tpos-B 1…tpos即为t22t23 = s
SHIFT(hash(s ))=4不等于0，下次开始搜寻Text的位置pos = 23 4=27
⑧Natural language texts are random
pos = 27,B = 2,所以tpos-B 1…tpos即为t26t27 = e
SHIFT(hash(e ))=4不等于0，下次开始搜寻Text的位置pos = 27 4=31
⑨Natural language texts are random
pos = 31,B = 2,所以tpos-B 1…tpos即为t30t31 = nd
SHIFT(hash(nd))=4不等于0，下次开始搜寻Text的位置pos = 31 4=35
⑩ pos > length(Text)，匹配结束。
与未改进的Wu-Manber算法相比，可以看到改进的Wu-Manber算法在匹配过程中的第6步，减少了3次比较次数。
2.6 改进的Wu-Manber算法分析
(1)改进的Wu-Manber算法与原算法相比的不同之处：
①减少了当多个模式串具有相同后缀的情况下的比较次数。
②省去了PREFIX表的构建，节省了算法预处理时间和空间内存的使用。
(2)改进的Wu-Manber算法性能分析和测试
表3中的WM表示Wu-Manber算法，LWM表示改进的Wu-Manber算法。
②算法分析
从图4—8可以看出，随着模式串数量的增加，两种算法在特定模式长度的情况下扫描时间都相应增大，改进的WM算法的扫描时间一直小于WM算法所用时间。随着模式串长度的增加，两种算法在特定模式串数量的情况下，扫描时间都相应减小，改进的WM算法扫描所用时间一直小于WM算法所用时间，但差距在逐渐缩小。
从表3可以看出，两算法字符比对次数的比较类似于两算法所用时间的比较。
产生这种实验结果的原因是随着模式串个数的增加，具有相同后缀的模式串不断增多，当模式串较短时，算法的平均跳跃距离比较短，因而此时WM算法所用时间和改进的WM算法所用时间差距巨大。而随着模式串长度的增加，两种算法的平均跳跃距离也在增大，虽然WM算法中具有相同后缀的模式串同样很多，但随着跳跃距离的增大，WM算法所用时间也急剧减小，与改进的WM算法的差距也不断缩小。
从实验结果可以看出，改进后的算法性能不论在哪种情况下都比原算法有较大提高，达到了预期效果。
3 结束语
本章重点分析了经典的多模式匹配算法Wu-Manber算法，针对Wu-Manber算法在多个模式串具有相同后缀的情况下，算法效率较低的问题进行了改进，提出了改进算法的设计思想、原理，并对其进行了详细的描述，最后通过程序仿真，证明了改进后的算法性能优于原算法性能。
参考文献：
[1]谢希仁.计算机网络(第4版).北京:电子工业出版社,2005.
[2]杨东红,徐恪,崔勇.改进的Wu-Manber多模式匹配算法.清华大学学报.
[3]张鑫,谭建龙,程学旗. 一种改进的Wu-Manber多关键词匹配算法[J].计算机应用, 2003.
[4]孙晓山,王强,关毅,王晓龙. 一种改进的Wu-Manber多模式匹配算法及应用.中文信息学报.
[5]WU Sun,Manber U.A Fast Algorithm for Multi-Pattern Searching. Technical Report TR 94-17,University of Arizona at Tuscon, 1994.
收稿日期：2008-01-25
作者简介：王灿明（1980-），男，湖南涟源人，怀化学院计算机系，助教，硕士，主要研究网络信息安全，RFID技术；肖峰（1983-），男，四川成都人，电子科技大学，在读硕士，主要研究网络信息安全。
关键词：入侵防御系统；多模式匹配；Wu-Manber算法
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)12-2pppp-0c
Research on Wu-Manber Algorithm for Intrusion Detection
(1.Department of Computer Science and Technology,Huaihua University,Huaihua 418008,China；2.School of Software .uestc,Chengdu 610054,China)
Abstract:Pattern matching algorithm is one of the core algorithms in the detection engine of the intrusion prevention system. Efficiency of the intrusion prevention system is determined by pattern matching algorithm. A survey of the pattern matching algorithm is described in this thesis. The Wu-Manber algorithm which is one of the multi-pattern matching algorithm is explained in detail, and the improvement of the the Wu-Manber algorithm is presented to improve the efficiency.
Key words:intrusion prevention system; multi-pattern matching; Wu-Manber algorithm
网络入侵检测系统(NIDS)作为提高网络系统安全性的重要技术之一,已经得到了广泛应用。典型的NIDS是用一系列的规则(特征)来描述已知的攻击行为。一条规则包含了一个或多个用以识别某种攻击行为的模式串[1]。随着网络速度和入侵检测规则的持续增长,模式匹配正在成为网络入侵检测系统的性能瓶颈。因此有必要对现有的多模式匹配算法进行改进，提高检测速度。
本文对多模式匹配算法Wu-Manber算法进行了研究，针对Wu-Manber算法存在的不足，提出了Wu-Manber算法的改进算法。通过实验证明了改进算法相对于原算法具有较高的性能。
1 Wu-Manber算法
Wu-Manber算法是BM算法的扩展算法，是一种实用的多模式匹配算法。它的主要特点是采用了BM算法的不良字符转移机制,利用块字符扩展了不良字符转移的效果,同时使用散列表来筛选匹配阶段应进行匹配的模式串,减少匹配计算量。Wu-Manber算法的执行时间不会随着模式集的增加而成比例增长，而且要远少于使用每一个模式串和BM算法对文本进行匹配的时间总和[2]。Wu-Manber算法是应用中平均性能最好的一个算法。
在介绍Wu-Manber算法前首先定义以下一些变量：
包含r个模式的模式集 P={p1,p2,…pr}；
文本串T=t1t2…tn；
B:块字符长度；
m:模式集中最短模式串的长度；
n：文本长度；
hash：块字符散列函数；
|P|：模式集中模式数量；
∑：字符集。
Wu-Manber算法采用了跳跃不可能匹配字符的策略和hash散列的方法,以加速匹配的进行。算法需要对所有模式进行预处理,预处理需构建SHIFT,HASH 和PREFIX 3个表。SHIFT表用于在扫描文本串的时候,根据读入字符串决定可以跳过的字符数。HASH表用来存放指针，此指针指向后缀散列值相同的所有模式串的模式串链表。PREFIX表存储每个模式串的前B个字符的字符块的散列值。扫描时如果SHIFT表中相应的跳跃值为0,则说明可能产生匹配,就要用到HASH表和PREFIX表做进一步判断,找出有哪些匹配候选模式串,并验证是哪个或者哪些候选模式与文本完全匹配[3]。
1.1 算法预处理
(1)首先计算模式集P中最小模式串的长度m，并且只考虑每个模式串的前m个字符，即要求所有的模式串有相同的长度m。
(2)以长度为B的块字符作为比较的基本单位，而不是以单个字符作为比较的基本单位。B的取值为log∑(2*m*r),通常B的值为2或3。
(3)构建SHIFT表：SHIFT表中存储字符集中所有快字符在文本中出现时的转移距离。假设S是当前正在处理的字符集中长度为B个字符的字符块，计算其散列值为h，作为SHIFT表的索引。如果字符块S不出现在任何模式串中，则在SHIFT[h]中存放m-B 1。如果S在某些模式串中出现，查看模式串中S出现的最右位置。假设S在pi中的q位出现，并且在其他模式串中出现S的位置都不大于q。那么在SHIFT[h]中存放m-q。
(4)构建HASH表：计算每个模式串的后B个字符的字符块的散列值h，后B个字符散列值相同的所有模式串组成一个模式串链表。在HASH[h]中存放指向此链表的指针。
(5)构建PREFIX表：存储每个模式串的前B个字符的字符块的散列值[4]。
1.2 算法扫描
匹配从文本的第m个字符开始，对模式的匹配从右向左进行，每次扫描B个字符：
(1)对文本中的当前长度为B的块字符计算其hash值h。
(2)检查SHIFT[h]是否为0。如果大于0，移动文本并返回(1),否则进入第(3)步。
(3)计算当前文本窗口的前缀hash值，记为text_prefix。
(4)检查满足HASH[h]≤p
2 改进的Wu-Manber算法
2.1 Wu-ManberM算法的不足
假如文本串T为：“Natural language texts are not random”；
模式串为：texts、language、maxts和boxts；
HASH表和PREFIX表如图1和图2所示。
HASH表第一项中的指针p1指向了具有三个元素的模式串链表。
当匹配过程进行到第6步时，即SHIFT（hash(ts)）=0。计算文本窗口的B个字符前缀的hash值text_prefix，并转入HASH表。此时HASH表所对应的项存储的是指向以ts为尾块的模式串链表的指针。需查找PREFIX表，对模式串链表的每一项考察其前缀hash值是否与text_prefix相等[5]。
本例中对于此种情况需进行三次比较。从上面的实例可以总结出Wu-Manber算法具有这样的不足：随着模式串的增加，多个模式串拥有相同后缀的情况也会增加，即所构建的HASH表相应表项内的指针所指向的模式串链表长度增加，从而增加查找PREFIX表的次数，并导致PREFIX表内容和当前文本窗口的前缀hash值比较次数。这样必然使匹配过程需要更多的比较次数，影响算法性能。
2.2 改进算法的设计思想
根据上面讨论的Wu-Manber算法中存在的不足，提出算法改进思想：
(1)修改HASH表的结构，使它不再以模式串的后缀hash值作为入口。在算法的预处理阶段，对每个模式串计算其前缀和后缀所组成字符块的hash值，以此作为HASH表的入口。
因为通常情况下不同的模式串，同时具有相同的后缀和前缀的情况非常少，因而这样处理可以减少HASH表中指向的模式链表的模式串数量，从而减少文本窗口前缀hash值和PREFIX表项的比较次数，提高算法匹配效率。
(2)由于将每个模式串的前缀和后缀组成的字符块hash值作为HASH表的入口，即将模式串的前缀信息加入到了HASH表中，而原算法中PREFIX表中存储的正是模式串前缀hash值，在这种情况下PREFIX表与HASH表功能发生了冲突，因而在改进的Wu-Manber算法中取消PREFIX表的构建。
2.3 改进算法的设计
(1)算法预处理阶段
①首先计算模式集P中最小模式串的长度m。并且只考虑每个模式串的前m个字符。即要求所有的模式串具有相同的长度m。
②确定B的值，B的值取2或3。
③构建SHIFT表：与Wu-Manber算法的SHIFT表构建方法相同。
④构建HASH表：计算每个模式串的后B个字符和前B个字符组成的字符块的散列值h1，散列值相同的所有模式串组成一个模式串链表。在HASH[h1]中存放指向此链表的指针。
(2)扫描阶段
匹配从文本的第m个字符开始，对模式的匹配从右向左进行，每次扫描B个字符：
①对文本中的当前长度为B的块字符计算其hash值。
②检查SHIFT[h]是否为0。如果大于0，移动文本并返回(1),否则进入第③步。
③计算当前文本窗口的前缀，并与后缀组成新的块字符，并计算其hash值，记为h1。
④检查满足HASH[h1]项是否为存在。如过存在，即HASH[h1]=p，则将p指向的模式链表中的每个模式串和当前文本比较。如匹配，将其记录。文本窗口后移一位，返回第①步，直到比较结束。如HASH[h1]项不存在，说明没有模式串满足这样的条件，返回第①步，直到比较结束。
2.4 改进的Wu-Manber算法描述
while (text <= textend) {
h=hashBlock(text) /*计算当前文本块hash值*/
shift=SHIFT[h]; /*查看跳跃距离*/
if(shift==0){
h1=hashBlock(text text_prefix); /*计算文本前缀和后缀组成
的字符块的hash值*/
p=HASH[h1];/*得到可能与当前文本匹配
的模式串链表入口*/
while(p){
进行完全匹配。如发现匹配，报告结果
}
shift=1;
}
text = shift;
}
2.5 改进的Wu-Manber算法实例
文本串T为：“Natural language texts are not random”；
模式串为：texts、language、maxts和boxts；
最短模式长度：m=5。
(1)计算SHIFT表
这里取B=2。
计算每个块字符的散列值和块字符与模式串串尾的距离。此即为当该字符块在文本中出现时的跳转距离，参见表1。
(3)匹配过程
①Natural language texts are not random
pos = 5,B = 2,所以tpos-B 1…tpos即为t4t5 = ur
SHIFT(hash(ur))=4 不等于0，下次开始搜寻Text的位置pos = 5 4=9
②Natural language texts are not random
pos = 9,B = 2,所以tpos-B 1…tpos即为t8t9 =l
SHIFT(hash( l))=4不等于0，下次开始搜寻Text的位置pos = 9 4=13
③Natural language texts are not random
pos = 13,B = 2,所以tpos-B 1…tpos即为t12t13 = gu
SHIFT(hash(gu))=0,h1=hash(lagu)=13,HASH(13)=p2,比较language与Text。发现相等,标记language出现过。pos=pos 1=14
④Natural language texts are not random
pos = 14,B = 2,所以tpos-B 1…tpos即为t13t14 = ua
SHIFT(hash(ua))=4不等于0，所以下次开始搜寻Text的位置pos = 14 4=18
⑤Natural language texts are not random
pos = 18,B = 2,所以tpos-B 1…tpos即为t17t18 =t
SHIFT(hash( t))=4不等于0，下次开始搜寻Text的位置pos = 18 4=22
⑥Natural language texts are not random
pos = 22,B = 2,所以tpos-B 1…tpos即为t21t22 = ts
SHIFT(hash(ts))=0,h1=hash(tets)=13,HASH(13))=p1,比较texts与Text。发现相等,标记texts出现过。pos=pos 1=23
⑦Natural language texts are random
pos = 23,B = 2,所以tpos-B 1…tpos即为t22t23 = s
SHIFT(hash(s ))=4不等于0，下次开始搜寻Text的位置pos = 23 4=27
⑧Natural language texts are random
pos = 27,B = 2,所以tpos-B 1…tpos即为t26t27 = e
SHIFT(hash(e ))=4不等于0，下次开始搜寻Text的位置pos = 27 4=31
⑨Natural language texts are random
pos = 31,B = 2,所以tpos-B 1…tpos即为t30t31 = nd
SHIFT(hash(nd))=4不等于0，下次开始搜寻Text的位置pos = 31 4=35
⑩ pos > length(Text)，匹配结束。
与未改进的Wu-Manber算法相比，可以看到改进的Wu-Manber算法在匹配过程中的第6步，减少了3次比较次数。
2.6 改进的Wu-Manber算法分析
(1)改进的Wu-Manber算法与原算法相比的不同之处：
①减少了当多个模式串具有相同后缀的情况下的比较次数。
②省去了PREFIX表的构建，节省了算法预处理时间和空间内存的使用。
(2)改进的Wu-Manber算法性能分析和测试
表3中的WM表示Wu-Manber算法，LWM表示改进的Wu-Manber算法。
②算法分析
从图4—8可以看出，随着模式串数量的增加，两种算法在特定模式长度的情况下扫描时间都相应增大，改进的WM算法的扫描时间一直小于WM算法所用时间。随着模式串长度的增加，两种算法在特定模式串数量的情况下，扫描时间都相应减小，改进的WM算法扫描所用时间一直小于WM算法所用时间，但差距在逐渐缩小。
从表3可以看出，两算法字符比对次数的比较类似于两算法所用时间的比较。
产生这种实验结果的原因是随着模式串个数的增加，具有相同后缀的模式串不断增多，当模式串较短时，算法的平均跳跃距离比较短，因而此时WM算法所用时间和改进的WM算法所用时间差距巨大。而随着模式串长度的增加，两种算法的平均跳跃距离也在增大，虽然WM算法中具有相同后缀的模式串同样很多，但随着跳跃距离的增大，WM算法所用时间也急剧减小，与改进的WM算法的差距也不断缩小。
从实验结果可以看出，改进后的算法性能不论在哪种情况下都比原算法有较大提高，达到了预期效果。
3 结束语
本章重点分析了经典的多模式匹配算法Wu-Manber算法，针对Wu-Manber算法在多个模式串具有相同后缀的情况下，算法效率较低的问题进行了改进，提出了改进算法的设计思想、原理，并对其进行了详细的描述，最后通过程序仿真，证明了改进后的算法性能优于原算法性能。
参考文献：
[1]谢希仁.计算机网络(第4版).北京:电子工业出版社,2005.
[2]杨东红,徐恪,崔勇.改进的Wu-Manber多模式匹配算法.清华大学学报.
[3]张鑫,谭建龙,程学旗. 一种改进的Wu-Manber多关键词匹配算法[J].计算机应用, 2003.
[4]孙晓山,王强,关毅,王晓龙. 一种改进的Wu-Manber多模式匹配算法及应用.中文信息学报.
[5]WU Sun,Manber U.A Fast Algorithm for Multi-Pattern Searching. Technical Report TR 94-17,University of Arizona at Tuscon, 1994.
收稿日期：2008-01-25
作者简介：王灿明（1980-），男，湖南涟源人，怀化学院计算机系，助教，硕士，主要研究网络信息安全，RFID技术；肖峰（1983-），男，四川成都人，电子科技大学，在读硕士，主要研究网络信息安全。