一種提高系統搜索效率的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.