基于哈希和编辑距离算法的SCD双层向量化与变更校验技术

01SCD配置文件及变更方式1.1

智能变电站SCD组成智能变电站SCD配置文件基于IEC618506标准中智能变电站的配置描述语言（substationconfigurationlanguage，SCL）编写与建模。SCD模型中节点采用树型层次结构，包括头文件描述（Header）、变电站模型（Substation）、通信模型（Communication）、数据类型模板（Datatypetemplates）、智能电子设备模型（intelligentelectronicdevice，IED）5个树枝组成。树枝由分支构成，其分支含有多种枝叶，一般采用SCL元素描述，每种元素通过属性描述解析。1.2

SCD变更方式智能变电站配置文件的差异主要包括配置变更和增减更换，如IED设备的增减和更换、虚端子的变化（变更/增减）、通信方式的变更等，这些差异在SCD文本中，表现为SCD文本相关元素发生修改、增加和删减3种变更操作。当SCD文件发生变更时，3种变更方式及可能出现的结果如表1所示。表1

SCD变更方式Table1

SCDchangemode不同智能变电站对SCD的变更要求不同，针对SCD文件变更，研究准确快速校验技术至关重要。02SCD文本向量化模型计算表面文本相似度实现不同文本的比较可以找到SCD文件变更情况。针对原始文本和发生修改的文本，对字符串序列或字符的组合进行计算处理，得到2个文本的字符匹配程度或距离，作为相似度的评判标准。在文本相似度的计算中常使用基于空间向量模型方法。空间向量模型将文本视为相互独立的词语，根据词语出现的频率，将其作为特征项并赋予不同的权重vi，以所有特征项的权重为分量构成该文本的空间向量模型，修改前后文本T和T′的特征向量可以分别构建为fT=[v1,v2,⋅⋅⋅,vn]，fT′=[v′1,v′2,⋅⋅⋅,v′n]。文构建双层向量模型结构完成SCD文本校验，对SCD文本不再赋予权重值，直接将各部分元素及属性抽象成向量化模型。第一层向量模型判断SCD文本是否存在变化，并作为第二层向量模型校验的启动判据。2.1

SCD校验第一层向量模型SCD文本第一层向量模型由Header、Communication、IED节点元素和CRC校验码组成。2.1.1基于Header部分的第一层向量建模Header部分包含SCD文件的版本信息、修订信息、文件书写工具标识以及名称映射等信息。其中全站CRC校验码只有一种，与全站所有IED虚端子配置相关，任意IED虚端子配置发生变化时CRC都会发生变化。此部分第一层向量模型为式中：n1、n2分别为version和revision元素数目；c为SCD全站虚端子配置CRC校验码。2.1.2

基于Communication部分的第一层向量建模Communication部分发生网络拓扑变化、通信协议更改、硬件设备更换等会使站控层网和过程层网ConnectedAp元素及节点下的GSE和PhysConn元素发生变化。此部分第一层向量模型为式中：n1、n2、n3分别为ConnectedAp、GSE和PhysConn元素的数目。2.1.3

基于IED部分的第一层向量建模IED部分描述了IED的配置情况及其所包含的逻辑装置、逻辑节点、数据对象和所具备的通信服务能力。此部分第一层向量模型为式中：n1、n2、n3、n4分别为IED设备、AccessPoint、LDevice、LN元素的数目。2.1.4

基于CRC校验码的向量化建模IED部分有2种校验码：一种是全站过程层虚端子配置CRC校验码，另一种是IED过程层虚端子配置CRC校验码。此部分第一层向量模型为式中：c1,c2,c3,⋯,cn分别为各IED装置CRC校验码。第一层向量中变更前SCD文本向量记为fk，变更后记为f′k，其中k代表第一层向量模型第k个部分。2.2

SCD校验第二层向量模型在第一层向量模型的基础上，分别对Header、Communication和IED中关键性节点元素部分进行第二层向量模型构建。2.2.1

