文献类型：期刊文章

作　　者：王浩[1] 张霖[1] 张庆[1]

机构地区：[1]安徽建筑工业学院信息网络中心,安徽合肥230022

出　　处：《计算机工程与科学》

基　　金：安徽高校省级自然科学研究重点项目(KJ2009A61);安徽高校省级自然科学研究一般项目(KJ2010B041)

年　　份：2012

卷　　号：34

期　　号：3

起止页码：113-117

语　　种：中文

收录情况：BDHX、BDHX2011、CSCD、CSCD2011_2012、ZGKJHX、核心刊

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

关 键 词：模式匹配  双字符序  BM算法 BMHS算法  

分 类 号：TP391]