一种串匹配的快速Boyer-Moore算法

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

一种改进Boyer-Moore算法效率的预处理算法

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

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

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

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

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

Boyer-Moore串查找JAVA算法

针对 JAVA虚拟机运行代码效率低的特点 ,提出了实现 JAVA字符串快速搜索的改进算法，运用有限状态自动机（ FSM）控制实现 Boyer－ Moore串查找 JAVA方法，详细描述了算法的机理及其实现的 JAVA源程序。

入侵检测中模式匹配算法的性能分析

模式匹配算法在入侵检测中有着广泛的应用,它直接影响到入侵检测系统的实时性能。论文主要研究了Boyer-Moore算法,ModifiedWu-Manber算法,Exclusion-Based算法和Aho-Corasick算法。通过实验对上述四种算法在混合攻击和特定攻击的条件下进行了性能测试,根据实验结果,得出了不同算法的应用范围,为今后入侵检测系统开发者选择模式匹配算法提供了有价值的参考。

面向入侵检测的模式匹配算法研究

在入侵检测系统的实现中,关键部分是检测引擎的实现。而在检测引擎的实现中,关键的是数据分析模块。对于基于规则的入侵检测来说,模式匹配算法非常重要,它直接影响到系统的准确性和实时性能。论文主要研究了BruteForce算法,Boyer-Moore算法,Aho-Corasick算法,Set-wiseBoyer-Moore-Horspool算法,Aho-Corasick_Boyer-Moore算法。

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

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

一种BM模式匹配算法的改进

模式匹配算法是入侵检测系统中使用较多的一种重要算法。在分析了BM算法以及相关算法的基础上,提出了一种新的改进算法——BMI算法。该算法借鉴了BM算法的思想,并利用了下一字符和末字符的单一性和组合性,有效地提高了最大位移出现的概率。实验测试结果表明该算法能够有效提高匹配过程的效率。

一种高效的多目标串匹配算法

本文通过引入右对齐位置标识方式解决了Boyer Moore算法思想用于多串匹配的串长不等的问题 ,提出用于多模式串的高效匹配算法MPBM。该算法的特点主要在于能够直接处理长度不等的多模式串匹配 。

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

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

基于BM窗口竞争的高效单模式匹配算法

对于单模式匹配Boyer-Moore(BM)算法,为提高首字符的不匹配率和失配窗口的最大移动距离,结合BM系列改进算法的设计思想,提出一种高效算法Skii-BM。在Q(x)函数基础上引入窗口竞争思想,以极大化跳跃距离。实验结果表明,改进算法能减少不必要的匹配过程,提高窗口移动速度,从而改善匹配效率。

汉语定义语句的抽取方法

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

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

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

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

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

基于Libpcap和Libnids的网络入侵检测系统(NIDS)设计与实现

本中设计并实现了一种在RedhatLinux操作系统下基于Libpcap、Libnids和Boyer-Moore算法的网络入侵检测系统,重点阐述了该系统的体系结构,入侵规则库的建立,基于BPF过滤机制的Libpcap数据包捕获技术,利用Libnids实现IP分片重组和TCP流重组技术。

高效率的串查找 一个简捷的算法怎样带来巨大的变化

为什么有些程序比其它程序执行得快?比方说,为什么一个字处理程序对一篇文档进行拼写检查需要30秒,而另一个字处理程序只需要15秒种? 这种速度差异常常取决于代码的效率。一个程序员可能在100个时钟周期内完成的一项工作。

一种改进的多模式串匹配算法

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