多模式匹配算法及硬件实现 被引量：42

1

作者 李伟男 鄂跃鹏 +1 位作者 葛敬国 钱华林 《软件学报》 EI CSCD 北大核心 2006年第12期2403-2415,共13页

介绍了多模式匹配的算法和硬件实现方法.首先介绍了两种常用的多模式匹配算法——Aho-Corasick基于自动机的算法和Wu-Manber基于hash的后缀匹配加移位跳跃的算法以及相关的改进算法.并通过实验对各种多模式匹配算法的时空复杂度进行了... 介绍了多模式匹配的算法和硬件实现方法.首先介绍了两种常用的多模式匹配算法——Aho-Corasick基于自动机的算法和Wu-Manber基于hash的后缀匹配加移位跳跃的算法以及相关的改进算法.并通过实验对各种多模式匹配算法的时空复杂度进行了分析比较.通过几个硬件实现的实例介绍了多模式匹配的硬件实现方法及策略.最后对多模式匹配的发展趋势进行了展望. 展开更多

关键词 多模式匹配 AHO-CORASICK算法 有限状态自动机 wu-manber算法 FPGA(现场可编程门阵列) TCAM(三态内容寻址存储器) bloom filter

下载PDF 职称材料

Wu-Manber算法性能分析及其改进 被引量：13

2

作者 陈瑜 陈国龙 《计算机科学》 CSCD 北大核心 2006年第6期203-205,209,共4页

在模式匹配中,多模式匹配算法越来越受到人们的关注。本文首先介绍了一些著名的多模式匹配算法,重点介绍了Wu-Manber算法的基本概念及其实现原理,此算法在实践应用中是最有效的。然后提出了对Wu-Manber算法的改进,以解决多模式串长度很... 在模式匹配中,多模式匹配算法越来越受到人们的关注。本文首先介绍了一些著名的多模式匹配算法,重点介绍了Wu-Manber算法的基本概念及其实现原理,此算法在实践应用中是最有效的。然后提出了对Wu-Manber算法的改进,以解决多模式串长度很短时出现的性能问题。最后,实验数据表明,改进后的Wu-Manber算法,其性能远远优于传统的Wu-Manber算法。 展开更多

关键词 wu-manber算法 多模式匹配 性能分析

下载PDF 职称材料

改进的Wu-Manber多模式串匹配算法 被引量：13

3

作者 杨东红 徐恪 崔勇 《清华大学学报（自然科学版）》 EI CAS CSCD 北大核心 2006年第4期555-558,共4页

为提高串匹配算法在实际应用中的运算性能，对Wu-Manber算法进行了改进。吸收了QS（Quick Search）算法的思想，并利用匹配过程中匹配失败的信息，达到最大跳跃距离，实现了快速的多模式匹配算法。对改进后的算法和Wu-Manber算法进行对... 为提高串匹配算法在实际应用中的运算性能，对Wu-Manber算法进行了改进。吸收了QS（Quick Search）算法的思想，并利用匹配过程中匹配失败的信息，达到最大跳跃距离，实现了快速的多模式匹配算法。对改进后的算法和Wu-Manber算法进行对比实验，当最小模式长度较大时，改进后的算法性能与原算法基本相同；而当模式最小长度较小时（〈9），改进后的算法比原算法有显著提高，用于英文文本时比原算法的所用时间平均减少了8％～20％，用于中文文本时平均减少了15％～30％。 展开更多

关键词 多模式串匹配 字符串匹配 wu-manber算法

原文传递

入侵检测中一种新的多模式匹配算法 被引量：8

4

作者 李庚 韩进 谢立 《计算机应用研究》 CSCD 北大核心 2008年第8期2474-2476,共3页

基于模式匹配的检测方法是目前入侵检测系统的一种重要方法,因此作为模式匹配方法核心的字符串匹配算法直接影响入侵检测系统的性能和效率。在AC算法和Wu-Manber算法的研究基础上,提出了一种新的多模式匹配算法——AC-WM。该算法能够增... 基于模式匹配的检测方法是目前入侵检测系统的一种重要方法,因此作为模式匹配方法核心的字符串匹配算法直接影响入侵检测系统的性能和效率。在AC算法和Wu-Manber算法的研究基础上,提出了一种新的多模式匹配算法——AC-WM。该算法能够增加字符跳转距离,比较稳定地减少匹配过程中字符比较的次数,提高匹配的速度和效率。 展开更多

关键词 入侵检测 多模式匹配 AC算法 wu-manber算法 AC-WM算法

