The Improve of BM Algorithm Base on First Character

The article analyzes the classical BM algorithm and an improved algorithm, and then it puts forward a new improved algorithm which called I_BM algorithm according to the characteristics of the string matching. The I_BM algorithm determines the right distance according to the first character of the pattern string and the distance between the matching windows, so it fasts matching. The matching way of I_BM algorithm is from right to left. In order to verify the IBM algorithm＇ s performance, it does experiments on I_BM algorithm from two aspects of the matching times and the numbers of matching characters under the condition of the same text strings and pattem string. The experimental results show that I_BM algorithm is more quickly and more efficient because it reduces greatly the number of matching and character comparison for maximizing to skip the bad characters.

基于Snort的BM模式匹配算法的改进

近些年来,很多国家工控系统都遭受到了网络安全攻击,造成了巨大的经济损失。网络入侵检测系统(NIDS)是网络安全的重要组成部分之一,开源入侵检测软件通过活跃的社区和研究者们不断更新来应对这快速发展的网络环境。文章介绍了Boyer-Moore字符串匹配算法,并提出一种改进的BM算法,并基于Snort入侵检测系统实现并验证改进算法,实验表明改进的算法提高了模式匹配效率。

对BM串匹配算法的一个改进

在对著名的Boyer -Moore串匹配算法进行分析后 ,对BM算法中的尝试位置移动处理部分进行改进 ,提出了IBM算法。该算法将好后缀移动与坏字符移动合并进行处理 ,从而尽量利用已有信息进行更大的尝试位置移动 ,使算法具有更高的效率。对IBM算法进行复杂度分析 ,对BM算法、KMP算法和IBM算法进行实际性能比较 ,结果表明IBM算法的平均运行时间明显优于BM算法与KMP算法。

BM模式匹配改进算法

字符串模式匹配在实际生活中被广泛的应用,它也是计算机基础科学的一个重要部分,现在比较著名的模式匹配算法有BF算法、KMP算法、RK算法和BM算法。讨论了一种基于BM模式匹配算法及其算法的改进。

一种面向入侵检测的BM模式匹配改进算法

在分析了目前常用的模式匹配算法的基础上,提出了一种改进的BM算法。实验结果表明改进的模式匹配算法能减少比较次数,有效地提高了匹配速度。

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

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

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

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

基于自动机并操作的多目标AC-BM算法

AC-BM算法的优点在于能同时进行多个模式串的匹配搜索,且文本串的移位得到优化,但一次只能在一个文本串中进行搜索。为了实现一次可以同时在多个文本串中进行搜索,设计了多目标AC-BM算法。利用自动机并操作技术构造多目标多模式树自动机,借助BM算法的坏字符跳转技术来计算文本串集移位。在Snort系统中分别实现2-目标AC-BM算法和3-目标AC-BM算法。实验结果表明,新算法如果在多个文本串中找到模式串就停止(表示检测到攻击行为),其在时间性能上就明显优于AC-BM算法。

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

分析了目前网络上最流行的BM算法及其改进算法BMH,在此基础上提出了BMH算法的改进算法BMH2。考虑了模式串自身的特征,在原有移动距离数组的基础上增加一个新的移动数组,从而充分利用模式串特征进行更大距离的移动,使算法获得更高的效率。实验证明,改进后的算法能够增加"坏字符"方法的右移量,有效地提高匹配速率。

基于双字符序检测的BM模式匹配改进算法

BM算法是一类效率较高的单模式匹配算法,通常改进的BM算法往往从提高字符首次不匹配概率和匹配窗口的最大移动距离入手,但为实现此目的所带来的高访存开销使算法实际效率受到影响。DCSBM算法以适当减小关键步长为代价,在利用双字符序检测提高首次匹配失败概率的同时,对匹配窗口移动关键步长字符距离所需的查表次数和访存次数进行优化。经测试,DCSBM算法显著提高了匹配窗口的平均移动距离。在文本或模式串相对较长情况下,该算法实际测试效率优于BM、BMHS、BMN等算法。

BM算法的研究与改进

随着网络的迅速发展,网络安全问题日益突出,入侵检测技术也成为当今社会关注的焦点.对于基于规则的入侵检测来说,模式匹配算法非常重要,它直接影响到系统的准确性和实时性能.文中介绍了KM P和BM算法,对BM算法的改进进行了研究,并提出一种改进的BM算法,改进后的算法极大地提高了匹配速度.

基于语义和改进BM算法的Web服务发现

随着面向服务计算模式的快速应用,越来越需要高效准确的Web服务发现机制.针对目前基于关键字和语义匹配的服务发现方法存在查全率和查准率不高的情况,提出一种基于语义和改进BM算法的Web服务发现方法.该方法首先进行语义Web服务发现,当语义匹配结果为空时,采用改进的BM算法进行模式匹配作为补充,弥补了单纯语义服务发现不足的缺点,有效解决了由于Web服务的名称、输入、输出和功能描述在概念上存在字面上的歧义而导致语义服务匹配失效的问题.实验结果表明,该方法在查全率和查准率方面具有较大的优越性.

基于改进的BM算法在IDS中的实现

指出了模式匹配技术的好坏直接关系到检测系统性能的好坏 ,通过对开放的源代码snort中模式匹配技术的改进 ,提出了一种更快的字符匹配算法 .该算法可以大大加快入侵检测系统的检测速度 ,提高现有的入侵检测系统的检测能力 .

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

文章在分析BM算法以及一些重要的改进算法的基础上,提出了一种新的改进算法———BMG算法。该算法结合了BMH算法和BMHS算法的优点,同时考虑了字符串后一位字母的惟一性,大大提高了最大位移m+1的出现概率,因此有效地加快了匹配速度。

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

模式匹配在入侵检测系统中有着广泛的应用。在对BM以及相关算法分析的基础上,提出了一种基于BM算法的改进算法。该算法同时运用BMH和BMHS算法的思想对模式进行移动,并利用了模式串末字符与首字符的组合性,缩短了比较过程,有效地减少了匹配过程中的字符比较次数。实验证明,该算法具有高的匹配效率。

BM算法中函数shift的研究

建立BM算法中函数shift及其构造算法的严格的形式理论,对于BM算法及其各种变形的研究与改进是十分必要的。给出了shift的一个清晰的形式定义,引入模式串后缀的特征集及其最小值函数,通过特征集描述了shift的构造,从而严格建立了shift及其构造算法的理论基础。根据shift的构造定理与最小值函数的迭代计算方法,给出了shift的一个新的构造算法,证明了该算法具有线性的时间与空间复杂度。理论分析和计算结果表明,该算法比已有算法更简单,计算复杂度更低,因而更适合硬件实现。

BM模式匹配算法的研究和改进

模式匹配算法在数字通信、入侵检测等多种领域都有着广泛的应用,BM算法以其高效的匹配过程成为模式匹配算法中应用最为广泛的算法之一。尽管如此,BM算法的效率还是可以再提高的。本文在介绍经典BM算法及其改进的BMH、BMHS算法的基础上,通过整合、改进后,提出了一种新的改进的IBMH算法。在对以上算法进行复杂度分析以后,再通过具体的实验验证。结果表明IBMH算法在比较次数、运行时间、稳定性等方面明显优于BM、BMH以及BMHS等算法。

BM串匹配算法的一个改进算法

在BM算法的基础上,本文提出了改进的算法—IMBM算法。该算法有以下重要特点:(1)有效地减少了字符重复比较与样本的移动次数,提高了算法的匹配效率;(2)在串的匹配问题中有较广泛的用途。

改进BM算法及其在网络入侵检测中的应用

传统BM算法存在一些无用的比较,影响了字符串的匹配速度,降低了入侵检测效率。为此,提出一种改进BM算法,并将其用于网络入侵检测系统的检测引擎中。实验结果表明,较采用BM算法的Snort检测器,改进BM算法构建的网络入侵检测系统可有效降低误报率和漏报率,提高入侵检测率与时间利用率。显然,这对提升网络入侵检测系统的整体能力非常有用。

基于改进BM算法的确定型有穷自动机的设计

通过对有穷自动机理论与BM算法进行分析,设计了一个基于改进BM算法的确定型有穷自动机的模型.该模型描述了向基于改进BM算法的确定型有穷自动机输入文本字符串,自动机输出TRUE,说明文本串中存在与模式串相匹配的字符;自动机输出FALSE,说明文本串中不存在与模式串相匹配的字符串.并给出了对比实验及分析.