计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

基于BM窗口竞争的高效单模式匹配算法

陈伟,滕宏舜   

  1. (浙江师范大学数理与信息工程学院,浙江 金华 321004)
  • 收稿日期:2014-12-08 出版日期:2015-12-15 发布日期:2015-12-15
  • 作者简介:陈伟(1973-),男,副教授,主研方向:模式识别,密码学;滕宏舜,硕士研究生。
  • 基金项目:
    金华市科学技术研究计划基金资助项目(2013-1-023)。

Efficient Single Pattern Matching Algorithm Based on BM Window Competition

CHEN Wei,TENG Hongshun   

  1. (College of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Jinhua 321004,China)
  • Received:2014-12-08 Online:2015-12-15 Published:2015-12-15

摘要: 对于单模式匹配Boyer-Moore(BM)算法,为提高首字符的不匹配率和失配窗口的最大移动距离,结合BM系列改进算法的设计思想,提出一种高效算法Skii-BM。在Q(x)函数基础上引入窗口竞争思想,以极大化跳跃距离。实验结果表明,改进算法能减少不必要的匹配过程,提高窗 口移动速度,从而改善匹配效率。

关键词: 模式匹配, Boyer-Moore算法, 特征字符, 窗口竞争, Q函数

Abstract: For the single pattern matching algorithm Boyer-Moore(BM),improvement always starts from increasing the mismatching rate of first character and maximizing the move distance of the mismatched window.Absorbing the design thoughts of BM improving algorithm,this paper presents an efficient algorithm Skii-BM,which introduces an idea of window competition based on Q(x) function to maximize the jump distance.Experimental results show that such improvement can reduce unnecessary comparison,and speed up window moving through above measures,to improve the matching efficiency.

Key words: pattern matching, Boyer-Moore(BM) algorithm, characteristic character, window competition, Q function

中图分类号: