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

• 作者: 李烨 江艳霞 王亚刚 王艳霞
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 模式匹配 BMH2C算法 字符串 右移 预处理
• 年，卷（期）: 2014,（3）
• 所属期刊栏目: 开发研究与工程应用
• 页码范围: 298-302
• 页数: 5页
• 分类号: TP301.6
• 字数: 4997字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2014.03.063

摘要

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%，有效提高了匹配效率。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	江艳霞	上海理工大学光电信息与计算机工程学院	21	69	6.0	7.0
2	王亚刚	上海理工大学光电信息与计算机工程学院	134	472	11.0	15.0
3	李烨	上海理工大学光电信息与计算机工程学院	44	133	7.0	9.0
4	王艳霞	上海理工大学光电信息与计算机工程学院	1	7	1.0	1.0