一種提高系統(tǒng)搜索效率的BM改進(jìn)算法

王友釗，黃 冬

(浙江大學(xué)數(shù)字技術(shù)及儀器研究所，杭州 310027)

1 概述

在框架網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)環(huán)境下，在線式微機(jī)防誤系統(tǒng)各設(shè)備的具體信息均以字符串的形式存于系統(tǒng)文件中，在字符串匹配方面存在“同前綴或同后綴的待匹配字符串多、同后綴比同前綴的待匹配字符串少”等特點(diǎn)。落實(shí)到搜索設(shè)備的具體信息時(shí)，需要使用字符串匹配算法進(jìn)行實(shí)現(xiàn)。

目前在字符串匹配方面使用最多的 3種算法是字符串順序匹配法算法、經(jīng)典前綴匹配KMP算法與經(jīng)典后綴匹配BM算法[1]，經(jīng)實(shí)驗(yàn)對(duì)比后得知：BM算法在提高匹配速度上比其余 2種算法性能更好，更適合在微機(jī)防誤系統(tǒng)框架網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)環(huán)境中應(yīng)用。但 BM 算法也存在不足：其好后綴規(guī)則在理論上效果好，但在應(yīng)用中作用小，反而增加了算法的總運(yùn)行時(shí)間，影響了算法的性能。

為進(jìn)一步縮短算法的匹配時(shí)間，提高系統(tǒng)搜索效率，本文在研究了目前多種應(yīng)用廣泛的BM改進(jìn)算法后[2-3]，分析并提出一種BM改進(jìn)算法——WBM算法，去除傳統(tǒng)的好后綴規(guī)則、并對(duì)壞字符規(guī)則進(jìn)行改進(jìn)，構(gòu)建出適合系統(tǒng)維護(hù)的框架網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)，并將 WBM 算法運(yùn)用于該數(shù)據(jù)結(jié)構(gòu)，融合Visual C++語(yǔ)言(VC++)，以微機(jī)防誤系統(tǒng)軟件的形式實(shí)現(xiàn)了WBM算法的實(shí)際應(yīng)用。

2 框架網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)的描述、構(gòu)建與優(yōu)化

框架網(wǎng)絡(luò)是一種適用于在線式微機(jī)防誤系統(tǒng)維護(hù)的數(shù)據(jù)結(jié)構(gòu)環(huán)境，能夠提高知識(shí)在計(jì)算機(jī)中存儲(chǔ)、檢索、使用和修改的效率，從而節(jié)省系統(tǒng)維護(hù)的時(shí)間[4]。

作為分析和改進(jìn) BM 算法的環(huán)境基礎(chǔ)，本文分步構(gòu)建了框架網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)：(1)通過(guò)框架表示法描述設(shè)備與邏輯的參數(shù)與信息[5]；(2)通過(guò)框架、槽與側(cè)面的橫向與縱向聯(lián)系[6]，構(gòu)建了框架網(wǎng)絡(luò)結(jié)構(gòu)。

在線式微機(jī)防誤系統(tǒng)的整體框架網(wǎng)絡(luò)結(jié)構(gòu)模型如圖 1所示。

在接到點(diǎn)擊設(shè)備操作的消息后，推理機(jī)首先在生成的邏輯知識(shí)庫(kù)框架網(wǎng)絡(luò)中搜尋該設(shè)備拉合條件框架，隨后在一次設(shè)備電路圖框架網(wǎng)絡(luò)中尋取相對(duì)應(yīng)基礎(chǔ)框架的設(shè)備信息字符串，最后進(jìn)行比對(duì)、做出判斷。

圖1 在線式微機(jī)防誤系統(tǒng)的整體框架網(wǎng)絡(luò)結(jié)構(gòu)模型

在建立框架網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，本文采用并結(jié)合2種方式對(duì)整體框架網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化與改進(jìn)，進(jìn)一步節(jié)省了微機(jī)防誤系統(tǒng)的知識(shí)搜索時(shí)間，提高了搜索效率與可維護(hù)性：

(1)網(wǎng)絡(luò)維度參數(shù)控制法。在系統(tǒng)整體框架網(wǎng)絡(luò)中增加網(wǎng)絡(luò)維度控制參數(shù)，系統(tǒng)先將寫(xiě)成TXT文件的防誤邏輯程序讀入系統(tǒng)，生成“邏輯知識(shí)庫(kù)”框架網(wǎng)絡(luò)的同時(shí)，形成網(wǎng)絡(luò)維度參數(shù)，自動(dòng)控制系統(tǒng)在“一次設(shè)備電路圖”框架網(wǎng)絡(luò)結(jié)構(gòu)中搜索知識(shí)的層次，與單純的從首層到底層遍歷“一次設(shè)備電路圖”框架網(wǎng)絡(luò)相比，減少對(duì)不必要層次的搜索，能夠明顯提高搜索效率。

