基于KMP算法在電力信息智能決策專家庫系統中的應用分析

尹昭舜 錢秋明 郭坤 段彭圓

摘要：調控一體化實施后，調度直面監控，對設備參數、監控信號的質量和處置提出更高要求，如何規范、完整、準確、快速地從這些信號中挑選出調度集中監控需要的信號，變成一個難題。本文立足于普洱電力信息智能決策專家庫系統，在新（改/擴）建的信號審核中以及在運站梳理的信號處置中運用了KMP算法，極大地增加了信號匹配通過率，提高了系統的實用性。

Abstract： After the implementation of integrated regulation and control， the dispatching faces up to the monitoring and puts forward higher requirements on the quality and disposal of equipment parameters， monitoring signals. How to select the signals needed for centralized monitoring from these signals in a standardized， complete， accurate and fast manner becomes a difficult problem. Based on the intelligent decision expert database system of Puer electric power information， this paper uses KMP algorithm in the signal audit of new （change/expand） construction and in the signal disposal of carding of transportation station， which greatly increases the pass rate of signal matching and improves the practicability of the system.

關鍵詞：規范;監控信號;智能決策專家庫系統;KMP算法

Key words： standardized;pilot signal;information intelligent decision-making expert database system;KMP algorithm

中圖分類號：TM76 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1006-4311（2020）17-0225-04

0 ?引言

隨著世界經濟的飛速發展，人類對電力資源的需求越來越多，社會對電力資源的依賴越來越高。變電站作為輸送電力資源重要環節之一，其有效運轉極大的保障人們對電力資源的需求;通過變電站設備的信號，技術人員能更好的了解變電站的運行情況，同時也能很好的管理變電站。因此，統一、規范的信號顯得尤為重要。

目前，變電站數量較多，不同變電站之間信號有較大差異。南網調控一體化實施后，調度直面監控，如何更好的規范、統一設備信號，提高變電站的管理效率、促進調控一體化進程顯得十分重要，電力信息智能決策專家庫系統的出現便是為了解決這一難題。

電力信息智能決策專家庫系統的主要功能是規范、統一信號，系統信號審核與處置模塊利用KMP匹配算法，將原始信號與標準信號進行匹配，生成標準、規范的信號，從而促進調控一體化的后續推進。

1 ?KMP算法概述

1.1 KMP字符串匹配算法任務概述

字符串匹配任務，就是從一個主串中找到與模式串相同的部分，并且返回它的位置，可以通過便利的方法暴力實現，成為BF算法，即 brute force （暴力算法）。暴力算法是如何實現的——如果主串中的一部分已經匹配好了模式串中的一部分，當下一個char不匹配的時候，就需要重新匹配，即主串與模式串的對齊為位置不變的前提下，模式串的第一個char的位置往右移動一格，然后對齊，重新對比。因此，對于主串中比較的那個指針來說，這實際是有一個主串指針回溯的過程。所謂的KMP算法是對暴力求解的一種改進，它可避免指針回溯，同時可保留前面匹配成功的字符。

1.2 KMP算法解析與實現

KMP算法主要是通過消除主串指針的回溯來提高匹配的效率的，其核心思想是它提取并運用了加速匹配的信息。而這種信息可以理解為：對于模式串t的每個元素tj，都有一個實數k，并且讓模式串t開頭的k個字符（t0 t1…t k-1）依次與tj前面的 k（tj-k ?tj-k+1…tj-1，因為第一個字符 tj-k至少從t1開始，所以j>k）個字符相同。在這個匹配中，如果k值有多個，則取最大的一個。因為模式串 t 中每個位置 j 的字符都有這種信息，采用 next 數組表示，即 next[j]=MAX{k}。其代碼運算為：

利用代碼公式求解出next的數組后，就可以進行KMP的算法匹配，其方法如圖1-圖3。

設定標串：s，指針為 i;模式串：t，指針為j。

其中圖1表示：“si-j～si-1”等于“t0～tj-1”，si不等于tj（前面相等，比較到 tj時不相等）并且next[j]==k。

圖2表示根據 next 數組的定義得知 “tk～tj-1”等于“t0～tk-1”，所以 “t0～tk-1”等于“si-k～si-1”。

因此，KMP算法可提高匹配的準確率，加快匹配速度。

2 ?基于KMP算法與設備信號匹配

設備信號作為反映配電設備狀態的關鍵信息，在配電自動化應用中具有極其重要的作用，電力信息智能決策專家庫系統主要用于規范、統一設備信號，KMP算法運用在系統中體現在原始信號與標準信號的匹配，主要包含兩個功能模塊：設備信號自動審核和設備信號處置。

2.1 設備信號審核與KMP算法

每個變電站都有一份點表，即設備信號，該點表由電網公司自動化來設計，參考一個標準，但由于每個地方的人員都有自己的編制習慣，因此生成的點表便存在差異，從而導致信號不規范、不統一。電力信息智能決策專家庫系統的信號編制規則是根據國家電力公司相關規范來實現，所以它生成統一、規范的信號。而信號在編制過程中需要審核，即設備原始信號與標準信號進行匹配，該匹配運用了KMP匹配算法。設標準信號tj有k個元素，如標準信號“110kV母差保護裝置運行異常”，其元素可拆分為“110kV”、“母差”、“保護”、“裝置”、“運行”、“異常”，此處k值等于6;原始信號有多個k元素組成。信號審核中，要求原始信號與標準信號完全一致才會自動審核，即tj=tk、j=k，如圖4。

