BMH2C单模匹配算法的研究与改进

摘要：

BMH2C算法综合BMH和BMHS算法，利用当前窗口字符t[k]及其下一字符t[k+1]组成的双字符串来决定模式串右移量，具有比BM算法、BMH算法、BMHS算法更优的性能。但对于双字符串在模式串中出现一次及以上的情况，BMH2C算法中的模式串右移量仍有待进一步增大，从而减少当前窗口右移次数，提高 BMH2C算法的匹配效率。为此，在 BMH2C算法的基础上提出一种改进算法，该算法考虑双字符串 t[k]t[k+1]在模式串中出现的次数，以及该双字符串在模式串中对应位置的后继字符与字符t[k+2]的相等关系。改进算法利用2个右移数组和1个模式串预处理数组，在匹配过程中通过判断字符t[k+2]与模式串预处理数组中相应字符是否相等，从而选择2个右移数组之一的对应值作为当前窗口的右移量。实验结果显示，在相同条件下，对于当前窗口移动次数和匹配所耗时间，BMH2C改进算法比BMH2C算法分别平均减少11.33%和9.40%，有效提高了匹配效率。

关键词：模式匹配、BMH2C算法、字符串、右移、预处理

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61074016,61074087；上海市研究生创新基金资助项目JWCXSL1202；上海市教育委员会科研创新基金资助项目12ZZ144。

在线出版日期：2014-04-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：298-302