基于KMP算法在電力信息智能決策專家?guī)煜到y(tǒng)中的應(yīng)用分析

尹昭舜 錢秋明 郭坤 段彭圓

摘要：調(diào)控一體化實(shí)施后，調(diào)度直面監(jiān)控，對(duì)設(shè)備參數(shù)、監(jiān)控信號(hào)的質(zhì)量和處置提出更高要求，如何規(guī)范、完整、準(zhǔn)確、快速地從這些信號(hào)中挑選出調(diào)度集中監(jiān)控需要的信號(hào)，變成一個(gè)難題。本文立足于普洱電力信息智能決策專家?guī)煜到y(tǒng)，在新（改/擴(kuò)）建的信號(hào)審核中以及在運(yùn)站梳理的信號(hào)處置中運(yùn)用了KMP算法，極大地增加了信號(hào)匹配通過(guò)率，提高了系統(tǒng)的實(shí)用性。

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.

關(guān)鍵詞：規(guī)范;監(jiān)控信號(hào);智能決策專家?guī)煜到y(tǒng);KMP算法

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

中圖分類號(hào)：TM76 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)：1006-4311（2020）17-0225-04

0 ?引言

隨著世界經(jīng)濟(jì)的飛速發(fā)展，人類對(duì)電力資源的需求越來(lái)越多，社會(huì)對(duì)電力資源的依賴越來(lái)越高。變電站作為輸送電力資源重要環(huán)節(jié)之一，其有效運(yùn)轉(zhuǎn)極大的保障人們對(duì)電力資源的需求;通過(guò)變電站設(shè)備的信號(hào)，技術(shù)人員能更好的了解變電站的運(yùn)行情況，同時(shí)也能很好的管理變電站。因此，統(tǒng)一、規(guī)范的信號(hào)顯得尤為重要。

目前，變電站數(shù)量較多，不同變電站之間信號(hào)有較大差異。南網(wǎng)調(diào)控一體化實(shí)施后，調(diào)度直面監(jiān)控，如何更好的規(guī)范、統(tǒng)一設(shè)備信號(hào)，提高變電站的管理效率、促進(jìn)調(diào)控一體化進(jìn)程顯得十分重要，電力信息智能決策專家?guī)煜到y(tǒng)的出現(xiàn)便是為了解決這一難題。

電力信息智能決策專家?guī)煜到y(tǒng)的主要功能是規(guī)范、統(tǒng)一信號(hào)，系統(tǒng)信號(hào)審核與處置模塊利用KMP匹配算法，將原始信號(hào)與標(biāo)準(zhǔn)信號(hào)進(jìn)行匹配，生成標(biāo)準(zhǔn)、規(guī)范的信號(hào)，從而促進(jìn)調(diào)控一體化的后續(xù)推進(jìn)。

1 ?KMP算法概述

1.1 KMP字符串匹配算法任務(wù)概述

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

1.2 KMP算法解析與實(shí)現(xiàn)

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

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

設(shè)定標(biāo)串：s，指針為 i;模式串：t，指針為j。

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

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

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

2 ?基于KMP算法與設(shè)備信號(hào)匹配

設(shè)備信號(hào)作為反映配電設(shè)備狀態(tài)的關(guān)鍵信息，在配電自動(dòng)化應(yīng)用中具有極其重要的作用，電力信息智能決策專家?guī)煜到y(tǒng)主要用于規(guī)范、統(tǒng)一設(shè)備信號(hào)，KMP算法運(yùn)用在系統(tǒng)中體現(xiàn)在原始信號(hào)與標(biāo)準(zhǔn)信號(hào)的匹配，主要包含兩個(gè)功能模塊：設(shè)備信號(hào)自動(dòng)審核和設(shè)備信號(hào)處置。

2.1 設(shè)備信號(hào)審核與KMP算法

