一种串匹配的快速Boyer-Moore算法 被引量：7

1

作者 李雪梅 代六玲 +1 位作者 童新海 李莉 《计算机应用研究》 CSCD 北大核心 2005年第9期49-51,共3页

在对经典的Boyer-Moore和Quick Search串匹配算法进行分析的基础上,提出了一种更加快速的串匹配算法Quick Boyer-Moore(QBM)。QBM算法利用当前尝试中的已匹配子串、匹配失败字符信息以及与当前窗口下一个字符的位置信息,以在每一次跳跃... 在对经典的Boyer-Moore和Quick Search串匹配算法进行分析的基础上,提出了一种更加快速的串匹配算法Quick Boyer-Moore(QBM)。QBM算法利用当前尝试中的已匹配子串、匹配失败字符信息以及与当前窗口下一个字符的位置信息,以在每一次跳跃中获得更大的跳跃距离,从而使算法具有更高的效率。在真实语料上的实验结果表明,QBM算法的效率较显著地高于原始的BM算法及其改进算法Improved Boyer-Moore(IBM)。 展开更多

关键词 串匹配 boyer-moore算法 IMPROVED boyer-moore算法 Quick boyer-moore算法

下载PDF 职称材料

入侵检测系统中BM模式匹配算法的改进 被引量：11

2

作者 程玉青 梅登华 《计算机技术与发展》 2009年第3期172-174,共3页

随着计算机网络的持续快速发展,网络安全问题日益突出,入侵检测技术也成为当前研究的热点。检测引擎作为入侵检测系统(IDS)的核心模块,基本上采用基于模式匹配的检测方法,模式匹配算法直接影响到系统的准确性和实时性能。文中介绍了目... 随着计算机网络的持续快速发展,网络安全问题日益突出,入侵检测技术也成为当前研究的热点。检测引擎作为入侵检测系统(IDS)的核心模块,基本上采用基于模式匹配的检测方法,模式匹配算法直接影响到系统的准确性和实时性能。文中介绍了目前最常用的BM模式匹配算法,以及其改进算法Boyer-Moore-Horspool(BMH)算法,在此基础上提出了另一种改进的BM算法。该算法减少了匹配次数,有效地加快了模式匹配的速度,提高了入侵检测的效率。 展开更多

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

下载PDF 职称材料

基于Snort和改进BM算法的入侵检测系统的研究与实现 被引量：7

3

作者 崔玮 刘建伟 张其善 《电子测量技术》 2006年第6期144-146,167,共4页

网络入侵检测系统是近年来发展较快的一种网络安全技术。文中提出并实现了一种在基于Snort和改进的BM算法的入侵检测系统的实现方案。分析研究了该系统的架构,网络数据截获模块的设计方案。文中还针对传统的Boyer-Moore匹配算法的缺陷... 网络入侵检测系统是近年来发展较快的一种网络安全技术。文中提出并实现了一种在基于Snort和改进的BM算法的入侵检测系统的实现方案。分析研究了该系统的架构,网络数据截获模块的设计方案。文中还针对传统的Boyer-Moore匹配算法的缺陷进行了讨论,并提出了改进意见。结论显示改进后的算法能够取得更高的匹配效率和更短的匹配时间。 展开更多

关键词 入侵检测 SNORT boyer-moore算法

下载PDF 职称材料

基于Horspool算法的模糊匹配 被引量：2

4

作者 钱立进 吴泽俊 董红斌 《计算机工程》 CAS CSCD 北大核心 2004年第1期60-61,共2页

匹配模式中存在模糊信息的匹配形式称为模糊匹配，它是目前字符串匹配的重 要研究方向。Horspool算法是精确匹配的经典算法，但不能实现模糊匹配。该文将要求匹配 的模式转化为相应的二进制数序列，在Horspool算法基础上扩大其功能，使... 匹配模式中存在模糊信息的匹配形式称为模糊匹配，它是目前字符串匹配的重 要研究方向。Horspool算法是精确匹配的经典算法，但不能实现模糊匹配。该文将要求匹配 的模式转化为相应的二进制数序列，在Horspool算法基础上扩大其功能，使其能够实现模糊 匹配，且不影响其精确匹配的功能。 展开更多

