计算机工程Issue(3)：298-302,5.DOI:10.3969/j.issn.1000-3428.2014.03.063
BMH2C单模匹配算法的研究与改进
Research and Improvement of BMH2C Single Pattern Matching Algorithm
摘要
Abstract
BMH2C algorithm combines BMH and BMHS algorithm. In BMH2C algorithm, the right shift distance of pattern string is determined by the double string, which is made of the character t[k] of the current window and the next character t[k+1]. BMH2C algorithm has better performance than BM, BMH and BMHS algorithm. Nevertheless, the right shift distance of pattern string in the BMH2C algorithm remains to be further increased, when the double string appears for one time or more than one time. Do like that, the number of window’s shift will be greatly reduced and the matching speed improved effectively. Therefore, an improved algorithm based on BMH2C algorithm is proposed. It takes the number of appearance in the pattern string of the double string t[k]t[k+1] into account. And the equality relationship of character t[k+2] and the character which is followed the appropriate position of t[k]t[k+1] in the pattern string is considered. The improved algorithm uses two right shift arrays and a pretreated array of the pattern strings. During the matching, the corresponding value of one of the two right shift arrays is selected as the right shift distance of current window, by judging the equality relationship of character t[k+2] and the corresponding character in the pretreated array. Experimental results show that the improved BMH2C algorithm is respectively 11.33%and 9.40%less than BMH2C algorithm on average in the same conditions, for the matching time and the number of window’s shift. With the algorithm, the matching speed is improved effectively.关键词
模式匹配/BMH2C算法/字符串/右移/预处理Key words
pattern matching/BMH2C algorithm/character string/right shift/pretreatment分类
信息技术与安全科学引用本文复制引用
王艳霞,江艳霞,王亚刚,李烨..BMH2C单模匹配算法的研究与改进[J].计算机工程,2014,(3):298-302,5.基金项目
国家自然科学基金资助项目(61074016,61074087)；上海市研究生创新基金资助项目(JWCXSL1202)；上海市教育委员会科研创新基金资助项目(12ZZ144)。 （61074016,61074087）
