计算机工程

• 体系结构与软件技术 • 上一篇    下一篇

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

王友钊,黄 冬   

  1. (浙江大学数字技术及仪器研究所,杭州 310027)
  • 收稿日期:2012-12-25 出版日期:2014-01-15 发布日期:2014-01-13
  • 作者简介:王友钊(1963-),男,副教授,主研方向:智能电网技术,图像识别,机器视觉;黄 冬,硕士研究生
  • 基金项目:
    浙江省自然科学基金资助项目(LY12F03012)

An Improved BM Algorithm for Improving System Search Efficiency

WANG You-zhao, HUANG Dong   

  1. (Institute of Advanced Digital Technology and Instrumentation, Zhejiang University, Hangzhou 310027, China)
  • Received:2012-12-25 Online:2014-01-15 Published:2014-01-13

摘要: 针对在线式微机防误系统中字符串匹配的特点以及BM算法匹配性能不足的问题,提出一种BM改进算法——WBM算法,以进一步缩短算法的匹配时间。去掉好后缀规则,适当改进坏字符规则,构建适用于系统维护的框架网络数据结构环境,将WBM算法应用于框架网络,实现基于该算法的微机防误系统软件。实验比对结果表明,WBM算法在BM、WBM、BMH、QS这4种对比算法中速度最快,且同硬件测试CPU使用率为0.76%,应用该算法使搜索时间缩短为3.9 s,搜索准确度提高到99.5%,能明显提高知识在计算机中搜索的效率,与框架网络相结合后,进一步节省了微机防误系统的维护时间。

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

Abstract: 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.

Key words: microcomputer anti-disoperation system, string matching, WBM algorithm, bad character function, search efficiency, frame network

中图分类号: