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

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

Boyer-Moore串匹配算法的改进

在分析Boyer-Moore(BM)算法的基础上,提出了BM算法的一个新的变形。其基本思想是在算法的预处理阶段,对扩展模式串Pa建立好后缀规则,其中:P是模式串,a是字母表中的任一字符,既加大了已匹配后缀的长度,同时隐含了Sunday算法的坏字符规则,从而获得更大的窗口跳跃距离。理论分析证明,该算法具有线性最差时间复杂度和亚线性平均时间复杂度,空间复杂度为O(m(σ+1))。实验结果表明,该算法的实际性能与BM算法相比有明显改善,尤其适合小字母表的情形。

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

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

对Boyer-Moore模式匹配算法的优化研究

在大数据时代,如何运用模式匹配方法加强对相关信息的搜索是当前自然科学和社会科学界都面临的重要问题.通过对经典的模式匹配算法BM算法、BMH算法和BMHS算法的分析和研究,并在此基础上提出了加快匹配速度,缩短比较次数和匹配的时间的改进方法——OBM模式匹配算法.

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

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

基于自适应BM3D的绝缘子缺陷检测图像降噪方法

由于拍摄环境的影响,获取的图像中常常混有噪声,极易影响绝缘子缺陷检测的准确性。针对该问题,提出了一种自适应BM3D降噪方法。首先,引入基于噪声水平与图像块协方差矩阵特征值的统计关系的噪声估计算法,解决原始BM3D算法需要先验知识的问题;其次,以峰值信噪比为目标函数,通过量子遗传算法得到绝缘子图像在各个噪声强度下的参数最优值,包括基础估计中的硬阈值参数、距离阈值和最终估计中的距离阈值;最后,以噪声强度为自变量,采用多项式拟合的方式得到上述3个参数的拟合曲线,从而得到各个噪声强度下算法的最佳参数组合,实现BM3D算法在不同噪声水平下的参数快速自适应。对比实验的结果表明所提出的方法在直观视觉和客观评价指标上优于其他方法。当噪声标准差为25时,所提出的方法相较于原始BM3D算法在峰值信噪比、结构相似性和边缘保留指数指标上均有所提升,尤其是边缘保留指数提升近20%。在提升降噪效果的同时能够保留更多边缘细节,这有助于提高后续绝缘子识别及缺陷检测的效果。

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

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

基于BM3D算法的快中子图像降噪方法

在快中子照相过程中,由于受到各种因素影响,快中子图像严重降质,呈现大量噪声,不利于无损检测和后续的定量分析。通过噪声分析得出了快中子图像的噪声统计分布符合高斯噪声模型,探讨了将BM3D算法应用到快中子图像降噪处理的方法。实验结果表明,BM3D算法不仅能够有效滤除快中子图像的噪声,而且保护了图像的细节和边缘信息,可为快中子图像的降噪处理提供参考。

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

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

基于乌鸦搜索算法和自适应BM3D的NSST域电气设备红外图像增强

为了解决红外图像对比度低、模糊、含噪声等问题,本文提出基于信息熵准则乌鸦搜索算法和三维块匹配(block matching 3D,BM3D)自适应去噪的电气设备非下采样剪切波变换(non-subsampled shearlet transform,NSST)红外图像增强方法。通过NSST变换将图像分解为不同频率的2个部分。低频图像主要为设备特征,高频子带主要为噪声。针对低频图像中的背景干扰问题,提出乌鸦搜索算法进行分割得到设备前景和环境后景,前者经灰度扩增得到前景增强图,后者经直方图均衡得到后景增强图。针对高频子带中的噪声干扰问题,提出BM3D自适应去噪算法用于去噪。通过实验可知,基于乌鸦搜索算法和自适应BM3D的图像增强算法针对图像分割细节处理、多余杂音的过滤以及对比度的提高均有显著效果。

一种改进的Boyer-Moore算法在IDS中的应用

在IDS的检测引擎模块设计中,基于Pattern-Matching的误用检测算法是设计师们最常用到的一种核心技术实现途径,而IDS丢包率和误报率的高低以及检测引擎匹配速度的快慢都取决于模式匹配算法性能的好与坏。Boyer-Moore算法及其改进了的Boyer-Moore Horspool算法和Boyer-Moore HorspoolS算法是目前应用最广泛的单模式匹配算法。在分析了BM算法及各种改进算法的基础上提出了一种新的基于BM算法的改进算法。该算法利用了字符串末字符和末字符对应文本串的下一字符的唯一性,同时考虑了文本串的信息以加大匹配速率,从而更好地适应IDS对模式匹配算法高效性的要求。

Boyer-Moore串查找JAVA算法

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

基于方差稳定变换和BM4D的MR图像莱斯噪声去除方法

磁共振图像(MR)通常含有莱斯(Rician)噪声,莱斯噪声是一种与信号相关的非加性噪声,不服从正态分布,难以去除。已有方法表明,方差稳定变换(VST)可以将方差不固定的莱斯分布转换为方差固定的高斯分布。首先,运用VST算法把莱斯噪声转换为高斯噪声,然后,运用在高斯去噪方面表现优良的三维块匹配去噪(BM4D)算法去噪,最后,运用方差稳定变换的逆变换(IVST)对去噪后的图像进行处理,得到最终的无偏的去噪后图像。仿真结果表明,研究所用方法不但在视觉上明显优于BM4D算法和小波去噪(wavelet)算法,而且在峰值信噪比(PSNR)和平均结构相似度(SSIM)两个客观指标上明显优于其他两种方法,其中PSNR高出10dB左右,SSIM高出30%以上,该方法有效地降低了噪声,较好地保留了图像的边缘及细节信息。

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

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

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

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

BM模式匹配改进算法

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

BM模式匹配算法剖析

在对典型的BF、KMP模式匹配算法进行比较分析的基础上,详细分析了BM算法。为了进一步加快算法的速度,对BM算法中已经部分匹配的移动位置情况进行改进。在原有的移动距离函数基础上增加一个新的移动距离函数,从而尽量利用已有信息进行更大的尝试位置移动,使算法具有更高的效率。通过引用具体实例,比较分析了改进前后的BM算法,结果证明改进后的BM算法的速度更快,效率更高。

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

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

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

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

BM算法的研究与改进

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