共查询到19条相似文献,搜索用时 31 毫秒
1.
在分析QS算法的基础上,提出了一种新的改进算法—EQS算法。该算法在模式匹配成功时用一个字符来确定右移量,在匹配失败时用两个字符来确定右移量。实验结果表明:该算法使模式串的右移量增大、匹配次数减少,达到提高算法效率的目的。 相似文献
2.
3.
4.
一个改进的BM串匹配算法 总被引:8,自引:0,他引:8
赵一瑾 《计算机研究与发展》1998,35(1):45-48
文中利用BM算法中依据d函数来右移模式距离大小的特点,在一定条件下,将模式分解成具有一定性质的两个子串。通过子模式各自的性质及相互间的关系,控制模式匹配过程,以减少字符重复比较次数,从而提高算法匹配效率。 相似文献
5.
在对著名的SunWu多模式串匹配算法进行分析之后,结合QS算法的优点,设计了一种较高效的多模式串匹配算法QMS.该算法使用散列技术和前缀表减少发生部分匹配时实际进行的模式串比较次数.在计算跳跃距离时,充分考虑当前窗口紧邻的下一个字符带来的信息,使用更加精确的跳跃距离计算方法以获得更大的平均跳跃距离,从而获得更高的扫描效率和空间利用率.在真实文本上的对比实验表明,在通常应用环境中,该算法缩短了扫描时间,取得了较好的效果. 相似文献
6.
7.
8.
本文在分析BM和QS算法特点的基础上,综合利用了正文T[i m-1]和T[i m]位置上 的字符信息,提出一种移动距离不小于模式长度的快速字符串匹配算法。该算法解决了QS算法在 skip[i m-1]相似文献
9.
一种串匹配的快速Boyer-Moore算法 总被引:5,自引:0,他引:5
在对经典的Boyer-Moore和Quick Search串匹配算法进行分析的基础上,提出了一种更加快速的串匹配算法Quick Boyer-Moore(QBM)。QBM算法利用当前尝试中的已匹配子串、匹配失败字符信息以及与当前窗口下一个字符的位置信息,以在每一次跳跃中获得更大的跳跃距离,从而使算法具有更高的效率。在真实语料上的实验结果表明,QBM算法的效率较显著地高于原始的BM算法及其改进算法Impmved Boyer-Moore(IBM)。 相似文献
10.
在分析Boyer-Moore (BM)算法的基础上,提出了BM算法的一个新的变形。其基本思想是在算法的预处理阶段,对扩展模式串Pa建立好后缀规则,其中:P是模式串,a是字母表中的任一字符,既加大了已匹配后缀的长度,同时隐含了Sunday算法的坏字符规则,从而获得更大的窗口跳跃距离。理论分析证明,该算法具有线性最差时间复杂度和亚线性平均时间复杂度,空间复杂度为O(m(σ+1))。实验结果表明,该算法的实际性能与BM算法相比有明显改善,尤其适合小字母表的情形。 相似文献
11.
一种针对网络入侵检测系统的字符串匹配算法 总被引:2,自引:0,他引:2
精确的字符串匹配算法对网络入侵检测系统的性能有重要的影响,为了提高其效率,这里设计了一个专门针对网络入侵检测系统的字符匹配算法,并在snort1.9中实现。和目前最好的替代算法相比较,试验表明此算法能提高NIDS性能10%~40%。 相似文献
12.
针对已有算法对文本和模式的相关性依赖较大,提出一种基于分段的字符串匹配算法——SM。该算法利用特殊字符将文本先分段再匹配,且匹配过程对模式内容和长度不敏感。通过将SM算法与经典算法进行分析和实验对比,证明SM算法性能稳定,特别是在多模式字符串匹配情况下,SM算法具有比Wu-Manber算法更快的速度和更小的空间消耗。 相似文献
13.
一种高效的多目标串匹配算法 总被引:5,自引:0,他引:5
本文通过引入右对齐位置标识方式解决了Boyer-Moore算法思想用于多串匹配的串长不等的问题,提出用于多模式串的高效匹配算法MP_BM。该算法的特点主要在于能够直接处理长度不等的多模式串匹配,同时又能获得很高的匹配效率。 相似文献
14.
本文分析了模糊字符串几种类型和它的表示方法,并给出模糊匹配的算法及C语言的源程序,同时也指出了在文枉编辑器的应用例子。 相似文献
15.
16.
针对现有名单匹配算法由于对名单中文件路径使用明文保存方式存在安全隐患,提出一种基于字符串压缩的用于全模式匹配的名单匹配算法。首先对保存有文件全路径的字符串进行MD5运算,然后将MD5值与压缩处理成16个字节的二进制路径数据合并进行求模运算,最终将名单元素转化成一个32字节结构体。通过仿真实验对朴素匹配算法、BM、压缩三种算法在内存使用、遍历时间、查找时间以及重复数上进行比较,实验结果表明,所提出的算法在性能以及安全性上优于其他算法。 相似文献
17.
字符串检索指在一个文本Text=t1…tn中找出一个字符串Pat=p1…pm的所有出现。本文给出了在CREW/CRCW PRAM机器模型上并行检索汉字/字符串的算法, 它使用n/m。个处理机, 预处理时间为O(m+|∑|, 并行执行时间为O(m)。 相似文献
18.
提出一种基于坏字符序检测的快速模式匹配算法(BCSBM)。该算法利用相邻字符序列在模式串中不出现的概率较单字符高的特性,基于好字符和坏字符序表实现字符匹配过程的"跳跃"。BCSBM算法显著减少了匹配窗口内字符的匹配次数,同时增大了匹配窗口的平均移动距离。算法的实际测试效率较高,在文本或模式串相对较长的情况下该算法的效率提高明显。 相似文献
19.
一个改进的较佳路径求解算法 总被引:3,自引:0,他引:3
较佳路径的求解问题事实上是货郎担近似算法的问题。现有算法实质上属于一种经典的单向增长的贪婪法,存在着改进的余地。本文提出一种改进的双向增长的贪婪算法,与经典算法相比,其策略有所增强,因而其结果得到进一步改善,更加接近于理想的Hamilton通路。算法的理论分析和实际测试数据都证实,改进是有效的。 相似文献