基于Header部分的第二层向量建模Header部分第二层向量模型为式中：f1,1、f1,2分别为用revision和version元素属性值r1,r2,r3,⋯,rn和v1,v2,v3,⋯,vn构建的向量模型。2.2.2

基于Communication部分的第二层向量建模Communication部分第二层向量模型为式中：f2,1、f2,2分别为用PhysConn和GSE元素的属性值构建的向量模型。2.2.3

基于IED部分的第二层向量建模IED部分第二层向量模型为式中：f3,i为用第i个IED设备构成的向量模型；Ni为第i个IED设备的name属性值；Ai、Di、Li分别为第i个IED设备的AccessPoint、LDevice和LN元素个数；Si、Mi、Gi分别为第i节点inputs中ExtRef属性值。第二层向量模型中变更前后的SCD文本向量分别记为fk,i、f′k,i，其中k,i代表第二层向量模型第k个部分中第i个元素或IED设备。双层向量模型的对应关系如图1所示。图1

双层向量关系框架

Fig.1

Thetwo-layervectorrelationshipframework

03SCD文本校验技术

基于空间向量构建的SCD向量模型需要经过相应处理才可计算相似度，完成对比校验。3.1

基于哈希算法的SCD向量模型处理技术哈希算法是将任意长度的二进制值映射为较短固定长度的二进制值，可以处理复杂的文本，其映射过程为式中：{0,1}*为任意长度的文本位串；{0,1}n为长度为固定值n的二进制位串。哈希算法对SCD文本向量处理的过程为：首先，应用哈希函数对SCD文本向量f检测，确定各向量元素的终止位置，动态调节各向量的长度；然后，逐一扫描向量，应用强哈希函数H计算第i个向量元素的哈希值ti；最后，将所有向量中的哈希值按照先后顺序连接起来，得到哈希向量h=[t1,t2,t3,⋯,tn]，从而完成哈希处理转化。将SCD文本向量f中长度为s的字符串Rs做哈希运算，其函数表达式为式中：Ri为Rs第i个位置上的字符；mod为取模运算。为了更有效处理SCD空间向量，可以利用定长滚动指针对向量中元素逐字节进行滚动哈希计算，提高效率。若长度为s的指针移动到结尾位置a，则计算的哈希值字符串为若指针向后移动一个字节，字符串Rs,a+1为如果已知H(Rs,a)的值，则计算H(Rs,a+1)时，只需从H(Rs,a)中去除Ra−s+1产生的结果，再添加Ra+1的作用结果即可达到滚动计算哈希值的目的。SCD文本向量求解哈希值的过程是对其进行预处理，将SCD文本向量模型转化为哈希向量模型。此向量模型为字符串的形式，因此求解SCD文本相似度问题转化为求解字符串相似度问题。3.2

基于编辑距离算法的向量相似度计算方法编辑距离通过对字符串文本中某个字符进行添加、删减、更换的编辑操作完成相似度比较。经过哈希计算得到的SCD文本向量由字符串组成，先结合编辑距离算法对其进行计算处理得到字符串相似度，再完成SCD文本的校验。取SCD变更前后某一部分的两个哈希向量h和h′中对应的2个哈希值串E和F：E=e1,e2,e3,⋅⋅⋅,em，F=f1,f2,f3,⋅⋅⋅,fn，并分别将其作为第一行和第一列构建关系矩阵L，L表示为式中：元素dij为哈希值串E和F之间的编辑距离，记为L(E,F)，表示哈希值串E变化到哈希值串F所需最少编辑操作次数。经计算得到的各个字符串的编辑距离相加即可得到两个向量h和h′的编辑距离L(h,h′)，则利用字符串相似度公式求出的文本相似度为式中：Ls(h)、Ls(h′)分别为SCD变更前后的哈希向量字符串总长度。3.3

基于回溯路径法的定位校验回溯路径法可以完成SCD变更文本定位校验。即将矩阵右下角元素dmn按一定规则上溯至左上角元素d00时，遍历过的单元格从右下到左上走过的路径，得到匹配结果可完成定位校验。对于字符串P=1349347685和Q=144032745，经过计算可得到L(P,Q)=5，则匹配结果如图2所示。图2中，黑色表示未发生变化，红色表示发生了变化，“_”表示字符增加或者删减。图2

