基于双字符序检测的BM模式匹配改进算法

• 作者: 张庆 张霖 王浩
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 模式匹配 双字符序 BM算法 BMHS算法
• 年，卷（期）: 2012,（3）
• 所属期刊栏目: 数据挖掘
• 页码范围: 113-117
• 分类号: TP391
• 字数: 4015字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2012.03.021

摘要

BM算法是一类效率较高的单模式匹配算法,通常改进的BM算法往往从提高字符首次不匹配概率和匹配窗口的最大移动距离入手,但为实现此目的所带来的高访存开销使算法实际效率受到影响.DCSBM算法以适当减小关键步长为代价,在利用双宇符序检测提高首次匹配失败概率的同时,对匹配窗口移动关键步长字符距离所需的查表次数和访存次数进行优化.经测试,DCSBM算法显著提高了匹配窗口的平均移动距离.在文本或模式串相对较长情况下,该算法实际测试效率优于BM、BMHS、BMN等算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张霖	安徽建筑工业学院信息网络中心	22	135	4.0	11.0
2	王浩	安徽建筑工业学院信息网络中心	21	63	4.0	7.0
3	张庆	安徽建筑工业学院信息网络中心	11	42	3.0	6.0