• 开发研究与工程应用 •

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

1. (上海理工大学光电信息与计算机工程学院，上海 200082)
• 收稿日期:2013-04-03 出版日期:2014-03-15 发布日期:2014-03-13
• 作者简介:王艳霞(1986－)，女，硕士研究生，主研方向：3G/4G网络通信技术，模式识别；江艳霞，讲师；王亚刚，教授；李 烨，高级工程师。
• 基金资助:
国家自然科学基金资助项目(61074016, 61074087)；上海市研究生创新基金资助项目(JWCXSL1202)；上海市教育委员会科研创新基金资助项目(12ZZ144)。

Research and Improvement of BMH2C Single Pattern Matching Algorithm

WANG Yan-xia, JIANG Yan-xia, WANG Ya-gang, LI Ye

1. (School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200082, China)
• Received:2013-04-03 Online:2014-03-15 Published:2014-03-13

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