《基于KMP算法在电力信息智能决策专家库系统中的应用分析》-工学论文，工程论文-论文范文参考-科学狗论文网

标题

基于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.

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。