每個(gè)變電站都有一份點(diǎn)表，即設(shè)備信號(hào)，該點(diǎn)表由電網(wǎng)公司自動(dòng)化來(lái)設(shè)計(jì)，參考一個(gè)標(biāo)準(zhǔn)，但由于每個(gè)地方的人員都有自己的編制習(xí)慣，因此生成的點(diǎn)表便存在差異，從而導(dǎo)致信號(hào)不規(guī)范、不統(tǒng)一。電力信息智能決策專家?guī)煜到y(tǒng)的信號(hào)編制規(guī)則是根據(jù)國(guó)家電力公司相關(guān)規(guī)范來(lái)實(shí)現(xiàn)，所以它生成統(tǒng)一、規(guī)范的信號(hào)。而信號(hào)在編制過(guò)程中需要審核，即設(shè)備原始信號(hào)與標(biāo)準(zhǔn)信號(hào)進(jìn)行匹配，該匹配運(yùn)用了KMP匹配算法。設(shè)標(biāo)準(zhǔn)信號(hào)tj有k個(gè)元素，如標(biāo)準(zhǔn)信號(hào)“110kV母差保護(hù)裝置運(yùn)行異?！?，其元素可拆分為“110kV”、“母差”、“保護(hù)”、“裝置”、“運(yùn)行”、“異?！?，此處k值等于6;原始信號(hào)有多個(gè)k元素組成。信號(hào)審核中，要求原始信號(hào)與標(biāo)準(zhǔn)信號(hào)完全一致才會(huì)自動(dòng)審核，即tj=tk、j=k，如圖4。

當(dāng)tj=tk時(shí)，可知必然有t0…tk-1等于tj-k…tj-1，此時(shí)的 k 是相同子串的長(zhǎng)度。

因?yàn)?t0…tk-1=tj-k…tj-1，

且tj= tk，

進(jìn)而 t0…tk=tj-k…tj，

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

在信號(hào)自動(dòng)審核中，所有滿足 next[j+1]=k+1的原始信號(hào)都會(huì)自動(dòng)審核，無(wú)需手動(dòng)審核，這一部分審核會(huì)占據(jù)大量信號(hào)，使得需要手動(dòng)審核的信號(hào)減少，這極大的減少了工作量，提高了效率。

2.2 在運(yùn)站設(shè)備信號(hào)處置與KMP算法

調(diào)控一體化實(shí)施后，要求信號(hào)實(shí)現(xiàn)規(guī)范與統(tǒng)一。目前，設(shè)備信號(hào)繁多、差異較大，即使相同電壓等級(jí)，同間隔設(shè)備下的信號(hào)也會(huì)有所差異。電力信息智能決策專家?guī)煜到y(tǒng)出現(xiàn)后，很好的解決了這個(gè)問(wèn)題，該系統(tǒng)的在運(yùn)站梳理模塊將原始信號(hào)重新梳理，梳理完成后會(huì)生成新版的信號(hào)，該版本信號(hào)規(guī)范、統(tǒng)一、符合電網(wǎng)相關(guān)信號(hào)規(guī)范條例。

在運(yùn)站梳理中，其重要環(huán)節(jié)之一便是信號(hào)處置，即原始信號(hào)與標(biāo)準(zhǔn)信號(hào)之間的匹配處置，該環(huán)節(jié)同樣運(yùn)用了KMP算法。信號(hào)處置與信號(hào)審核有所不同，信號(hào)審核中，原始信號(hào)與標(biāo)準(zhǔn)信號(hào)之間差異較小，而信號(hào)處置中，信號(hào)之間的差異較大，因此，信號(hào)處置將從三個(gè)方面分析如何運(yùn)用KMP算法：

①原始信號(hào)與標(biāo)準(zhǔn)信號(hào)元素?cái)?shù)量相同，即tj=tk，該情況與信號(hào)審核相同，原始信號(hào)與標(biāo)準(zhǔn)信號(hào)完全相同，即兩條信號(hào)內(nèi)容描述一致，匹配度（相似度）為“100%”，滿足條件，該類信號(hào)會(huì)自動(dòng)處置。

②標(biāo)準(zhǔn)信號(hào)元素?cái)?shù)量多余原始信號(hào)，如標(biāo)準(zhǔn)信號(hào)“寶峰變500kV大寶Ⅱ回線/500kV寶峰玉溪Ⅱ回線5082斷路器A相斷路器”，其元素為“寶峰變”“500kV”“大寶”“Ⅱ回線”“寶峰玉溪”……原始信號(hào)“寶峰玉溪Ⅱ回線5082斷路器”其元素為“寶峰玉溪”“Ⅱ回線”……同樣，此處設(shè)標(biāo)準(zhǔn)信號(hào)為tj，其元素?cái)?shù)量為k;tk為原始信號(hào)，其表示具有一個(gè)或多個(gè)標(biāo)準(zhǔn)信號(hào)元素。上述兩個(gè)信號(hào)進(jìn)行處置時(shí)，原始信號(hào)的元素會(huì)與標(biāo)準(zhǔn)信號(hào)進(jìn)行匹配，其匹配順序與KMP匹配算法中t[j] ！=t[k]的情況相同，以圖5為解釋。

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

③標(biāo)準(zhǔn)信號(hào)元素?cái)?shù)量少于原始信號(hào)，即標(biāo)準(zhǔn)信號(hào)為tj，原始信號(hào)為tk+a。其匹配方法與第二種況相同，匹配完成后進(jìn)行相應(yīng)處置即可。

同時(shí)，標(biāo)準(zhǔn)信號(hào)與原始信號(hào)匹配中，還有關(guān)鍵字段做關(guān)聯(lián)限制，即關(guān)鍵元素。如“裝置告警”與“裝置異?！?，二者字面匹配相似度為“50%”，實(shí)際上二者為完全不同的信號(hào)，設(shè)置關(guān)鍵字“告警”后，二者相似度實(shí)際為“0%”。

3 ?系統(tǒng)算法測(cè)試

本節(jié)主要是針對(duì)基于KMP算法在電力信息智能決策專家?guī)煜到y(tǒng)中模擬實(shí)際數(shù)據(jù)進(jìn)行實(shí)驗(yàn)測(cè)試，其中包括信號(hào)審核的算法測(cè)試、在運(yùn)站梳理的信號(hào)處置的算法測(cè)試，實(shí)驗(yàn)的目的是為了測(cè)試設(shè)備信號(hào)自動(dòng)審核、信號(hào)處置匹配通過(guò)率的實(shí)際效果。

3.1 信號(hào)審核的算法測(cè)試

本小節(jié)實(shí)驗(yàn)的目的是為了測(cè)試設(shè)備信號(hào)自動(dòng)審核通過(guò)率的實(shí)際效果。

實(shí)驗(yàn)測(cè)試采用以下操作步驟：

①模擬現(xiàn)場(chǎng)實(shí)際的信號(hào)環(huán)境;

②通過(guò)KMP算法，實(shí)現(xiàn)原始信號(hào)與標(biāo)準(zhǔn)信號(hào)自動(dòng)匹配;

③與標(biāo)準(zhǔn)信號(hào)匹配一致的原始信號(hào)實(shí)現(xiàn)自動(dòng)審核通過(guò)，形成規(guī)范統(tǒng)一信號(hào)。

以下將結(jié)合實(shí)驗(yàn)測(cè)試數(shù)據(jù)進(jìn)行具體的分析，為了對(duì)KMP算法進(jìn)行驗(yàn)證，在系統(tǒng)的環(huán)境中測(cè)試了2種不同的自動(dòng)審核結(jié)果，其中第1種情況為自動(dòng)審核通過(guò)的狀態(tài)，即原始信號(hào)與標(biāo)準(zhǔn)信號(hào)自動(dòng)匹配一致，審核通過(guò);第2種情況為自動(dòng)審核未通過(guò)的狀態(tài)，即原始信號(hào)與標(biāo)準(zhǔn)信號(hào)自動(dòng)匹配不一致，未能審核通過(guò)。其結(jié)果如表1、表2所示。

表1、表2中給出了2種不同原始信號(hào)與標(biāo)準(zhǔn)信號(hào)自動(dòng)匹配審核通過(guò)與未通過(guò)的測(cè)試結(jié)果，從表1中可以看出，原始信號(hào)與標(biāo)準(zhǔn)信號(hào)描述一致，二者信號(hào)不存在任何差異，即自動(dòng)匹配后審核通過(guò)，與第1種情況吻合;從表2中可以看出，原始信號(hào)與標(biāo)準(zhǔn)信號(hào)描述不一致，二者信號(hào)存在著一定的差異，即自動(dòng)匹配后未能通過(guò)審核，與第2種情況吻合。

通過(guò)KMP算法，根據(jù)原始信號(hào)與標(biāo)準(zhǔn)信號(hào)自動(dòng)匹配，二者信號(hào)的描述一致即能自動(dòng)審核通過(guò)，描述不一致的信號(hào)即自動(dòng)匹配后未能通過(guò)審核，即印證了該算法的功能效果，以達(dá)到實(shí)驗(yàn)前期的預(yù)期效果，亦能生成相應(yīng)的規(guī)范性信號(hào)。

3.2 在運(yùn)站信號(hào)處置的算法測(cè)試

本小節(jié)實(shí)驗(yàn)的目的是為了測(cè)試設(shè)備信號(hào)處置匹配通過(guò)率的實(shí)際效果。

實(shí)驗(yàn)測(cè)試采用以下操作步驟：

①模擬現(xiàn)場(chǎng)實(shí)際的信號(hào)環(huán)境;

②通過(guò)KMP算法，實(shí)現(xiàn)原始信號(hào)與標(biāo)準(zhǔn)信號(hào)匹配的相似度;

③根據(jù)相似度進(jìn)行設(shè)備信號(hào)的處置，按照標(biāo)準(zhǔn)信號(hào)規(guī)范最終實(shí)現(xiàn)信號(hào)的規(guī)范統(tǒng)一。

下面將結(jié)合實(shí)驗(yàn)測(cè)試數(shù)據(jù)進(jìn)行具體分析，為了對(duì)KMP算法進(jìn)行驗(yàn)證，在系統(tǒng)的環(huán)境中測(cè)試了3種不同的匹配相似度，其中第1種匹配情況的相似度為100%，即原始信號(hào)與標(biāo)準(zhǔn)信號(hào)匹配一致;第2種匹配情況的相似度為一定的范圍內(nèi)，即大于等于1%且小于等于99%，原始信號(hào)與標(biāo)準(zhǔn)信號(hào)二者的描述有所差異，存在一定的相似度;第3種匹配情況的相似度為0%，即原始信號(hào)與標(biāo)準(zhǔn)信號(hào)二者的描述間不存在相似度，標(biāo)準(zhǔn)信號(hào)庫(kù)中無(wú)與原始信號(hào)匹配的標(biāo)準(zhǔn)信號(hào)，或原始信號(hào)中未匹配到相對(duì)應(yīng)的標(biāo)準(zhǔn)信號(hào)。其結(jié)果如表3-表5所示。

表3、表4、表5中給出了3種不同原始信號(hào)與標(biāo)準(zhǔn)信號(hào)匹配相似度的測(cè)試結(jié)果，從表3中可以看出，原始信號(hào)與標(biāo)準(zhǔn)信號(hào)的匹配相似度為100%，二者信號(hào)描述一致，與第1種匹配情況吻合;從表4中可以看出，原始信號(hào)與標(biāo)準(zhǔn)信號(hào)的匹配相似度在1%-99%范圍內(nèi)，二者的信號(hào)描述存在一定的差異，所以相似度在該范圍之內(nèi)，與第2種匹配情況吻合;從表5中可以看出，原始信號(hào)與標(biāo)準(zhǔn)信號(hào)的匹配相似度為0%，二者信號(hào)描述不存在相似度，即標(biāo)準(zhǔn)信號(hào)庫(kù)中無(wú)與原始信號(hào)匹配的標(biāo)準(zhǔn)信號(hào)，或者是原始信號(hào)中未找到與之對(duì)應(yīng)匹配的標(biāo)準(zhǔn)信號(hào)，與第3種匹配情況吻合。

同時(shí)，為了進(jìn)一步確認(rèn)KMP算法在處置信號(hào)上的實(shí)際效果，實(shí)驗(yàn)采取隨機(jī)抽樣的抽查方法，隨機(jī)抽取10個(gè)變電站（變電站包含不同電壓等級(jí)與不同電站類型），將10個(gè)變電站的信號(hào)表導(dǎo)入在運(yùn)站梳理中，對(duì)其進(jìn)行模擬處置，分別是采用KMP算法與為采用KMP算法后的處置效果，其統(tǒng)計(jì)結(jié)果如表6、表7所示。

通過(guò)表6中可知：原始信號(hào)與標(biāo)準(zhǔn)信號(hào)相似度為100%的信號(hào)僅占3.16%，由此可知原始信號(hào)與標(biāo)準(zhǔn)信號(hào)之間差異較大;其中80%到100%之間的信號(hào)占比較多，通過(guò)人工處置后發(fā)現(xiàn)，該區(qū)間原始信號(hào)與標(biāo)準(zhǔn)信號(hào)存在描述差異，但均能匹配標(biāo)準(zhǔn)信號(hào);相似度為60%-80%之間的信號(hào)與標(biāo)準(zhǔn)信號(hào)便不能完全匹配，所以針對(duì)該區(qū)間信號(hào)，我們還需要其他算法來(lái)進(jìn)行輔助，促進(jìn)信號(hào)處置;當(dāng)信號(hào)低于60%時(shí)，其處置率較低，需要人工處置信號(hào)。

通過(guò)對(duì)比表6與表7，兩者在信號(hào)匹配度與自動(dòng)處置率上都存在差異，KMP算法效果更優(yōu)，所以，采用KMP算法，能提高信號(hào)匹配度與自動(dòng)處置率。

通過(guò)KMP算法，根據(jù)原始信號(hào)與標(biāo)準(zhǔn)信號(hào)匹配的相似度來(lái)進(jìn)行處置設(shè)備的信號(hào)，生成相對(duì)應(yīng)的規(guī)范信號(hào)。

4 ?結(jié)論

本文通過(guò)KMP匹配算法在電力信息智能決策專家?guī)煜到y(tǒng)的研究，從KMP算法原理，信號(hào)審核與信號(hào)處置運(yùn)用匹配算法原理以及通過(guò)實(shí)際數(shù)據(jù)測(cè)試，證明KMP算法在系統(tǒng)中對(duì)于信號(hào)的審核與信號(hào)處置上起到了極其關(guān)鍵的作用。電力信息智能決策專家?guī)煜到y(tǒng)運(yùn)用了KMP算法，精準(zhǔn)匹配信號(hào)，加快了信號(hào)的審核與處置，減少了用戶工作量，使信號(hào)規(guī)范統(tǒng)一，促進(jìn)了調(diào)控一體化進(jìn)程。

參考文獻(xiàn)：

[1]肖海.南網(wǎng)方略：構(gòu)筑南網(wǎng)主心骨[J].企業(yè)文明，2007（012）：62-64.

[2]楊冠軍，郭文杰，劉琪，等.輸變電設(shè)備集中監(jiān)控信息專家?guī)旖ㄔO(shè)[J].電力安全技術(shù)，2018，020（007）：33-37.

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

[4]韓光輝，曾誠(chéng).KMP算法的理論研究[J].微電子學(xué)與計(jì)算機(jī)，2013，30（4）：36-39.

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

[6]陳媛.算法與數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社，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.