计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (1): 28-31.DOI: 10.3778/j.issn.1002-8331.2010.01.009

• 研究、探讨 • 上一篇    下一篇

高效字符匹配算法的研究

王志伟,平玲娣,陆敏锋   

  1. 浙江大学 计算机科学与技术学院,杭州 310027
  • 收稿日期:2009-07-07 修回日期:2009-08-10 出版日期:2010-01-01 发布日期:2010-01-01
  • 通讯作者: 王志伟

Research on high-performance pattern matching algorithm

WANG Zhi-wei,PING Ling-di,LU Min-feng   

  1. Department of Computer Science and Technology,Zhejiang University,Hangzhou 310027,China
  • Received:2009-07-07 Revised:2009-08-10 Online:2010-01-01 Published:2010-01-01
  • Contact: WANG Zhi-wei

摘要: 在分析BM算法以及它的衍生版本BMH、Sunday等算法的基础上,提出一种新的改进算法。改进算法有三个重要特点:(1)采用双字符启发策略,提高模式串最大移动位数及其概率,最大移动位数为n+2;(2)采用窗口动态分段方法,尽量减少字符匹配次数;(3)建立模式串中相同字符的位置链,充分利用启发字符,降低模式匹配的冗余度。实验结果表明,改进算法具有较高的匹配效率。

关键词: BM算法, 双字符启发, 窗口动态分段, 位置链

Abstract: On the basis of the BM algorithm and its derivative versions:BMH,Sunday and other algorithms,a new improved algorithm is presented.The improved algorithm has three important features:(1)using two-character inspired strategy to improve the pattern moving length and its probability.The largest length is n+2;(2)using the method of dynamic segmentation to minimize the matching;(3)building the chain with the location for the same character in the pattern to take full advantage of inspiring characters and reduce the redundancy of matching.Experimental results show that the improved algorithm has higher matching efficiency.

Key words: Boyer-Moore(BM) algorithm, two-character inspired, dynamic segmentation, location chain

中图分类号: