高效字符匹配算法的研究

摘要：

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

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

所属期刊栏目：46

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家"十一五"科技支撑计划重大项目资助the National Great Project of Scientific and Technical Supporting Programs Funded by Ministry 0f Science & Technology of China During the 11th Five-Tear Plan.2008BAH21803;浙江省科技计划N0.2007C11088;浙江省重大专项2007C11068

在线出版日期：2010-03-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：28-31