-
题名BMH2C单模匹配算法的研究与改进
被引量：5
- 1
-
-
作者
王艳霞
江艳霞
王亚刚
李烨
-
机构
上海理工大学光电信息与计算机工程学院
-
出处
《计算机工程》
CAS
CSCD
2014年第3期298-302,共5页
-
基金
国家自然科学基金资助项目(61074016
61074087)
+1 种基金
上海市研究生创新基金资助项目(JWCXSL1202)
上海市教育委员会科研创新基金资助项目(12ZZ144)
-
文摘
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算法
字符串
右移
预处理
-
Keywords
pattern matching
bmh2c algorithm
character string
right shift
pretreatment
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