(2)同步準(zhǔn)備法。在讀取“邏輯知識(shí)庫(kù)”的邏輯程序、生成框架網(wǎng)絡(luò)的同時(shí)，對(duì)“一次設(shè)備電路圖”框架網(wǎng)絡(luò)進(jìn)行分層。減少在“一次設(shè)備電路圖”框架網(wǎng)絡(luò)中搜索知識(shí)的準(zhǔn)備時(shí)間，從而加快系統(tǒng)的搜索速度。

3 BM算法的研究與改進(jìn)

3.1 微機(jī)防誤系統(tǒng)中字符串匹配算法的分析

在線式微機(jī)防誤系統(tǒng)中各設(shè)備的具體信息均以字符串的形式存于系統(tǒng)文件中，落實(shí)到搜索基礎(chǔ)框架中的具體信息時(shí)，需要使用字符串匹配算法進(jìn)行實(shí)現(xiàn)。

設(shè)備信息文本串與模式串“DeviceState=1”相比存在以下特點(diǎn)：許多待匹配字符串具有相同前綴或相同后綴，例如“Device”、“=1”等，而相同后綴比相同前綴的字符串少。例如：“刀閘2”的一系列信息以字符串的形式存儲(chǔ)如下：

隨著微機(jī)防誤系統(tǒng)維護(hù)中各設(shè)備信息量的增加，搜索時(shí)間必然會(huì)越來(lái)越長(zhǎng)，這就會(huì)降低系統(tǒng)的整體效率，不利于系統(tǒng)軟件可維護(hù)性的提高。而且各設(shè)備如刀閘(DZ)、斷路器(DLQ)、變壓器(BYQ)等的具體信息由于不同設(shè)備的屬性各異，因此在字符串中的存儲(chǔ)順序也是不同的。如在搜索前通過(guò)程序先將全部信息按順序進(jìn)行排序，工程量巨大，且浪費(fèi)時(shí)間。

因此，針對(duì)以上維護(hù)中會(huì)出現(xiàn)的問(wèn)題，要尋找一種字符串匹配算法實(shí)現(xiàn)快速搜索，在搜索時(shí)無(wú)需改動(dòng)設(shè)備具體信息的存儲(chǔ)方式，并且在字符串增多同樣長(zhǎng)度的情況下搜索時(shí)間更少，從而在系統(tǒng)可維護(hù)性方面能夠盡量減少設(shè)備信息量的增加對(duì)搜索效率的降低程度。

本文研究了在字符串匹配方面使用最多的 3種算法：字符串順序匹配法算法，經(jīng)典前綴匹配KMP算法與經(jīng)典后綴匹配BM算法，并針對(duì)微機(jī)防誤系統(tǒng)設(shè)計(jì)實(shí)驗(yàn)進(jìn)行對(duì)比。如圖 2所示，在微機(jī)防誤系統(tǒng)框架網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)環(huán)境的應(yīng)用中，BM 算法在提高匹配速度上比其余 2種算法性能更好，而且隨著字符串長(zhǎng)度的增加，優(yōu)勢(shì)更加明顯。

圖2 3種算法在框架網(wǎng)絡(luò)結(jié)構(gòu)環(huán)境中應(yīng)用性能的比較

3.2 BM算法的改進(jìn)

以上研究與實(shí)驗(yàn)證明，后綴比較的 BM 算法更加適合在微機(jī)防誤系統(tǒng)網(wǎng)絡(luò)框架數(shù)據(jù)結(jié)構(gòu)環(huán)境的應(yīng)用。為進(jìn)一步縮短算法的匹配時(shí)間，本文對(duì) BM 算法進(jìn)行了的研究與改進(jìn)，改進(jìn)后的新的字符串匹配算法稱(chēng)為WJFW BM算法，簡(jiǎn)稱(chēng)為WBM算法。

3.2.1 WBM算法的實(shí)現(xiàn)步驟

本文將 WBM 算法的實(shí)現(xiàn)步驟分為預(yù)處理、初始于匹配這2個(gè)階段：

(1)預(yù)處理階段

計(jì)算 Badchar1[c]和 Badchar2[c](c為字符集∑上的字符)。

Badchar1函數(shù)為BM算法中的壞字符函數(shù)，計(jì)算方法如下：

其中，P[m]為用于對(duì)比的模式字符串；m為對(duì)比時(shí)模式串的絕對(duì)距離長(zhǎng)度值，下同。

本文的Badchar2[c]函數(shù)在Badchar1[c]函數(shù)基礎(chǔ)上有小的改變，計(jì)算方法如下：

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

匹配開(kāi)始后，模式串 P[m]的左端與設(shè)備信息文本串的左端對(duì)齊，字符的比較由模式串的末端對(duì)齊處文本字符T[m-1]開(kāi)始從右向左進(jìn)行；先比較P[m-1]與T[i+m-1]，若匹配，再比較P[0]與T[i]，若再次匹配，則再比較中間的字符；發(fā)生失配時(shí)，模式串從文本的左端向右移動(dòng)。

本文改進(jìn)后的算法流程如圖3所示。

3.2.2 WBM 算法時(shí)間復(fù)雜度分析

WBM 算法的最好時(shí)間復(fù)雜度[7]為 O(n/m)，最壞時(shí)間復(fù)雜度為O(m·n)。Badchar1最大值為m，Badchar2最大值為 m+1，每次跳躍的字符數(shù)取兩者中最大者。在模式串 P與文本串T匹配時(shí)：每次都跳過(guò)m+1個(gè)字符，此時(shí)時(shí)間復(fù)雜度為 O(n/m)；另一種情況，每次都跳過(guò)一個(gè)字符，則文本串中除開(kāi)始的m-1個(gè)字符與最后的m-1個(gè)字符外，其余均比較了m+1次，此時(shí)時(shí)間復(fù)雜度為O(m·n)。

4 實(shí)驗(yàn)項(xiàng)目設(shè)計(jì)與算法驗(yàn)證

該系統(tǒng)的部分實(shí)現(xiàn)界面圖如圖4所示。

圖4 電路設(shè)備圖的繪制、增加、清空和修改界面圖

本文利用框架理論構(gòu)建了在線式微機(jī)防誤系統(tǒng)元件參數(shù)的結(jié)構(gòu)模型，運(yùn)用面向?qū)ο蟮木幊陶Z(yǔ)言VC++為編程工具，通過(guò)框架理論與VC++的融合，采用有界深度優(yōu)先搜索法與 WBM 字符串匹配算法，實(shí)現(xiàn)了一個(gè)維護(hù)性好和搜索效率高的在線式微機(jī)防誤系統(tǒng)。其中，本文使用的有界深度優(yōu)先搜索法派生于深度優(yōu)先搜索法[8]，基本思想是：在深度優(yōu)先搜索的基礎(chǔ)上，設(shè)定搜索深度的界限(類(lèi)似網(wǎng)絡(luò)維度參數(shù))，在搜索深度達(dá)到限定值而仍未找到目標(biāo)節(jié)點(diǎn)時(shí)，換一個(gè)分支繼續(xù)搜索，直到搜索到為止，適合微機(jī)防誤系統(tǒng)的知識(shí)高效搜索。

4.1 改進(jìn)算法的實(shí)驗(yàn)與比對(duì)

為測(cè)試當(dāng)設(shè)備信息字符串長(zhǎng)度、模式串在文本串中所處位置等條件發(fā)生改變時(shí)WBM、BM等算法的性能表現(xiàn)，針對(duì)本文3.1節(jié)中提出要解決的問(wèn)題，進(jìn)行了同硬件環(huán)境下的實(shí)驗(yàn)設(shè)計(jì)，思想如下：

(1)研究并測(cè)試在目標(biāo)字符串增多同樣長(zhǎng)度的情況下搜索時(shí)間更少的算法。

(2)研究并測(cè)試模式串處于文本串不同位置的情況下搜索時(shí)間更少的算法。

(3)采用多次搜索(10000次)記錄總時(shí)間，最后取平均值的方法提高精確度。

綜合以上設(shè)計(jì)思想，本文選取BM算法、WBM算法進(jìn)行主要比對(duì)，并引入BMH算法、QS算法[9]作為參照比對(duì)，總共對(duì)4種算法進(jìn)行實(shí)驗(yàn)，測(cè)試項(xiàng)目與數(shù)據(jù)結(jié)果如表1所示。

表1 經(jīng)整理后的算法實(shí)驗(yàn)項(xiàng)目與結(jié)果

為了更好地對(duì)比展現(xiàn) 4種算法的性能，經(jīng)專(zhuān)業(yè)數(shù)學(xué)計(jì)算軟件Matlab等對(duì)實(shí)驗(yàn)結(jié)果數(shù)據(jù)的分析，4種算法的性能如圖5所示。從多組實(shí)驗(yàn)對(duì)比以及圖5的結(jié)果可以看到，在微機(jī)防誤系統(tǒng)網(wǎng)絡(luò)框架數(shù)據(jù)結(jié)構(gòu)環(huán)境中，WBM算法在性能上比BM算法有明顯提高，較BMH和QS算法也有一定的提高。同樣都是改進(jìn)算法，WBM算法總的比對(duì)時(shí)間相比BMH與QS有一定程度的減少，且隨著模式串的增加，效果更明顯。

