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

王友钊，黄 冬

(浙江大学数字技术及仪器研究所，杭州 310027)

1 概述

在框架网络数据结构环境下，在线式微机防误系统各设备的具体信息均以字符串的形式存于系统文件中，在字符串匹配方面存在“同前缀或同后缀的待匹配字符串多、同后缀比同前缀的待匹配字符串少”等特点。落实到搜索设备的具体信息时，需要使用字符串匹配算法进行实现。

目前在字符串匹配方面使用最多的 3种算法是字符串顺序匹配法算法、经典前缀匹配KMP算法与经典后缀匹配BM算法[1]，经实验对比后得知：BM算法在提高匹配速度上比其余 2种算法性能更好，更适合在微机防误系统框架网络数据结构环境中应用。但 BM 算法也存在不足：其好后缀规则在理论上效果好，但在应用中作用小，反而增加了算法的总运行时间，影响了算法的性能。

为进一步缩短算法的匹配时间，提高系统搜索效率，本文在研究了目前多种应用广泛的BM改进算法后[2-3]，分析并提出一种BM改进算法——WBM算法，去除传统的好后缀规则、并对坏字符规则进行改进，构建出适合系统维护的框架网络数据结构，并将 WBM 算法运用于该数据结构，融合Visual C++语言(VC++)，以微机防误系统软件的形式实现了WBM算法的实际应用。

2 框架网络数据结构的描述、构建与优化

框架网络是一种适用于在线式微机防误系统维护的数据结构环境，能够提高知识在计算机中存储、检索、使用和修改的效率，从而节省系统维护的时间[4]。

作为分析和改进 BM 算法的环境基础，本文分步构建了框架网络数据结构：(1)通过框架表示法描述设备与逻辑的参数与信息[5]；(2)通过框架、槽与侧面的横向与纵向联系[6]，构建了框架网络结构。

在线式微机防误系统的整体框架网络结构模型如图 1所示。

在接到点击设备操作的消息后，推理机首先在生成的逻辑知识库框架网络中搜寻该设备拉合条件框架，随后在一次设备电路图框架网络中寻取相对应基础框架的设备信息字符串，最后进行比对、做出判断。

图1 在线式微机防误系统的整体框架网络结构模型

在建立框架网络数据结构的基础上，本文采用并结合2种方式对整体框架网络数据结构进行优化与改进，进一步节省了微机防误系统的知识搜索时间，提高了搜索效率与可维护性：

(1)网络维度参数控制法。在系统整体框架网络中增加网络维度控制参数，系统先将写成TXT文件的防误逻辑程序读入系统，生成“逻辑知识库”框架网络的同时，形成网络维度参数，自动控制系统在“一次设备电路图”框架网络结构中搜索知识的层次，与单纯的从首层到底层遍历“一次设备电路图”框架网络相比，减少对不必要层次的搜索，能够明显提高搜索效率。

(2)同步准备法。在读取“逻辑知识库”的逻辑程序、生成框架网络的同时，对“一次设备电路图”框架网络进行分层。减少在“一次设备电路图”框架网络中搜索知识的准备时间，从而加快系统的搜索速度。

3 BM算法的研究与改进

3.1 微机防误系统中字符串匹配算法的分析

在线式微机防误系统中各设备的具体信息均以字符串的形式存于系统文件中，落实到搜索基础框架中的具体信息时，需要使用字符串匹配算法进行实现。

设备信息文本串与模式串“DeviceState=1”相比存在以下特点：许多待匹配字符串具有相同前缀或相同后缀，例如“Device”、“=1”等，而相同后缀比相同前缀的字符串少。例如：“刀闸2”的一系列信息以字符串的形式存储如下：

随着微机防误系统维护中各设备信息量的增加，搜索时间必然会越来越长，这就会降低系统的整体效率，不利于系统软件可维护性的提高。而且各设备如刀闸(DZ)、断路器(DLQ)、变压器(BYQ)等的具体信息由于不同设备的属性各异，因此在字符串中的存储顺序也是不同的。如在搜索前通过程序先将全部信息按顺序进行排序，工程量巨大，且浪费时间。

因此，针对以上维护中会出现的问题，要寻找一种字符串匹配算法实现快速搜索，在搜索时无需改动设备具体信息的存储方式，并且在字符串增多同样长度的情况下搜索时间更少，从而在系统可维护性方面能够尽量减少设备信息量的增加对搜索效率的降低程度。

本文研究了在字符串匹配方面使用最多的 3种算法：字符串顺序匹配法算法，经典前缀匹配KMP算法与经典后缀匹配BM算法，并针对微机防误系统设计实验进行对比。如图 2所示，在微机防误系统框架网络数据结构环境的应用中，BM 算法在提高匹配速度上比其余 2种算法性能更好，而且随着字符串长度的增加，优势更加明显。

图2 3种算法在框架网络结构环境中应用性能的比较

3.2 BM算法的改进

以上研究与实验证明，后缀比较的 BM 算法更加适合在微机防误系统网络框架数据结构环境的应用。为进一步缩短算法的匹配时间，本文对 BM 算法进行了的研究与改进，改进后的新的字符串匹配算法称为WJFW BM算法，简称为WBM算法。

3.2.1 WBM算法的实现步骤

本文将 WBM 算法的实现步骤分为预处理、初始于匹配这2个阶段：

(1)预处理阶段

计算 Badchar1[c]和 Badchar2[c](c为字符集∑上的字符)。

Badchar1函数为BM算法中的坏字符函数，计算方法如下：

其中，P[m]为用于对比的模式字符串；m为对比时模式串的绝对距离长度值，下同。

本文的Badchar2[c]函数在Badchar1[c]函数基础上有小的改变，计算方法如下：

(2)初始位置和匹配方向

匹配开始后，模式串 P[m]的左端与设备信息文本串的左端对齐，字符的比较由模式串的末端对齐处文本字符T[m-1]开始从右向左进行；先比较P[m-1]与T[i+m-1]，若匹配，再比较P[0]与T[i]，若再次匹配，则再比较中间的字符；发生失配时，模式串从文本的左端向右移动。

本文改进后的算法流程如图3所示。

3.2.2 WBM 算法时间复杂度分析

WBM 算法的最好时间复杂度[7]为 O(n/m)，最坏时间复杂度为O(m·n)。Badchar1最大值为m，Badchar2最大值为 m+1，每次跳跃的字符数取两者中最大者。在模式串 P与文本串T匹配时：每次都跳过m+1个字符，此时时间复杂度为 O(n/m)；另一种情况，每次都跳过一个字符，则文本串中除开始的m-1个字符与最后的m-1个字符外，其余均比较了m+1次，此时时间复杂度为O(m·n)。

4 实验项目设计与算法验证

该系统的部分实现界面图如图4所示。

图4 电路设备图的绘制、增加、清空和修改界面图

本文利用框架理论构建了在线式微机防误系统元件参数的结构模型，运用面向对象的编程语言VC++为编程工具，通过框架理论与VC++的融合，采用有界深度优先搜索法与 WBM 字符串匹配算法，实现了一个维护性好和搜索效率高的在线式微机防误系统。其中，本文使用的有界深度优先搜索法派生于深度优先搜索法[8]，基本思想是：在深度优先搜索的基础上，设定搜索深度的界限(类似网络维度参数)，在搜索深度达到限定值而仍未找到目标节点时，换一个分支继续搜索，直到搜索到为止，适合微机防误系统的知识高效搜索。

4.1 改进算法的实验与比对

为测试当设备信息字符串长度、模式串在文本串中所处位置等条件发生改变时WBM、BM等算法的性能表现，针对本文3.1节中提出要解决的问题，进行了同硬件环境下的实验设计，思想如下：

(1)研究并测试在目标字符串增多同样长度的情况下搜索时间更少的算法。

(2)研究并测试模式串处于文本串不同位置的情况下搜索时间更少的算法。

(3)采用多次搜索(10000次)记录总时间，最后取平均值的方法提高精确度。

综合以上设计思想，本文选取BM算法、WBM算法进行主要比对，并引入BMH算法、QS算法[9]作为参照比对，总共对4种算法进行实验，测试项目与数据结果如表1所示。

表1 经整理后的算法实验项目与结果

为了更好地对比展现 4种算法的性能，经专业数学计算软件Matlab等对实验结果数据的分析，4种算法的性能如图5所示。从多组实验对比以及图5的结果可以看到，在微机防误系统网络框架数据结构环境中，WBM算法在性能上比BM算法有明显提高，较BMH和QS算法也有一定的提高。同样都是改进算法，WBM算法总的比对时间相比BMH与QS有一定程度的减少，且随着模式串的增加，效果更明显。