下载PDF 职称材料

一种面向入侵检测的快速多模式匹配算法 被引量：8

5

作者 高朝勤 陈元琰 李梅 《计算机应用》 CSCD 北大核心 2008年第1期82-84,共3页

随着网络速度和入侵检测规则的持续增长，模式匹配正在成为网络入侵检测系统的性能瓶颈。提出了一种新的Wu-Manber类型的模式匹配算法，通过将模式分组，对不同予模式组采用不同匹配方法，显著提高了模式匹配的效率。对比实验表明，当... 随着网络速度和入侵检测规则的持续增长，模式匹配正在成为网络入侵检测系统的性能瓶颈。提出了一种新的Wu-Manber类型的模式匹配算法，通过将模式分组，对不同予模式组采用不同匹配方法，显著提高了模式匹配的效率。对比实验表明，当模式组中含有长度小于3的模式时，新算法性能比原算法平均提高了29％-44％。 展开更多

关键词 多模式匹配 入侵检测系统 wu—manber算法 网络安全

下载PDF 职称材料

入侵检测系统中模式匹配算法的研究与改进 被引量：9

6

作者 陶善旗 李俊 +1 位作者 郭伟群 李海龙 《计算机技术与发展》 2010年第2期167-170,174,共5页

入侵检测系统的性能很大程度上取决于规则检测的效率,模式匹配算法是规则检测引擎的核心算法。对模式匹配算法进行了研究,重点分析了多模式匹配算法Wu-Manber算法。针对Wu-Manber算法在单字节模式串下移动距离短的不足,并结合网络数据... 入侵检测系统的性能很大程度上取决于规则检测的效率,模式匹配算法是规则检测引擎的核心算法。对模式匹配算法进行了研究,重点分析了多模式匹配算法Wu-Manber算法。针对Wu-Manber算法在单字节模式串下移动距离短的不足,并结合网络数据包和入侵检测系统中规则的特点,提出了一种适合入侵检测系统的改进的模式匹配算法。该算法利用位示图方法解决了单字节模式串匹配的问题,增加了移动距离,提高了检测数据包与规则匹配的速度,提升了系统运行的效率。 展开更多

关键词 入侵检测系统 模式匹配 wu—manber算法

下载PDF 职称材料

DHSWM:一种改进的WM多模式匹配算法 被引量：8

7

作者 刘卫国 胡勇刚 《中南大学学报（自然科学版）》 EI CAS CSCD 北大核心 2011年第12期3765-3771,共7页

针对WM算法的查找效率随着模式集规模的增大而降低的问题,提出一种改进算法。在预处理阶段,改变原有Hash表中的链表结构,采用双哈希法将模式串存放在Hash1表中指定的区间,Hash表中存放该存储区间的起始位置与区间长度;Prefix表用于判断... 针对WM算法的查找效率随着模式集规模的增大而降低的问题,提出一种改进算法。在预处理阶段,改变原有Hash表中的链表结构,采用双哈希法将模式串存放在Hash1表中指定的区间,Hash表中存放该存储区间的起始位置与区间长度;Prefix表用于判断模式集中是否存在与当前匹配窗口中文本前缀相同的模式;当Shift表中出现移动值为0时,根据后缀出现在模式串其他位置的信息计算匹配窗口可滑动的最大距离并存于Shift1表中。在查找阶段,采用双哈希法在Hash1表的某一区间中查找模式串,避免在大规模模式集情况下查找过长的模式链表,扩大匹配操作后匹配窗口滑动的距离,减少冗余的匹配操作,缩短查找时间。研究结果表明:在模式集规模较大时,改进后的算法显著地提高了匹配速度;当模式串数目超过5 000条时,改进算法的查找时间要比WM算法缩短40%～47%。 展开更多

关键词 入侵检测 模式匹配 wu-manber算法 双哈希查找

下载PDF 职称材料

一种改进的Wu-Manber多模式串匹配算法 被引量：5

8

作者 马伟华 刘玉梅 +1 位作者 叶飞 杨旭东 《应用科技》 CAS 2007年第10期32-34,38,共4页

在分析Wu—Manber算法的基础上，结合QS算法思想，设计了一种改进的多模式串匹配算法：QWM（quick Wu—Manber）．算法充分利用紧邻当前窗口之后的B字符块，使算法的最大移动距离由原来的（m—B＋1）增大至（m＋B），平均移动距离也得... 在分析Wu—Manber算法的基础上，结合QS算法思想，设计了一种改进的多模式串匹配算法：QWM（quick Wu—Manber）．算法充分利用紧邻当前窗口之后的B字符块，使算法的最大移动距离由原来的（m—B＋1）增大至（m＋B），平均移动距离也得到很大提高．同时对QWM算法和Wu-Manber算法进行了实验对比，无论模式串数量和最小长度怎么变化，性能都有较大提升．实验表明，改进的算法在对英文文本进行扫描时有4％～13％的提高． 展开更多

关键词 多模式串匹配 字符串匹配 wu—manber算法

下载PDF 职称材料

短规则有效的快速多模式匹配算法 被引量：7

9

作者 夏念 嵩天 《计算机工程与应用》 CSCD 北大核心 2017年第7期1-8,共8页

随着网络技术快速发展,多模式匹配算法所处理的模式集合数目呈爆炸式增长且模式长度不统一,传统的多模式匹配算法已无法有效适应新的模式集合:不同的模式集合,同一算法呈现的性能差异明显。针对模式长度不等且分布不均匀的模式集合,提... 随着网络技术快速发展,多模式匹配算法所处理的模式集合数目呈爆炸式增长且模式长度不统一,传统的多模式匹配算法已无法有效适应新的模式集合:不同的模式集合,同一算法呈现的性能差异明显。针对模式长度不等且分布不均匀的模式集合,提出一种改进WM的多模式匹配算法(MWM),将模式集合分为长短两个集合并构造各自的长短SHIFT表,辅助WM算法原有SHIFT表验证匹配效果,匹配过程由单一线程完成。该算法不仅减少了模式验证次数,而且提高了算法的平均跳转距离。实验结果表明,所提出的多模式匹配算法(MWM)在模式长度不等且分布不均匀的模式集合下表现出更优的性能,随着模式集合的数目增多,性能提升越明显。在模式集合数目达到100 000时,相比WM算法,该算法性能提升达到了40%。 展开更多

关键词 模式匹配 字符串匹配 wu-manber算法

下载PDF 职称材料

一种面向PDF文本内容审查的高效多模式匹配算法 被引量：6

10

作者 刘邦国 陈庆春 类先富 《计算机应用研究》 CSCD 北大核心 2020年第6期1755-1759,共5页

针对Wu-Manber多模式匹配算法所存在的匹配效率低、跳转距离较小的问题,结合PDF文本内容的编码规则,提出了一种适用于中文PDF文本内容审查的Wu-Manber改进算法。该算法使用布隆过滤器提取模式串关键信息,同时结合双重哈希和PDF文本编码... 针对Wu-Manber多模式匹配算法所存在的匹配效率低、跳转距离较小的问题,结合PDF文本内容的编码规则,提出了一种适用于中文PDF文本内容审查的Wu-Manber改进算法。该算法使用布隆过滤器提取模式串关键信息,同时结合双重哈希和PDF文本编码规则,减少了无谓的匹配次数,加大了跳转幅度,从而提升了PDF文本的匹配性能。实验结果表明,这种改进算法在PDF文本审查中的匹配速率有较大提升,尤其当最短模式串较长且模式串规模较大时速度可以提升一倍以上。 展开更多

关键词 多模式匹配 wu-manber算法 PDF文本编码 布隆过滤器

下载PDF 职称材料

基于WM算法改进的多模式匹配算法 被引量：6

11

作者 董迎亮 玄雪花 王德民 《吉林大学学报（信息科学版）》 CAS 2011年第4期383-387,共5页

为提高入侵检测系统整体的性能和效率,在研究经典的WM(Wu-Manber)多模式匹配算法的基础上,提出一种改进的WM多模式匹配算法。该算法使用后缀表方法,减少了匹配过程中模式字符串与文本的比较次数。实验结果表明,该算法有效提高了入侵检... 为提高入侵检测系统整体的性能和效率,在研究经典的WM(Wu-Manber)多模式匹配算法的基础上,提出一种改进的WM多模式匹配算法。该算法使用后缀表方法,减少了匹配过程中模式字符串与文本的比较次数。实验结果表明,该算法有效提高了入侵检测系统匹配的速度和效率。 展开更多

关键词 入侵检测 多模式匹配 wu-manber算法

下载PDF 职称材料

一种改进的针对中文编码的Wu-Manber多模式匹配算法 被引量：4

12

作者 王一霈 石春 +1 位作者 戴上静 吴刚 《小型微型计算机系统》 CSCD 北大核心 2015年第4期778-781,共4页

Wu-Manber算法是多模式匹配领域性能优越的算法之一.针对Wu-Manber算法不能很好的用于中文环境,以及滑动距离受限和冗余匹配的问题,提出一种改进的针对中文编码的WM_CH多模式匹配算法.WM_CH针对中文编码修改了哈希函数,优化了建立哈希... Wu-Manber算法是多模式匹配领域性能优越的算法之一.针对Wu-Manber算法不能很好的用于中文环境,以及滑动距离受限和冗余匹配的问题,提出一种改进的针对中文编码的WM_CH多模式匹配算法.WM_CH针对中文编码修改了哈希函数,优化了建立哈希表的过程;修改并优化了算法匹配过程,在执行精确匹配时消除了冗余匹配,增大了单次精确匹配后的滑动距离.实际测试表明,该算法性能优异,保持与原算法匹配精确度一致,针对中文编码能快速过滤非中文字符.在特征串集规模大于50 000时,匹配速度比原算法提升40%以上,同时滑动窗口的跳转次数显著下降. 展开更多

关键词 多模式匹配算法 特征串 wu—manber算法 WM_CH算法

下载PDF 职称材料

一种改进的Wu-Manber多关键字匹配算法 被引量：4

13

作者 莫德敏 刘耀军 《中文信息学报》 CSCD 北大核心 2009年第1期30-34,共5页

针对Wu-Manber算法在处理公共子后缀模式情况下的不足,该文提出了一种基于非空公共子后缀模式的处理算法。该算法把有非空公共子后缀的模式汇集在一起,进一步减小了next链表的平均长度。在匹配过程中减少了字符比较的次数,从而提高算法... 针对Wu-Manber算法在处理公共子后缀模式情况下的不足,该文提出了一种基于非空公共子后缀模式的处理算法。该算法把有非空公共子后缀的模式汇集在一起,进一步减小了next链表的平均长度。在匹配过程中减少了字符比较的次数,从而提高算法的运行效率。该文对搜狗实验室给出的相关文档进行全文检索实验,并和原Wu-Manber算法、孙晓山等提出的改进算法进行比较。实验结果表明,该文提出的改进算法有效地减少了匹配过程中字符比较的次数,从而提高匹配的速度和效率。 展开更多

关键词 计算机应用 中文信息处理 wu—manber算法 多关键字匹配 模式匹配 字符串匹配

下载PDF 职称材料

Snort下模式串匹配算法的研究与改进 被引量：3

14

作者 李海芳 王喜聪 +1 位作者 陈俊杰 赵月爱 《太原理工大学学报》 CAS 北大核心 2010年第3期256-259,共4页

在阐述入侵检测技术研究现状的基础上,通过对入侵检测系统snort下BM和Wu-Manber两个模式匹配算法的研究,然后对其分别改进,并进行实验验证,实验结果表明使用改进的算法提高了匹配效率,减少了存储需求,从而进一步提高了入侵检测系统的检... 在阐述入侵检测技术研究现状的基础上,通过对入侵检测系统snort下BM和Wu-Manber两个模式匹配算法的研究,然后对其分别改进,并进行实验验证,实验结果表明使用改进的算法提高了匹配效率,减少了存储需求,从而进一步提高了入侵检测系统的检测性能。 展开更多

关键词 入侵检测 SNORT BM算法 wu-manber算法

下载PDF 职称材料

多模式匹配算法 被引量：2

15

作者 车莉 杨波 眭新光 《电信技术研究》 2007年第12期42-47,共6页

针对特征串匹配问题，本文对模式匹配算法作了概括介绍，分析了单模式匹配算法KMP、BM、QS等算法和多模式匹配算法Aho-Corasick、Wu-Manber、SBOM等算法的特点。在此基础上，文章结合Wu-Manber算法和QS算法各自的优点，同时对算法的匹... 针对特征串匹配问题，本文对模式匹配算法作了概括介绍，分析了单模式匹配算法KMP、BM、QS等算法和多模式匹配算法Aho-Corasick、Wu-Manber、SBOM等算法的特点。在此基础上，文章结合Wu-Manber算法和QS算法各自的优点，同时对算法的匹配和跳跃机制作了相应改进，提出了一种新的匹配算法QWM（QuickWu-Manber）。 展开更多

关键词 多模式匹配 KMP算法 BM算法 QS算法 AHO-CORASICK算法 wu-manber算法 SBOM算法

下载PDF 职称材料

入侵检测系统中模式匹配算法的优化研究 被引量：2

16

作者 秦晓明 牛全营 吴淼 《计算机与现代化》 2009年第4期5-7,共3页

