下载文档原格式
一种改进的Wu-Manber多模式匹配算法及应用
孙晓山;王强;关毅;王晓龙
【期刊名称】《中文信息学报》
【年(卷),期】2006(20)2
【摘要】本文针对Wu-Manber多模式匹配算法在处理后缀模式情况下的不足,给出了一种改进的后缀模式处理算法,减少了匹配过程中字符比较的次数,提高了算法的运行效率.本文在随机选择的TREC2000的52,067篇文档上进行了全文检索实验,对比了Wu-Manber算法、使用后缀模式的改进算法、不使用后缀模式的简单改进等三种算法的匹配过程中字符比较的次数.实验结果说明,本文的改进能够比较稳定的减少匹配过程中字符比较的次数,提高匹配的速度和效率.
【总页数】6页(P47-52)
【作者】孙晓山;王强;关毅;王晓龙
【作者单位】哈尔滨工业大学,计算机学院,黑龙江,哈尔滨,150001;哈尔滨工业大学,计算机学院,黑龙江,哈尔滨,150001;哈尔滨工业大学,计算机学院,黑龙江,哈尔滨,150001;哈尔滨工业大学,计算机学院,黑龙江,哈尔滨,150001
【正文语种】中文
【中图分类】TP391
【相关文献】
1.基于CUDA的Wu-Manber多模式匹配算法 [J], 马计;王国平;杨明
2.一种改进的Wu-Manber多模式串匹配算法 [J], 刘征宇;刘学生
3.一种改进的Wu-Manber多关键字匹配算法 [J], 莫德敏;刘耀军
4.Wu-Manber算法的一种综合改进 [J], 莫德敏;刘耀军
5.基于Wu-Manber的快速跳跃多模式匹配算法 [J], 王艳秋;兰巨龙
因版权原因，仅展示原文概要，查看原文内容请购买。
AC经典多模式匹配算法多模式匹配AC算法（Aho and Corasick），BM、Wu-Manber算法，WM 由BM派生，不过AC与它们无染，是另外一种匹配思路。
1.Step1:将由patterns组成的集合（要同时匹配多个patterns嘛）构成一个有限状态自动机。
Step2:将要匹配的text作为自动机输入，输出含有哪些patterns及patterns在全文中位置。
自动机的执行动作由三个部分组成：（1）一个goto function（2）一个failure function（3）一个output function我们先通过一个具体实例来了解一下这三个部分，及该自动机的运作方式。
先有个大概印象，后面会具体讲解。
patterns集合{he,she,his,hers}，我们要在”ushers”中查找并匹配。
(1)goto functioni123456789f(i)000120303（发现没？貌似i和f(i)有相同前缀哦^_^）(2)failure functioni output(i)2{he}5{she,he}7{his}9{hers}(3)output function首先我们从状态0开始，接收匹配字符串的第一个字符u，在goto（简称goto function）中可以看到回到状态0，接着第二个字符s，发现转到状态3，在output中查找一下output(3)为空字符串，说明没有匹配到patterns。
继续匹配h，转到状态4，查找output发现仍然没有匹配，继续字符e，状态转到了5，查找output，发现output(5)匹配了两个字符串she和he，并输出在整个字符串中的位置。
然后接着匹配r，但发现g(5,r)=fail，这时候我们需要查找failure，发现f(5)=2，所以就转到状态2，并接着匹配r，状态转移到了8，接着匹配s，状态转移到了9，查看output，并输出output(9):hers，记录下匹配位置。
WM算法详解WM算法采用字符块技术，增大了主串和模式串不匹配的可能性,从而增加了直接跳跃的机会。
使用散列表选择模式串集合中的一个子集与当前文本进行完全匹配。
使用前缀表进一步过滤不匹配的模式串，使算法获得了较高的运行效率。
WM算法首先对模式串集合进行预处理。
预处理阶段将建立3个表格：SHIFT表，HASH 表和PREFIX表。
SHIFT表用于在扫描文本串的时候，根据读入字符串决定可以跳过的字符数，如果相应的跳跃值为0，则说明可能产生匹配。
HASH表用来存储尾块字符散列值相同的模式串。
PREFIX表用于存储尾块字符散列值相同的模式串的首块字符散列值。
假设模式串集合P中最短的模式长度为m，那么，后续仅考虑所有模式的前m个字符组成的模式串。
设X=x1…xB为T中的待比较的长度为B的子串，通过hash函数映像得到一个索引值index，以该索引值作为偏移得到SHIFT表中的值，该值决定读到当前子串x后可以跳过的位数。
假设X映射到SHIFT表的入口为index的表项，即index=hash(x)。
SHIFT表中值的计算原则为：（1）如果X不出现在模式串中，则SHIFT[h]=m-B+1。
（2）如果X出现在某些模式串中，而且在所有的模式串中的最右出现位置为q，则SHIFT[h]=m-q。
算法匹配的大致原理：（1）设当前比较的文本串X的hash值为h。
如果SHIFT[h]=0，说明可能产生了匹配，那么需要进一步的判断。
（2）用该h值作为索引，查HASH表找到HASH[h]，它存储的是指标，指向两个单独的表：一个是模式链表，另一个是PREFIX表。
模式链表中存放的是后B个字符的hash值同为h的所有模式。
（3）对于待比较长度为m的串，如果其长度为B的前缀与模式的前缀的hash值也相同，则再将相应的文本串与符合的模式逐一进行比较，最终判定是否完全匹配。
算法匹配的主要过程：基于后缀的模式匹配，每次扫描B个字符T[m-B+1]…..T[m]。
多模式串匹配算法随着互联网和大数据时代的到来，数据量的急速增长使得文本处理和文本搜索算法越来越受到关注。
而多模式串匹配算法（Multiple Pattern String Matching）就是一个十分重要的文本处理算法，它能够高效地在文本中匹配多个模式串，被广泛应用于信息检索、网络安全等领域。
本文将介绍多模式串匹配算法的基本概念、实现方法和应用场景。
一、基本概念在介绍多模式串匹配算法之前，我们需要先了解下面几个概念：1. 模式串（Pattern String）：需要在文本中匹配的字符串。
2. 文本串（Text String）：需要进行匹配的文本。
3. 匹配（Match）：在文本中找到了与模式串相同的字符串。
4. 多模式串（Multiple Pattern）：需要匹配的模式串的集合。
二、实现方法多模式串匹配算法的实现方法有很多种，例如：1. Trie树（字典树）：将多个模式串构建成Trie树，然后在文本中逐个字符匹配，直到匹配到叶子节点为止。
2. AC自动机（Aho-Corasick Algorithm）：AC自动机是一种基于Trie树的改进算法，它可以在Trie树上同时匹配多个模式串，并且具有快速匹配的特点。
3. 后缀数组（Suffix Array）：后缀数组是将一个字符串的所有后缀按字典序排序后得到的数组，利用后缀数组可以高效地搜索模式串。
4. KMP算法（Knuth-Morris-Pratt Algorithm）：KMP算法是一种字符串匹配算法，可以在O(n)的时间复杂度内匹配单个模式串，将其与Trie树等算法结合可以实现多模式串匹配。
三、应用场景多模式串匹配算法在信息检索、网络安全、自然语言处理等领域都有广泛的应用，例如：1. 搜索引擎：搜索引擎需要对用户输入的查询串进行匹配，多模式串匹配算法可以高效地完成这个任务。
2. 病毒检测：病毒检测需要对文件进行扫描，多模式串匹配算法可以快速地检测出是否存在病毒。
改进的多模式匹配算法
王永成;沈州;许一震
【期刊名称】《计算机研究与发展》
【年(卷),期】2002(039)001
【摘要】在有限自动机的多模式匹配算法(DFSA算法)的基础上,结合Quick Search算法的优点,提出了一个快速的多模式字符串匹配算法.之后在算法中以连续跳跃的思想,给出了另一个更加有效的改进.在一般情况下,这两个算法不需要匹配目标文本串中的每个字符,并充分利用了匹配过程中本次匹配不成功的信息,跳过尽可能多的字符.在模式串较长和较短的情况下,算法都有很好的性能.实验表明,在模式串较短时,所提出的算法需要的匹配时间仅为DFSA算法的1/2到1/5,在模式串较长时,所需时间为DFSA算法的1/3至1/7.
【总页数】6页(P55-60)
【作者】王永成;沈州;许一震
【作者单位】上海交通大学计算机科学与工程系,上海,200030;上海交通大学计算机科学与工程系,上海,200030;上海交通大学计算机科学与工程系,上海,200030【正文语种】中文
【中图分类】TP311
【相关文献】
1.基于改进的模式匹配算法的SQL注入攻击防范技术 [J], 张生财;周淑惠
2.BF模式匹配算法的改进 [J], 巫喜红;文张斌
3.一种改进的字符串模式匹配算法 [J], 蔡婷;杨卫帅
4.BM模式匹配算法的研究与改进 [J], 王文霞
5.一种基于Aho-Corasick算法改进的\r多模式匹配算法 [J], CHEN Yongjie;Wushour Silamu;YU Qing
因版权原因，仅展示原文概要，查看原文内容请购买。
基于CUDA的Wu-Manber多模式匹配算法马计;王国平;杨明【期刊名称】《计算机系统应用》【年(卷),期】2012(021)003【摘要】Multi-pattern matching is a basic problem in computer science and used in many fields,in some cases,also the most time-consuming. GPU has more parallel computing capabilities than the CPU. With the introduction of CUD A,GPU computing for general purpose parallel programming becomes easier. This paper proposes Wu-Manber multi-pattern matching algorithm based on the CUD A,and evaluating the implementations we have achieved speedups up to 10 faster than the sequential implementations.%多模式匹配是计算机科学中最基本的问题,其应用在许多领域,在一些情形下也是比较耗时的.GPU拥有比CPU更强的并行计算能力,随着CUDA架构的推出,GPU用于通用计算领域的并行编程工作变得更加轻松.实现了基于CUDA架构的Wu-Manber多模式匹配算法,实验结果表明,相比传统串行算法而言,本文的实现获得了10倍以上的加速.【总页数】5页(P51-54,175)【作者】马计;王国平;杨明【作者单位】复旦大学计算机科学技术学院,上海200433;复旦大学计算机科学技术学院,上海200433;复旦大学计算机科学技术学院,上海200433【正文语种】中文【相关文献】1.基于Wu-Manber算法的大规模URL模式串匹配算法 [J], 贾博威;吴志刚;张树壮;2.基于Wu-Manber算法的大规模URL模式串匹配算法 [J], 贾博威;吴志刚;张树壮3.一种改进的Wu-Manber多模式匹配算法及应用 [J], 孙晓山;王强;关毅;王晓龙4.基于Wu-Manber的快速跳跃多模式匹配算法 [J], 王艳秋;兰巨龙5.基于大数据处理的模式匹配算法效率分析 [J], 汪滢;熊璐;刘晓因版权原因，仅展示原文概要，查看原文内容请购买。
第29卷第4期吉林大学学报（信息科学版）Vol．29No．4 2011年7月Journal of Jilin University（Information Science Edition）July2011文章编号：1671-5896（2011）04-0383-05基于WM算法改进的多模式匹配算法董迎亮a，玄雪花a，王德民b（吉林大学a．计算机科学与技术学院；b．网络中心，长春130012）摘要：为提高入侵检测系统整体的性能和效率，在研究经典的WM（Wu-Manber）多模式匹配算法的基础上，提出一种改进的WM多模式匹配算法。
该算法使用后缀表方法，减少了匹配过程中模式字符串与文本的比较次数。
实验结果表明，该算法有效提高了入侵检测系统匹配的速度和效率。
关键词：入侵检测；多模式匹配；Wu-Manber算法中图分类号：TP393.08文献标识码：AImproved Multiple Patterns Matching Algorithm Based on WM AlgorithmDONG Ying-liang a，XUAN Xue-hua a，WANG De-min b（a．College of Computer Science and Technology；b．Network Center，Jilin University，Changchun130012，China）Abstract：To improve the efficiency of intrusion detection system，we analyzed WM（Wu-Manber）multiple patterns matching algorithms，and then presented an improved patterns matching algorithm．This algorithm uses trail table to decrease the comparison times in matching process．The experiment result shows that it improves the intrusion detection system matching efficiency．Key words：intrusion detection；multiple patterns matching；Wu-Manber algorithm0引言随着计算机网络技术的飞速发展，网络安全也受到人们越来越多的关注。
为了更全面地保护网络环境，仅靠传统的防火墙技术已经不能完全满足网络安全的需求。
入侵检测技术被公认为是防火墙之后的第二道安全闸门，可以弥补防火墙技术明显的不足，为网络安全提供实时的入侵检测以及相应的防护手段。
在高速网络环境中，如果模式匹配算法不能满足处理大量实时网络数据包的要求，入侵检测系统必然会丢弃部分网络数据包，而这些被丢弃的数据包中就可能包含入侵信息。
由于模式匹配算法的性能直接影响入侵检测系统的检测效率，笔者将以基于误用检测技术的模式匹配算法为研究目标，提出一种改进后的WM多模式匹配算法。
该算法与原WM（Wu-Manber）算法相比具有运算效率高的优点。
1模式匹配算法模式匹配［1-7］是指在给定长度为n的文本串T=T［1］T［2］…T［n］中查找长度为m的模式串P= P［1］P［2］…P［m］的首次出现或多次出现的过程，其中T［i］（1≤i≤n），P［j］（1≤j≤m）∈∑（字符集）。
若在T中能找到P的出现，则称匹配成功；否则称匹配失败。
一次在文本中只能对一个模式串进行匹配的算法，称为单模式匹配算法，可同时对多个模式串进行匹配的算法称多模式匹配算法。
收稿日期：2011-04-13作者简介：董迎亮（1982—），男，长春人，吉林大学硕士研究生，主要从事计算机网络安全研究，（Tel）86-136********（E-mail）liangdyl @；王德民（1958—），男，长春人，吉林大学教授，硕士生导师，主要从事智能网络与数据库、网络安全研究（Tel）86-138********（E-mail）wdm@。
483吉林大学学报（信息科学版）第29卷1.1经典的单模式匹配算法最简单的模式匹配算法是BF（Brute-Force）算法。
在BF算法的文本串T和模式串P的字符比较中，首先比较T第一个字符和P的第一个字符，如果相等，则比较下个字符，如果不相等，T指向下一位，与P重复上述过程。
由于在匹配过程中，T的指针经常回溯，导致BF算法效率很低。
在最坏情况下，时间复杂度为O（mn）。
1970年，Cook从理论上证明了一维模式字符串的匹配问题可以在O（m+n）时间内完成。
Knuth 等［1］借鉴了Cook的思想，在BF算法的基础上提出了一种快速模式匹配算法，称为KMP（Knuth-Morris-Pratt）算法1，该算法消除了BF算法的文本串指针在相当多个字符比较相等后，只要有一个字符比较不匹配，便需要文本T回溯的缺点。
使算法的效率得到了大幅度提高，时间复杂度达到最理想的O（m +n）。
1977年，Boyer等［2］提出了一个全新的模式匹配算法———BM（Boyer-Moore）算法。
该算法在匹配过程中，模式串P从左向右移动，但与文本串T的比较按照从右向左的次序进行。
BM算法最主要的特点是在匹配过程中，可以跳过很多无用的字符。
通过这种跳跃式的匹配，获得了极高的匹配效率。
1990年，Sunday［3］提出了一种比BM算法搜索速度更快的算法———Sunday算法。
其核心思想是在匹配过程中，模式串P并不要求一定要按从左向右的顺序进行比较还是从右向左的顺序进行与文本串T 的比较，它在发现不匹配时，算法能跳过比BM算法更多的干扰字符进行下一步的匹配，从而提高了匹配效率。
1.2经典的WM多模式匹配算法1994年，Wu等［8］提出了多模式匹配算法（WM：Wu-Manber），该算法具有实现过程简单、逻辑清晰和运行效率高等特点。
WM算法在设计上广泛借鉴了BM算法的思想，采用散列（Hash）技术和高效过滤等方法，减小了匹配冲突对算法执行效率的影响。
WM算法将文本串T中的每B个字符分一个字符块，B为每个字符块的长度，B的值通常取2或3。
在本文中，B=2。
首先对模式串P进行预处理，在预处理阶段需要构造3张表：shift表、hash表和pre-fix表。
WM算法的主要匹配过程：从文本串T的第m－B+1个字符处开始（m为模式集合中最短模式串的长度），计算当前字符块的哈希值h，然后查找shift表中的shift［h］的值，当shift［h］=0时，则计算文本串T的首字符块的哈希值h'，在prefix表中进行查找prefix［index］=h'（index为模式串的下标）。
然后将文本串与模式串index逐个字符进行比对。
如果shift［h］≠0，模式串P将向右移动shift［h］个字符，重复上面的过程。
WM算法的主要优势是字符跳跃距离大，使用shift表可以跳过那些不可能成功的匹配入口，匹配入口点少，从而对字符的匹配次数减少，匹配的效率提高。
2改进后的WM算法通过对WM算法的分析，发现该算法使用了字符块技术，增大了模式串与文本串之间不匹配的概率。
因此在匹配过程中会跳过许多无用的字符，提高了匹配效率。
而且WM算法还使用了前缀表过滤掉了不符合的模式串，进一步减少了匹配的时间。
目前，WM算法被公认为是多模式匹配算法中匹配效率极高的算法之一。
但通过对该算法的进一步研究发现，WM算法还可以完善和改进。
WM算法的一个明显不足在于，在查找特定模式串过程中只对模式串集合中所有模式串前m个字符进行比对，m个字符后面的字符没有做任何的操作。
那么WM算法在查找特定模式串过程中，浪费了对m个以后字符串的资源。
假设，模式串集合中有100个模式字符串与文本串T进行匹配，其中10个模式串的长度为2，10个字符串为4，其余80个字符串长度为100，取字符块长度B=2。
由于WM 算法只关心字符块的哈希值h是否为0和文本的首字符块的哈希值h'是否存在于前缀表prefix中。
在shift［h］=0与h'∈prefix表时，就会将对应的模式串与文本串进行逐个字符比较。
假如，该模式串恰好是长度为100，则该模式串与文本串将会匹配100次才能确定是否匹配成功。
如果该模式串与文本串的第99或第100个字符不匹配，则前面逐个字符匹配的98次就会浪费。
当然这里说的是特殊情况，主要为了说明WM算法在匹配过程中的不足。
针对WM 算法在查找特定模式串时产生的资源浪费问题，笔者提出了一种增加一张后缀表（trail 表）的方法，可以有效解决上述问题。
该方法可以过滤掉更多的无效模式串，从而提高了匹配特定模式串的效率。
在文本进行匹配时，判断条件会变为shift ［h ］=0，prefix ［P ］=text_prefix 和trail ［P ］=text _trail 。
后缀表的建立与前缀表建立方法类似。
改进后WM 算法的预处理过程，需要建立4张表：shift 表、hash 表、prefix 表和trail 表。
shift 表的建立：这里的移动表和正常的BM 算法的shift 表起相同的作用。
但是，为了避免一个一个地匹配的字符，考虑对一块长度为B 的字符块进行匹配的方法。
该方法可以明显跳过无用字符，提高算法的匹配效率。
设M 为所有模式总的大小，M =km ，m 为模式串集合中最短模式串的长度。
设c 为字母表的大小。
一个好的B 的取值应该是log c 2M ，取B =2。
设W 是长度为B 的块字符，则在Shift 表构造的过程中将分以下两种情况。
1）如果W 不在模式串集合中任何模式串中出现，则shift ［h ］=m －B +1。
2）如果W 出现在模式串集合的某些模式串中，设W 在模式串P 的位置index 结束，并且W 在模式串集合的其他模式串中，都不会结束于比index 更后的位置，则shift ［h ］=m －index 。
hash 表的建立：当文本串T 中当前某段子串和模式串集合中某个或某些模式字符串发生匹配时，即shift ［h ］=0。
为了确定具体与哪个模式串发生了匹配，避免和模式串集合中所有模式字符串都进行比表1Hash 表构造过程Tab.1The construction process of hash table 模式串hash 表P 0：1234hash ［13108］=0P 1：ab cd efg hash ［25444］=1P 2：fg hi jklmn hash ［26729］=2较，可以使用哈希技术最小化需要比较的数量。