匹配结果

Fig.2

Matchingresults

3.4

SCD文本校验流程SCD文本校验在双层向量模型的基础上完成。首先，对于SCD变更前后的2个文本，选择Header、Communication、IED的相关元素和CRC校验码分别进行第一层向量模型的构建；其次，进行哈希计算得到哈希向量，编辑操作后得到其相似度；最后，判断是否启动第二层SCD校验。结合智能变电站实际情况，由于变更后的SCD文本不会出现大面积的变动，第一层向量计算的相似度设置阈值为0.78，用来作为判断不可能出现的情况。第一层相似度不同情况及操作如表2所示。表2

第一层相似度计算情况及操作Table2

Similaritycalculationandoperationofthefirstlayer根据第一层SCD文本校验情况判断启动第二层SCD文本校验。对判断启动SCD部分进行第二层向量建模，经过哈希和编辑距离处理后计算第二层向量相似度，最后使用回溯路径完成分析校验。SCD文件校验总流程如图3所示。图3

SCD文件校验流程

Fig.3

SCDfileverificationprocess

04算例分析本文结合某500kV智能变电站新旧SCD文件进行对比分析，并选择IED部分进行分析。4.1

IED部分第一层向量校验按照第一层空间向量模型进行构建，得到IED第一层的向量如表3所示。表3

IED第一层向量Table3

TheIEDfirstlayervector经哈希算法处理后IED第一层哈希向量。经编辑距离计算得到的L(h3,h′3)=78，则对第一层IED向量模型进行相似度计算得到的S=0.8972＜1，由表2可知第二层SCD校验启动。4.2

IED部分第二层向量校验按照第二层空间向量模型进行构建，得到IED第二层部分向量如表4所示。表4

IED第二层向量Table4

IEDsecondlayervector选取f3,23和f′3,23向量中的S、M、G的部分节点进行分析。对IED中部分哈希向量进行编辑距离计算和相似度计算，得到的结果如表5所示。表5

各IED向量编辑距离和相似度Table5

TheIEDvectoreditdistanceandsimilarity由表5可知，IED第二层向量模型的相似度范围为0~1。S=0表示IED设备发生了更换；S=1表示IED设备未发生变化；0＜S＜1表示IED设备存在增加、删除和修改的变更操作，可以通过回溯路径来定位判断发生的变更方式。对相似度0＜S＜1的IED设备采用回溯路径定位分析，其变更情况如图4所示（选取部分发生变更的设备，图中变更处箭头指到下层节点）。图4

增加、删减、修改变更情况

Fig.4

Add,subtractandmodifychanges由图4

a)可知，IED的某个设备Inputs节点元素发生了属性增加的变化，变更后的Inputs元素下新增了两列条目。由图4

b)可知，IED的某个设备Inputs节点元素发生了属性删减的变化，变更后的Inputs元素下删除了一列条目。由图4c)可知，IED的某个设备Inputs节点元素发生了属性值更换的变化，变更后的Inputs元素下两列条目发生了更换。4.3

算法模型对比本文选择键-值模型与所构建的向量模型再次对算例中IED部分进行校验并分析对比情况。两模型校验对比情况如图5所示。由图5a)可以看出，向量模型在48s左右第一层向量校验结束，未启动第二层向量校验。而采用键-值模型进行校验所用时间超过了100s，并且处理数据也多于向量模型校验。由图5b)可以看出，在A点之前为向量模型的第一层校验，满足启动条件后进行第二层向量校验，在80s左右校验结束。而采用键-值模型校验所用时间超过了110s，且向量模型校验处理数据也少于键-值模型处理数据。图5

键-值模型和向量模型校验对比

Fig.5

Verificationcomparisonofkey-valuemodelandvectormodel综上所述，采用本文SCD向量模型进行SCD文本校验相比于键-值