关键词 模式匹配 模糊匹配 BM算法 HORSPOOL算法 精确匹配

下载PDF 职称材料

一种改进的多模式串匹配算法 被引量：4

5

作者 代六玲 黄河燕 陈肇雄 《模式识别与人工智能》 EI CSCD 北大核心 2006年第1期47-51,共5页

在对著名的 SunWu 多模式串匹配算法进行分析之后,结合 QS 算法的优点,设计了一种较高效的多模式串匹配算法 QMS.该算法使用散列技术和前缀表减少发生部分匹配时实际进行的模式串比较次数.在计算跳跃距离时,充分考虑当前窗口紧邻的下一... 在对著名的 SunWu 多模式串匹配算法进行分析之后,结合 QS 算法的优点,设计了一种较高效的多模式串匹配算法 QMS.该算法使用散列技术和前缀表减少发生部分匹配时实际进行的模式串比较次数.在计算跳跃距离时,充分考虑当前窗口紧邻的下一个字符带来的信息,使用更加精确的跳跃距离计算方法以获得更大的平均跳跃距离,从而获得更高的扫描效率和空间利用率.在真实文本上的对比实验表明,在通常应用环境中,该算法缩短了扫描时间,取得了较好的效果. 展开更多

关键词 多模式串匹配 boyer-moore算法 Quick Search算法 SunWu算法

原文传递

一种改进Boyer-Moore算法效率的预处理算法 被引量：1

6

作者 金人超 宋恩民 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2005年第z1期265-267,共3页

通过理论分析和测试发现,对大多数字符串而言,按某个方向搜索文本总是会比按另一个方向的搜索速度快.提出了新的预处理算法,在使用Boyer-Moore算法之前先确定一个较优的搜索方向,其时间复杂度和空间复杂度分别为O(σm)和O(σ+m),其中σ... 通过理论分析和测试发现,对大多数字符串而言,按某个方向搜索文本总是会比按另一个方向的搜索速度快.提出了新的预处理算法,在使用Boyer-Moore算法之前先确定一个较优的搜索方向,其时间复杂度和空间复杂度分别为O(σm)和O(σ+m),其中σ和m分别为字母表的大小和字符串图案的长度.采用真实的人类DNA序列测试,包括序列库中前1 000个长度超过1 000的完整序列作为文本,从中随机选出1 000个长度为20的序列片段作为图案,进行实验对比,证明可以将搜索时间平均缩短到原来的约90%. 展开更多

关键词 DNA序列 字符串 图案匹配 boyer-moore算法

下载PDF 职称材料

BWT-Boyer-Moore压缩域搜索算法的研究

7

作者 姚全珠 丁晓剑 +1 位作者 任雪利 张志锋 《计算机应用研究》 CSCD 北大核心 2006年第7期59-61,共3页

针对Boyer-Moore匹配算法对压缩文本文件搜索的不足,分析了当前对于压缩文件搜索的主要方法,提出了一种基于BW转换的高效的搜索算法并予以验证。

关键词 压缩域 boyer-moore算法 Burrow-Wheeler转换

下载PDF 职称材料

基于多模板匹配和可信度分析的中文文档图像关键词过滤方法

8

作者 陈界伟 徐蔚然 郭军 《计算机应用研究》 CSCD 北大核心 2005年第2期35-36,42,共3页

针对互联网中文文档图像非法信息过滤提出了一种多模板匹配结合可信度分析的方法。该方法克服了传统OCR速度慢的缺点,同时改善了基于图像特征匹配方法对字体和噪音敏感的特性。通过改变关键词搜索方式有效地减小了计算量,提高了识别速... 针对互联网中文文档图像非法信息过滤提出了一种多模板匹配结合可信度分析的方法。该方法克服了传统OCR速度慢的缺点,同时改善了基于图像特征匹配方法对字体和噪音敏感的特性。通过改变关键词搜索方式有效地减小了计算量,提高了识别速度。实验结果表明了该方法的有效性。 展开更多

