一种提高系统搜索效率的BM改进算法  

An Improved BM Algorithm for Improving System Search Efficiency

作　　者：王友钊[1] 黄冬[1] 

机构地区：[1]浙江大学数字技术及仪器研究所,杭州310027

出　　处：《计算机工程》2014年第1期63-67,71,共6页Computer Engineering

基　　金：浙江省自然科学基金资助项目(LY12F03012)

摘　　要：针对在线式微机防误系统中字符串匹配的特点以及BM算法匹配性能不足的问题,提出一种BM改进算法——WBM算法,以进一步缩短算法的匹配时间。去掉好后缀规则,适当改进坏字符规则,构建适用于系统维护的框架网络数据结构环境,将WBM算法应用于框架网络,实现基于该算法的微机防误系统软件。实验比对结果表明,WBM算法在BM、WBM、BMH、QS这4种对比算法中速度最快,且同硬件测试CPU使用率为0.76%,应用该算法使搜索时间缩短为3.9 s,搜索准确度提高到99.5%,能明显提高知识在计算机中搜索的效率,与框架网络相结合后,进一步节省了微机防误系统的维护时间。Aiming at the on-line microcomputer anti-misoperation system string matching characteristic and BM algorithm insufficiency, this paper analyzes and puts forward an improved BM algorithm WBM algorithm in order to further shorten the matching time. It removes the good suffix rule, does the appropriate improvement of bad character, and constructs structure environment of network data for system maintenance framework. The WBM algorithm is applied to the frame network, based on the algorithm of microcomputer anti-misoperation system software. Experimental results prove that, WBM algorithm is the fastest in the contrast of four kinds of algorithm, such as BM, WBM, BMH, QS, and in the same hardware test, CPU is used in 0.76%. The application of the algorithm can shorten the search time to 3.9 s, improve search accuracy to 99.5%. It obviously improves the knowledge in computer search efficiency, and by integrated with framework of network, it can further saves microcomputer anti-misoperation system maintenance time.

关 键 词：微机防误系统 字符串匹配 WBM算法 坏字符函数 搜索效率 框架网络 

分 类 号：N945[自然科学总论—系统科学]