图5 4种算法在框架网络结构环境中应用的性能比较

4.2 WBM算法与框架网络结合后的横向比对

本文还选取了语义网络表示法、面向对象表示法和逻辑表示法进行微机防误软件的实现，对这 4种表示法在系统搜索时间、维护速度等方面进行了横向的分析与比对。

本文通过使用专业程序效率检验软件 EQATEC Profiler、EQATEC Tracer、Load Runner、PC-Lint、QAC[10]等对结合BM算法的原始框架网络表示法、结合BM算法的优化框架网络表示法、结合 WBM 算法的优化框架网络表示法、语义网络表示法、面向对象表示法和逻辑表示法实现的在线式微机防误系统进行了比对，对其代码量、搜索时间、搜索准确度、可维护性(增加、删除、修改、全部重写)、占用磁盘空间、占用 CPU和内存大小等性能，通过20次同硬件同任务测试取平均值的方式进行具体的比较，实验结果如表2所示[11-12]。

表2 4种表示法提高系统可维护性的效果对比

从以上客观比较可以看出，针对提高在线式微机防误系统可维护性的问题，本文结合 WBM 算法的优化框架网络表示法在同种表示方法中最为适合，其搜索时间最短、搜索准确度最高，所占系统硬件资源少，能较大地提升知识在计算机中存储、检索、使用和修改的效率，对在线式微机防误系统的可维护性提高效果好。

5 结束语

本文分析并提出一种面向微机防误的 BM 改进算法——WBM算法，针对该环境下的微机防误系统在字符串匹配方面具有“同前缀或同后缀的待匹配字符串多、同后缀比同前缀的待匹配字符串少”等特点，对 BM 算法的好后缀、坏字符规则进行研究与改进；构建出在线式微机防误系统的框架网络实验环境，通过对BM、WBM、BMH、QS这4种算法的比对，证明了WBM算法在微机防误系统应用中，缩短知识匹配时间的效果最好。今后将继续深入研究框架网络数据结构环境下的搜索算法，提高算法效率，从而进一步缩短搜索时间，提升系统的可移植性。

[1]Antoniou P, Iliopoulos C S, Mouchard L, et al.Algorithms for Mapping Short Degenerate and Weighted Sequences to a Reference Genome[J].International Journal of Computational Biology and Drug Design, 2009, 2(4): 385-397.

[2]吴 峰.Snort入侵检测系统中 BM算法的研究与改进[D].成都: 西南交通大学, 2010.

[3]何 畏.快速精确字符串匹配算法研究[D].合肥: 合肥工业大学, 2010.

[4]Wan H, Wong K P, Chung C Y.Multi-agent Application in Protection Coordination of Power System with Distributed Generations[C]//Proc.of Power and Energy Society General Meeting——Conversion and Delivery of Electrical Energy in the 21st Century.Pittsburgh, USA: IEEE Press, 2008: 1-6.

[5]陈小红, 尹 斌, 金 芝.基于问题框架的需求建模: 一种本体制导的方法[J].软件学报, 2011, 22(2): 177-194.

[6]谢 锋.基于框架理论的操作票自动生成专家系统[D].武汉: 武汉大学, 2003.

[7]吴红梅.入侵检测系统中模式匹配算法的研究[D].重庆:重庆大学, 2009.

[8]耿汉杰.110 kV变电站操作票自动生成系统研发[D].武汉:武汉大学, 2004.

[9]Pan Wulue, Zhu Bingquan, Qiu Yutao, et al.The Research and Application on Interfacing Technology Between Electronic Current Transformer and Relay Protection[C]//Proc.of International Conference on Advanced Power System Automation and Protection.[S.l.]: IEEE Press, 2011: 422-426.

[10]樊 鹏.基于GPS的SCADA-EMS煤矿供电调度系统的研究[D].阜新: 辽宁工程技术大学, 2009.

[11]Xiang Tieyuan, Wu Hongqing, Xie Feng, et al.The Research and Realization of the Automatically Forming System of Operation Tickets[C]//Proc.of International Conference on Power System Technology.[S.l.]: IEEE Press, 2002: 2140-2144.

[12]Barrada J R, Olea J, Ponsoda V, et al.A Method for the Comparison of Item Selection Rules in Computerized Adaptive Testing[J].Applied Psychological Measurement,2010, 34(6): 438-452.