关键词 关键词识别 多模板匹配 boyer-moore算法 可信度分析

下载PDF 职称材料

汉语定义语句的抽取方法 被引量：1

9

作者 张寅生 《计算机与数字工程》 2011年第10期45-47,112,共4页

该文介绍了在汉语文本中抽取定义语句的方法。方法的主要特点是:给定被定义的词汇(字符串),应用Bo-yer-Moore算法查找该串在文本中的位置,继而在该句子中查找符合定义特征的谓词。在这个工作基础上,根据谓词字符串的特征排除谓词歧义,... 该文介绍了在汉语文本中抽取定义语句的方法。方法的主要特点是:给定被定义的词汇(字符串),应用Bo-yer-Moore算法查找该串在文本中的位置,继而在该句子中查找符合定义特征的谓词。在这个工作基础上,根据谓词字符串的特征排除谓词歧义,并按照句法分析的结果对定义语句修饰谓词的不同语法单元进行识别,从而实现了基于字符串和语法特征的识别的定义语句抽取。 展开更多

关键词 知识抽取 信息抽取 汉语句子识别 定义语句 boyer-moore算法 自然语言理解

下载PDF 职称材料

改进的字符串查找算法 被引量：1

10

作者 陈瀛 张子能 韩行 《机电产品开发与创新》 2007年第2期140-141,147,共3页

字符串匹配效率的提高,能够带来入侵检测系统检测效率的提高。BM、WM是目前常用的字符匹配算法,从这些算法中结合数理统计抽样的思想,本文希望通过抽样检测的方式提高匹配的效率。首先,新算法按照模式字符串的长度,从文本中固定地截取... 字符串匹配效率的提高,能够带来入侵检测系统检测效率的提高。BM、WM是目前常用的字符匹配算法,从这些算法中结合数理统计抽样的思想,本文希望通过抽样检测的方式提高匹配的效率。首先,新算法按照模式字符串的长度,从文本中固定地截取字符作为抽样点;其次,判断该抽样点是否在模式中出现,并从中分离出那些出现在模式中的抽样点。最后,在分离出的抽样点周围进行精确的模式匹配,从中找到模式字符串。此外,本文还给出了算法的正确性证明。 展开更多

关键词 BM算法 WM算法 字符串 模式匹配 多模式匹配 入侵检测

下载PDF 职称材料

嗅探模式Web过滤器设计与实现

11

作者 王天竹 孙良旭 李林林 《辽宁科技大学学报》 CAS 2011年第3期259-263,共5页

对比Web过滤器的嵌入和嗅探工作模式,分析嗅探工作模式的部署方式和工作原理,使用原始套接字编程技术捕获网络数据包,按照IP、TCP和HTTP协议进行协议分析。当客户端向服务器端发送的HTTP请求信息时,使用Boyer-Moore算法对预定义的模式... 对比Web过滤器的嵌入和嗅探工作模式,分析嗅探工作模式的部署方式和工作原理,使用原始套接字编程技术捕获网络数据包,按照IP、TCP和HTTP协议进行协议分析。当客户端向服务器端发送的HTTP请求信息时,使用Boyer-Moore算法对预定义的模式进行模式匹配,并通过直接和间接两种方式实现先于服务器端在客户端显示Web信息。实际运行测试效果说明,嗅探模式Web过滤器在模式匹配速度和反馈过滤信息上都达到嵌入式Web过滤器的运行效果。 展开更多

关键词 嗅探 Web过滤 boyer-moore算法 TCP/IP协议栈

下载PDF 职称材料

带记忆的Boyer-Moore型模式匹配算法及其复杂性分析

12

作者 刘晓华 《湖南大学学报（自然科学版）》 EI CAS CSCD 北大核心 2008年第1期84-88,共5页

通过构建前缀匹配自动机,使得每轮匹配后下个匹配窗口的文本总是保持左端部分为模式的一个前缀、右端部分全为未比较过的字符的形式.对于与此相应的模式匹配算法,已证明文本内的每个字符在整个匹配过程中最多被比较一次,从而字符总比较... 通过构建前缀匹配自动机,使得每轮匹配后下个匹配窗口的文本总是保持左端部分为模式的一个前缀、右端部分全为未比较过的字符的形式.对于与此相应的模式匹配算法,已证明文本内的每个字符在整个匹配过程中最多被比较一次,从而字符总比较次数不超过n,已达到任意算法最坏情况下字符总比较次数的最小值.另外,在适当条件下还从理论上证明了此算法的亚线性(即字符总比较次数小于cn,其中常数c<1).根据实验结果,算法的实际运行速度快于Boyer-Moore算法. 展开更多

关键词 模式匹配 boyer-moore算法 自动机 计算复杂性

下载PDF 职称材料

基于后缀搜索的单模式匹配算法研究

13

作者 巫喜红 《计算机技术与发展》 2012年第12期127-130,共4页

快速发展的网络带给人们方便的同时,其安全问题也伴随而来,解决此问题就是提高入侵检测技术。而入侵检测系统的高效性和准确性又受到模式匹配算法的影响。文中在详细分析三种基于后缀搜索的单模式匹配算法特点的基础上,通过从不同模式... 快速发展的网络带给人们方便的同时,其安全问题也伴随而来,解决此问题就是提高入侵检测技术。而入侵检测系统的高效性和准确性又受到模式匹配算法的影响。文中在详细分析三种基于后缀搜索的单模式匹配算法特点的基础上,通过从不同模式串数目角度,对算法进行匹配所需要的时间、所尝试的次数、所比较的字符个数三方面进行实验。实验结果表明,由于QS和RF算法能够跳跃较大长度的字符串,能大大地缩短扫描时间,因而能更有效地提高模式匹配速度,更好地应用到检测系统中。 展开更多

关键词 后缀搜索 单模式匹配 BM算法 QS算法 RF算法

下载PDF 职称材料

一种快速的基于BM模式匹配的改进算法 被引量：9

14

作者 马占飞 杨树英 郭广丰 《控制与决策》 EI CSCD 北大核心 2013年第12期1855-1858,1863,共5页

模式匹配算法是入侵检测系统(IDS)中非常重要的一种算法.在研究和分析几种常用模式匹配算法的基础上,提出一种快速的基于BM(Boyer-Moore)模式匹配的改进算法—–IBM算法.该算法充分利用模式串的末字符和末字符所对应的文本串的后两字符... 模式匹配算法是入侵检测系统(IDS)中非常重要的一种算法.在研究和分析几种常用模式匹配算法的基础上,提出一种快速的基于BM(Boyer-Moore)模式匹配的改进算法—–IBM算法.该算法充分利用模式串的末字符和末字符所对应的文本串的后两字符的唯一性,同时参考文本串本身的信息来提高模式串的移动量,使得每次失配后,在保证不丢失匹配成功可能性的前提下尽可能多地向后跳跃.实验结果表明,该算法相比其他模式匹配算法,在检测性能和匹配效率上均具有很大优势,并且能够有效地提高IDS的检测效率和性能. 展开更多

关键词 模式匹配算法 入侵检测系统 IBM算法 模式串 文本串

原文传递

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

15

作者 董明明 巩青歌 张琦 《计算机应用与软件》 CSCD 2011年第5期272-274,277,共4页

入侵检测系统作为防火墙的合理补充,已经发展成为网络安全体系中的一个关键性组件。网络技术的飞速发展给入侵检测系统提出新的挑战,需要通过各种途径来提高系统性能,而模式匹配算法的优劣直接影响到入侵检测系统的核心模块——规则匹... 入侵检测系统作为防火墙的合理补充,已经发展成为网络安全体系中的一个关键性组件。网络技术的飞速发展给入侵检测系统提出新的挑战,需要通过各种途径来提高系统性能,而模式匹配算法的优劣直接影响到入侵检测系统的核心模块——规则匹配模块的运行效率。通过对原有BM算法的深入分析,从如何增大模式不匹配时的滑动距离这一点出发,对BM算法进行改进与实现,并通过实验证明该方法提高了匹配效率。 展开更多

关键词 入侵检测系统 模式匹配 BM算法

下载PDF 职称材料

Boyer-Moore算法的改进设计

16

作者 何强 卿昱 《信息安全与通信保密》 2005年第12期98-100,共3页

模式匹配算法在理论计算机科学领域占有重要地位,Boyer-Moore算法被认为是日常应用中效率最高的模式 匹配算法,本文提出了富有挑战性的问题:给出了该算法的一个优化模型。

关键词 模式匹配 boyer—moore算法 坏字符移动

原文传递

基于Linux和改进BM算法的入侵检测系统的研究与实现

17

作者 陈丹 郑增威 李际军 《计算机应用与软件》 CSCD 北大核心 2005年第7期106-107,共2页

网络入侵检测系统是近年来发展较快的一种网络安全技术。提出并实现了一种在Linux下的网络入侵检测系统,分析研究了该系统的架构,数据包过滤器BPF模型,网络数据截获模块的设计方案,以及改进的BoyerMoore字符匹配算法的具体实现等关键技术。

关键词 Linux BM算法 网络入侵检测系统 网络安全技术 字符匹配算法 BPF模型 包过滤器 设计方案 数据截获 关键技术 架构 模块

下载PDF 职称材料

一种改进的BM模式匹配算法 被引量：25

18

作者 杨薇薇 廖翔 《计算机应用》 CSCD 北大核心 2006年第2期318-319,共2页

首先介绍了目前最常用的BM模式匹配算法,以及其改进算法Boyer-Moore-Horspool(BMH)算法,在此基础上提出了另一种改进的BM算法,该算法减少了匹配次数,有效的加快模式匹配的速度。

关键词 模式匹配 BM算法 boyer—moore-Horspool算法

下载PDF 职称材料

基于内容的网络信息安全审计中的匹配算法研究 被引量：9

19

作者 陈国龙 陈火旺 康仲生 《小型微型计算机系统》 CSCD 北大核心 2004年第9期1676-1679,共4页

对流经网络的 WWW、E- mail、BBS和 FTP报文提出信息审计的方法 ,针对系统字符集比较大、模式串中出现的字符较少的情况下 ,提出一种改进的模式匹配算法 。

关键词 报文审计 匹配算法 BM(boyer-moore)算法

下载PDF 职称材料

基于BB-BM算法的网络协议内容符合性测试方法

20

作者 李涛 胡爱群 高尚 《东南大学学报（自然科学版）》 EI CAS CSCD 北大核心 2015年第6期1027-1031,共5页

为了检测网络通信协议的安全性,使用高效的模式识别方法对协议内容进行符合性测试.采用黑盒测试的方法,在检测端将协议服务器和检测模块分离,设计了协议安全性测试框架和测试流程;提出了以字节块为单位、分块计算摘要值再进行匹配的BB-B... 为了检测网络通信协议的安全性,使用高效的模式识别方法对协议内容进行符合性测试.采用黑盒测试的方法,在检测端将协议服务器和检测模块分离,设计了协议安全性测试框架和测试流程;提出了以字节块为单位、分块计算摘要值再进行匹配的BB-BM算法.实验结果表明,使用该方法能够对网络协议按照内容种类划分值域空间,通过匹配算法进行符合性测试.在进行模式匹配时通过分块处理减少了模式串和目标串数量,从而导致跳跃距离增加,匹配次数减少,检测性能在最优和最差测试状态下较现有检测方法分别提高了20%和80%.在该测试框架下,以字节块为单位进行匹配有效提升了检测效率,适用于对字段格式固定的网络协议进行内容符合性测试. 展开更多

关键词 内容符合性 模式识别 BM算法 协议安全

下载PDF 职称材料