圖5 4種算法在框架網(wǎng)絡(luò)結(jié)構(gòu)環(huán)境中應(yīng)用的性能比較

4.2 WBM算法與框架網(wǎng)絡(luò)結(jié)合后的橫向比對(duì)

本文還選取了語(yǔ)義網(wǎng)絡(luò)表示法、面向?qū)ο蟊硎痉ê瓦壿嫳硎痉ㄟM(jìn)行微機(jī)防誤軟件的實(shí)現(xiàn)，對(duì)這 4種表示法在系統(tǒng)搜索時(shí)間、維護(hù)速度等方面進(jìn)行了橫向的分析與比對(duì)。

本文通過(guò)使用專(zhuān)業(yè)程序效率檢驗(yàn)軟件 EQATEC Profiler、EQATEC Tracer、Load Runner、PC-Lint、QAC[10]等對(duì)結(jié)合BM算法的原始框架網(wǎng)絡(luò)表示法、結(jié)合BM算法的優(yōu)化框架網(wǎng)絡(luò)表示法、結(jié)合 WBM 算法的優(yōu)化框架網(wǎng)絡(luò)表示法、語(yǔ)義網(wǎng)絡(luò)表示法、面向?qū)ο蟊硎痉ê瓦壿嫳硎痉▽?shí)現(xiàn)的在線式微機(jī)防誤系統(tǒng)進(jìn)行了比對(duì)，對(duì)其代碼量、搜索時(shí)間、搜索準(zhǔn)確度、可維護(hù)性(增加、刪除、修改、全部重寫(xiě))、占用磁盤(pán)空間、占用 CPU和內(nèi)存大小等性能，通過(guò)20次同硬件同任務(wù)測(cè)試取平均值的方式進(jìn)行具體的比較，實(shí)驗(yàn)結(jié)果如表2所示[11-12]。

表2 4種表示法提高系統(tǒng)可維護(hù)性的效果對(duì)比

從以上客觀比較可以看出，針對(duì)提高在線式微機(jī)防誤系統(tǒng)可維護(hù)性的問(wèn)題，本文結(jié)合 WBM 算法的優(yōu)化框架網(wǎng)絡(luò)表示法在同種表示方法中最為適合，其搜索時(shí)間最短、搜索準(zhǔn)確度最高，所占系統(tǒng)硬件資源少，能較大地提升知識(shí)在計(jì)算機(jī)中存儲(chǔ)、檢索、使用和修改的效率，對(duì)在線式微機(jī)防誤系統(tǒng)的可維護(hù)性提高效果好。

5 結(jié)束語(yǔ)

本文分析并提出一種面向微機(jī)防誤的 BM 改進(jìn)算法——WBM算法，針對(duì)該環(huán)境下的微機(jī)防誤系統(tǒng)在字符串匹配方面具有“同前綴或同后綴的待匹配字符串多、同后綴比同前綴的待匹配字符串少”等特點(diǎn)，對(duì) BM 算法的好后綴、壞字符規(guī)則進(jìn)行研究與改進(jìn)；構(gòu)建出在線式微機(jī)防誤系統(tǒng)的框架網(wǎng)絡(luò)實(shí)驗(yàn)環(huán)境，通過(guò)對(duì)BM、WBM、BMH、QS這4種算法的比對(duì)，證明了WBM算法在微機(jī)防誤系統(tǒng)應(yīng)用中，縮短知識(shí)匹配時(shí)間的效果最好。今后將繼續(xù)深入研究框架網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)環(huán)境下的搜索算法，提高算法效率，從而進(jìn)一步縮短搜索時(shí)間，提升系統(tǒng)的可移植性。

[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入侵檢測(cè)系統(tǒng)中 BM算法的研究與改進(jìn)[D].成都: 西南交通大學(xué), 2010.

[3]何 畏.快速精確字符串匹配算法研究[D].合肥: 合肥工業(yè)大學(xué), 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]陳小紅, 尹 斌, 金 芝.基于問(wèn)題框架的需求建模: 一種本體制導(dǎo)的方法[J].軟件學(xué)報(bào), 2011, 22(2): 177-194.

[6]謝 鋒.基于框架理論的操作票自動(dòng)生成專(zhuān)家系統(tǒng)[D].武漢: 武漢大學(xué), 2003.

[7]吳紅梅.入侵檢測(cè)系統(tǒng)中模式匹配算法的研究[D].重慶:重慶大學(xué), 2009.

[8]耿漢杰.110 kV變電站操作票自動(dòng)生成系統(tǒng)研發(fā)[D].武漢:武漢大學(xué), 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煤礦供電調(diào)度系統(tǒng)的研究[D].阜新: 遼寧工程技術(shù)大學(xué), 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.