模式匹配是入侵检测系统中常用的技术,而字符串匹配算法是其核心内容。本文分析了三个常用的匹配算法,并在此基础上对其中的BM(Boyer-Moore)算法和WM(Wu-Manber)算法进行了改进和优化,从而提高了模式匹配的速度和效益。

关键词 入侵检测 模式匹配 BM算法 wu-manber算法

下载PDF 职称材料

Wu-Manber算法在大规模模式串下的改进 被引量：2

17

作者 莫德敏 刘耀军 《晋中学院学报》 2008年第3期86-90,共5页

对笔者在另一篇文章《一种改进的Wu-Manber多关键字匹配算法》中提出的算法进行了改进,把原算法中next链表中结点的Same-Subsuffix域中分裂成两个子域,使得搜索过程中字符比较的次数进一步减少,从而提高算法的效率.特别是在大规模模式... 对笔者在另一篇文章《一种改进的Wu-Manber多关键字匹配算法》中提出的算法进行了改进,把原算法中next链表中结点的Same-Subsuffix域中分裂成两个子域,使得搜索过程中字符比较的次数进一步减少,从而提高算法的效率.特别是在大规模模式串的情况下新算法的效率比原算法有进一步的提高.实验结果表明,当模式串较少时,新算法效率与原算法相比有一定的损失.而随着模式串的增加,新算法具有更高的效率.因此,新的算法比原算法具有更大的适用范围. 展开更多

关键词 wu—manber算法 多关键字匹配 模式匹配 字符串匹配 信息检索

下载PDF 职称材料

基于Wu-Manber算法的大规模URL模式串匹配算法 被引量：2

18

作者 贾博威 吴志刚 张树壮 《智能计算机与应用》 2017年第5期4-9,共6页

大规模高速URL匹配是许多网络安全系统中的关键技术,经典串匹配算法在大规模URL情况下有许多限制。针对URL数据的特点在经典多模式串匹配算法Wu-Manber基础上提出XWM-Tree算法和XWM-Hash算法。算法应用了模式串窗口选择,两阶段哈希和关... 大规模高速URL匹配是许多网络安全系统中的关键技术,经典串匹配算法在大规模URL情况下有许多限制。针对URL数据的特点在经典多模式串匹配算法Wu-Manber基础上提出XWM-Tree算法和XWM-Hash算法。算法应用了模式串窗口选择,两阶段哈希和关联容器组织冲突链表等多种优化手段,大幅度提高了算法的匹配性能。在大规模真实数据集上的测试结果表明本文提出的算法匹配速度可以提高一倍以上,尤其是当最短模式串较长的时候更有优势。 展开更多

关键词 多模式串匹配 URL匹配 wu-manber算法

下载PDF 职称材料

Hash函数对WM算法性能的影响 被引量：1

19

作者 张速 王锐利 《华北水利水电学院学报》 2011年第3期111-113,共3页

针对软件多模式匹配问题,对现有匹配算法做了介绍,分析了Wu-Manber算法的特点,发现采用不同的Hash函数和Hash空间大小可能会得到不同的实际性能.通过试验验证了该结果的正确性.同时指出要提高WM算法的性能,应该采用合适的Hash函数和Has... 针对软件多模式匹配问题,对现有匹配算法做了介绍,分析了Wu-Manber算法的特点,发现采用不同的Hash函数和Hash空间大小可能会得到不同的实际性能.通过试验验证了该结果的正确性.同时指出要提高WM算法的性能,应该采用合适的Hash函数和Hash空间大小. 展开更多

关键词 算法 多模式匹配 wu-manber算法 HASH函数 Hash空间

下载PDF 职称材料

基于Snort入侵检测系统模式匹配改进算法研究 被引量：1

20

作者 杨军 邓芳林 《计算机安全》 2011年第6期10-14,共5页

网络技术的应用已经从传统的小型业务系统逐渐扩展到大型的关键业务系统中,但是在浩瀚的Internet网络中,系统容易受到外界的攻击与破坏,信息被窃取和修改等网络安全问题越来越严重。研究现有的snort入侵检测系统算法,并进行优化改进,使... 网络技术的应用已经从传统的小型业务系统逐渐扩展到大型的关键业务系统中,但是在浩瀚的Internet网络中,系统容易受到外界的攻击与破坏,信息被窃取和修改等网络安全问题越来越严重。研究现有的snort入侵检测系统算法,并进行优化改进,使其在实际应用中提高信息安全防范能力。 展开更多

关键词 网络入侵检测 SNORT BM算法 wu-manber算法

下载PDF 职称材料