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

被引：7

作者：

李雪梅

代六玲

童新海

李莉

机构：

[1] 北京电子科技学院电子信息工程系

[2] 南京理工大学计算机科学系

[3] 北京电子科技学院电子信息工程系北京

[4] 江苏南京

[5] 北京

来源：

计算机应用研究 | 2005年 / 09期

关键词：

串匹配; Boyer-Moore算法; ImprovedBoyer-Moore算法; QuickBoyer-Moore算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：49 / 51

页数：3