當tj=tk時，可知必然有t0…tk-1等于tj-k…tj-1，此時的 k 是相同子串的長度。

因為 t0…tk-1=tj-k…tj-1，

且tj= tk，

進而 t0…tk=tj-k…tj，

所以next[j+1]=k+1。

在信號自動審核中，所有滿足 next[j+1]=k+1的原始信號都會自動審核，無需手動審核，這一部分審核會占據大量信號，使得需要手動審核的信號減少，這極大的減少了工作量，提高了效率。

2.2 在運站設備信號處置與KMP算法

調控一體化實施后，要求信號實現規范與統一。目前，設備信號繁多、差異較大，即使相同電壓等級，同間隔設備下的信號也會有所差異。電力信息智能決策專家庫系統出現后，很好的解決了這個問題，該系統的在運站梳理模塊將原始信號重新梳理，梳理完成后會生成新版的信號，該版本信號規范、統一、符合電網相關信號規范條例。

在運站梳理中，其重要環節之一便是信號處置，即原始信號與標準信號之間的匹配處置，該環節同樣運用了KMP算法。信號處置與信號審核有所不同，信號審核中，原始信號與標準信號之間差異較小，而信號處置中，信號之間的差異較大，因此，信號處置將從三個方面分析如何運用KMP算法：

①原始信號與標準信號元素數量相同，即tj=tk，該情況與信號審核相同，原始信號與標準信號完全相同，即兩條信號內容描述一致，匹配度（相似度）為“100%”，滿足條件，該類信號會自動處置。

②標準信號元素數量多余原始信號，如標準信號“寶峰變500kV大寶Ⅱ回線/500kV寶峰玉溪Ⅱ回線5082斷路器A相斷路器”，其元素為“寶峰變”“500kV”“大寶”“Ⅱ回線”“寶峰玉溪”……原始信號“寶峰玉溪Ⅱ回線5082斷路器”其元素為“寶峰玉溪”“Ⅱ回線”……同樣，此處設標準信號為tj，其元素數量為k;tk為原始信號，其表示具有一個或多個標準信號元素。上述兩個信號進行處置時，原始信號的元素會與標準信號進行匹配，其匹配順序與KMP匹配算法中t[j] ！=t[k]的情況相同，以圖5為解釋。

當t[j] ！= t[k]時，已知當 t[j]=t[k] 時，可知next[j+1] = k+1，所以next[j+1] < k，此時匹配指針需要不斷往后移，直到匹配到完全重合的元素或匹配結束，如圖5所示：標準信號“寶峰變”可用圖中“ABAC”表示，“寶峰玉溪”用“ABAB”表示;原始信號“寶峰玉溪”同樣用“ABAB”表示。匹配開始時，原始信號的元素會優先從t0位置開始匹配，“寶峰玉溪”與“寶峰變”有相似成分，其相似度可記為“75%”;同時“寶峰玉溪會”往后移動一個位置進行匹配，記錄相似度，最后保留最高相似度元素。當原始信號的所有元素匹配完畢后，統計每個元素最高相似度然后整合，最后得出的相似度便是原始信號與標準信號的相似度，若相似度為“100%”或達到客戶需求指定值，則信號自動處置;若低于“100%”或客戶需求指定值，則需要客戶手動審核確認。

③標準信號元素數量少于原始信號，即標準信號為tj，原始信號為tk+a。其匹配方法與第二種況相同，匹配完成后進行相應處置即可。

同時，標準信號與原始信號匹配中，還有關鍵字段做關聯限制，即關鍵元素。如“裝置告警”與“裝置異常”，二者字面匹配相似度為“50%”，實際上二者為完全不同的信號，設置關鍵字“告警”后，二者相似度實際為“0%”。

3 ?系統算法測試

本節主要是針對基于KMP算法在電力信息智能決策專家庫系統中模擬實際數據進行實驗測試，其中包括信號審核的算法測試、在運站梳理的信號處置的算法測試，實驗的目的是為了測試設備信號自動審核、信號處置匹配通過率的實際效果。

3.1 信號審核的算法測試

本小節實驗的目的是為了測試設備信號自動審核通過率的實際效果。

實驗測試采用以下操作步驟：

①模擬現場實際的信號環境;

②通過KMP算法，實現原始信號與標準信號自動匹配;

③與標準信號匹配一致的原始信號實現自動審核通過，形成規范統一信號。

以下將結合實驗測試數據進行具體的分析，為了對KMP算法進行驗證，在系統的環境中測試了2種不同的自動審核結果，其中第1種情況為自動審核通過的狀態，即原始信號與標準信號自動匹配一致，審核通過;第2種情況為自動審核未通過的狀態，即原始信號與標準信號自動匹配不一致，未能審核通過。其結果如表1、表2所示。

表1、表2中給出了2種不同原始信號與標準信號自動匹配審核通過與未通過的測試結果，從表1中可以看出，原始信號與標準信號描述一致，二者信號不存在任何差異，即自動匹配后審核通過，與第1種情況吻合;從表2中可以看出，原始信號與標準信號描述不一致，二者信號存在著一定的差異，即自動匹配后未能通過審核，與第2種情況吻合。

通過KMP算法，根據原始信號與標準信號自動匹配，二者信號的描述一致即能自動審核通過，描述不一致的信號即自動匹配后未能通過審核，即印證了該算法的功能效果，以達到實驗前期的預期效果，亦能生成相應的規范性信號。

3.2 在運站信號處置的算法測試

本小節實驗的目的是為了測試設備信號處置匹配通過率的實際效果。

實驗測試采用以下操作步驟：

①模擬現場實際的信號環境;

②通過KMP算法，實現原始信號與標準信號匹配的相似度;

③根據相似度進行設備信號的處置，按照標準信號規范最終實現信號的規范統一。

下面將結合實驗測試數據進行具體分析，為了對KMP算法進行驗證，在系統的環境中測試了3種不同的匹配相似度，其中第1種匹配情況的相似度為100%，即原始信號與標準信號匹配一致;第2種匹配情況的相似度為一定的范圍內，即大于等于1%且小于等于99%，原始信號與標準信號二者的描述有所差異，存在一定的相似度;第3種匹配情況的相似度為0%，即原始信號與標準信號二者的描述間不存在相似度，標準信號庫中無與原始信號匹配的標準信號，或原始信號中未匹配到相對應的標準信號。其結果如表3-表5所示。

表3、表4、表5中給出了3種不同原始信號與標準信號匹配相似度的測試結果，從表3中可以看出，原始信號與標準信號的匹配相似度為100%，二者信號描述一致，與第1種匹配情況吻合;從表4中可以看出，原始信號與標準信號的匹配相似度在1%-99%范圍內，二者的信號描述存在一定的差異，所以相似度在該范圍之內，與第2種匹配情況吻合;從表5中可以看出，原始信號與標準信號的匹配相似度為0%，二者信號描述不存在相似度，即標準信號庫中無與原始信號匹配的標準信號，或者是原始信號中未找到與之對應匹配的標準信號，與第3種匹配情況吻合。

同時，為了進一步確認KMP算法在處置信號上的實際效果，實驗采取隨機抽樣的抽查方法，隨機抽取10個變電站（變電站包含不同電壓等級與不同電站類型），將10個變電站的信號表導入在運站梳理中，對其進行模擬處置，分別是采用KMP算法與為采用KMP算法后的處置效果，其統計結果如表6、表7所示。

通過表6中可知：原始信號與標準信號相似度為100%的信號僅占3.16%，由此可知原始信號與標準信號之間差異較大;其中80%到100%之間的信號占比較多，通過人工處置后發現，該區間原始信號與標準信號存在描述差異，但均能匹配標準信號;相似度為60%-80%之間的信號與標準信號便不能完全匹配，所以針對該區間信號，我們還需要其他算法來進行輔助，促進信號處置;當信號低于60%時，其處置率較低，需要人工處置信號。

通過對比表6與表7，兩者在信號匹配度與自動處置率上都存在差異，KMP算法效果更優，所以，采用KMP算法，能提高信號匹配度與自動處置率。

通過KMP算法，根據原始信號與標準信號匹配的相似度來進行處置設備的信號，生成相對應的規范信號。

4 ?結論

本文通過KMP匹配算法在電力信息智能決策專家庫系統的研究，從KMP算法原理，信號審核與信號處置運用匹配算法原理以及通過實際數據測試，證明KMP算法在系統中對于信號的審核與信號處置上起到了極其關鍵的作用。電力信息智能決策專家庫系統運用了KMP算法，精準匹配信號，加快了信號的審核與處置，減少了用戶工作量，使信號規范統一，促進了調控一體化進程。

參考文獻：

[1]肖海.南網方略：構筑南網主心骨[J].企業文明，2007（012）：62-64.

[2]楊冠軍，郭文杰，劉琪，等.輸變電設備集中監控信息專家庫建設[J].電力安全技術，2018，020（007）：33-37.

[3]李靜.字符串的模式匹配算法——基于KMP算法的討論[J].青島科技大學學報（自然科學版），2002，023（2）：78-80.

[4]韓光輝，曾誠.KMP算法的理論研究[J].微電子學與計算機，2013，30（4）：36-39.

[5]周雅翠，孫磊.基于KMP算法的next函數理解與分析[J].吉林建筑大學學報，2012，029（1）：79-82.

[6]陳媛.算法與數據結構[M].清華大學出版社，2005.

[7]Gauri Kalnoor;Jayashree Agarkhed ?Procedia Computer Science， 2018-1.

[8]D'Amico Randy S; Zanazzi George; Hargus Gunnar; Dyster Timothy; Chan Shirley; Lignelli-Dipple Angela; Wang Tony J C; Faust Phyllis L; McKhann Guy M ?Journal of neurosurgery ?2018-2.