基于分层匹配和最长公共子序列的SCD文件比较算法①

徐 睿, 陈宏君, 张 磊, 周 磊, 文继锋

(南京南瑞继保电气有限公司, 南京 211102)

基于分层匹配和最长公共子序列的SCD文件比较算法①

徐 睿, 陈宏君, 张 磊, 周 磊, 文继锋

(南京南瑞继保电气有限公司, 南京 211102)

IEC61850通信已经在电力系统中广泛使用, 其中变电站通信系统使用SCD文件进行描述. SCD文件是XML格式的层次化结构, 不适合直接用文本按行对比来分析差异. 同时由于SCD文件层次结构多, 使用纯结构化的比较方法, 会导致比较结果冗长, 执行效率低. 本文基于SCD文件的特征, 提出了分层匹配的半结构化半文本比较思路. 先按照智能电子设备、连接接入点、逻辑设备等层次结构, 提取关键属性名, 进行对齐匹配. 之后在逻辑设备范围内, 针对逻辑节点的内容, 采用最长公共子序列的匹配算法对比局部文本内容, 该算法可去除仅调整顺序不影响实体内容的无效差异, 比较速度快, 比较结果准确直观.

IEC61850; SCD/ICD文件; 层次比较; 最长公共子序列

IEC61850通信已经在电力系统中被广泛使用, 其中SCD(substation configuration description)文件和ICD(IED capability description)文件在智能变电站的建设过程中起到了至关重要的作用. 由各个设备厂商提供IED设备的ICD文件, 由集成商实例化各个IED设备, 并且配置相关通信参数以及虚端子连接后, 形成全变电站的SCD文件[1,2]. 在整个配置建模的过程中,由于需求的变化或功能的调整, SCD和ICD文件也会发生变化. 因此需要能够方便的对比查看修改前后文件的差异, 便于工程调试和版本管理.

SCD文件采用XML层次结构进行描述, 并且各个层次的节点都具有特定的语义, 如果使用纯文本的比较方法, 难以正确地、清晰地表示文件的差异[3-6].文献[3]提出了一种基于键/值的SCL文件比较方法,即对关键节点定义键值和比较判据, 形成带主键的二维表结构, 比对文件的差异. 文献[4]提出了一种根据每个层次节点的属性遍历查找, 进行比对的方法. 这两种方法都是纯结构化的比较方法, 需要遍历查找整个文件的层次结构. 由于SCD文件结构复杂, 节点层次多, 每个层次的节点所具有的属性都不同, 很难抽象出一种统一的比较模式. 因此结构化的比较方法效率会比较低, 并且对于比较结果的展示不是很直观.

本文提出一种半结构化半文本的比较方法. 首先使用结构化的比较方法比较SCD文件的主体结构, 即不比较所有层次的节点, 只比较Header节点、IED节点、AcessPoint节点、LDevice节点等主干节点. 然后使用基于最长公共子序列的比较算法, 比较逻辑节点的内容. 计算最长公共子序列(Longest Common Subsequence, LCS)的算法在数据差异分析、文件版本控制、生物信息分析、图像处理等方面具有广泛的应用[7-9]. 本文将参与比较的两个逻辑节点的内容转换成两个序列, 通过计算这两个序列最长公共子序列实现对这两个序列的比较, 从而完成逻辑节点内容的比较.使用这种半结构化半文本的比较方法既可以在保持文件主体结构不变的情况下去除仅调整顺序不影响实体内容的无效差异, 又可以快速准确地比较具体内容,直观地展现比较结果.

1 SCD文件结构

SCD/ICD文件采用XML层次化结构描述, 其结构如图1所示, 顶层结构包括: 文件头(Header)、通信配置(Communication)、智能电子设备(IED)、数据模板(DataTypeTemplates)[1].

图1 SCD模型文件层次结构示例图

其中IED是SCD模型文件核心部分(可包括1-N个), IED包括若干连接接入点(AccessPoint), 连接接入点包括若干逻辑设备(LDevice), 逻辑设备由1个公用逻辑节点(LLN0)、代表具体功能的若干逻辑节点(LN)组成. 逻辑节点由若干数据对象实例(DOI)组成, 数据对象由若干数据类的实例组合(DAI)组成.

在数据结构上, SCD和ICD差异体现在IED的个数, 故SCD的比较算法也适用于ICD比较. 本文重点以SCD为例, 介绍实现方案.

2 层次化比较方法

对于两个SCD文件, 使用结构化分层向下的比较方法比较总体结构. 首先把文件按照层次结构进行分层. 然后对于同一层的节点, 以能够区分不同节点的内容作为关键字, 进行查找匹配. 如果查找到对应的节点, 则比较它们的内容以及它们的子节点. 比较子节点时, 同样以能够区分不同节点的内容作为关键字,进行查找匹配, 这样一层层递归向下进行比较. 子节点的比较结果会影响父节点的比较结果.

SCD文件的顶层节点主要包括四个: 文件头(Header)节点、通信配置(Communication)节点、智能电子设备(IED)节点和数据模板(DataTypeTemplates)节点.总体比较流程如图2所示.

图2 SCD文件总体比较流程

对于Header/Communication等内容简单的节点,直接比较它们的属性和内容, 就可以得到两个文件中对应的节点是否相同.

比较IED节点时, 以一个文件中的IED名称作为关键字, 在另一个文件中查找相同名称的IED节点.如果有对应的节点, 则将这两个节点对齐, 并且比较属性和子节点(AccessPoint节点). 如果它们的属性和子节点都相同, 则这两个IED节点被标记为相同. 如果没有对应的节点, 则在没有的文件中插入一个空节点.

比较AccessPoint节点时, 以一个文件中的接入点名称作为关键字, 在另一个文件中的匹配的 IED节点下查找相同名称的AccessPoint节点. 如果有对应的节点, 则将这两个节点对齐, 并且比较属性和子节点(LDevice节点). 如果它们的属性和子节点都相同, 则这两个AccessPoint节点被标记为相同. 如果没有对应的节点, 则在没有的文件中插入一个空节点.

图3 比较AccessPoint节点

比较LDevice节点时, 以一个文件中的逻辑设备实例名作为关键字, 在另一个文件中匹配的AccessPoint节点下查找相同实例名的LDevice节点.如果有对应的节点, 则将这两个节点对齐, 并且比较它们的属性和子节点(LN节点). 如果它们的属性和子节点都相同, 则这两个LDevice节点被标记为相同.如果没有对应的节点, 则在没有的文件中插入一个空节点.

图4 比较LDevice节点

比较LNode节点时, 以一个文件中的逻辑节点的类型+实例号作为关键字, 在另一个文件中对应的LDevice节点下查找具有相同类型+实例号的LNode节点. 如果有对应的节点, 则将这两个节点对齐, 并且比较它们的属性和内容, 使用下一节介绍的方法进行比较. 如果它们的属性和内容都相同, 则这两个LNode节点被标记为相同. 如果没有对应的节点, 则在没有的文件中插入一个空节点.

图5 比较LNode节点

对于DataTypeTemplates节点, 分别比较它的四个子节点(LNodeType节点、DOType节点、DAType节点和EnumType节点)的内容. 由于这四个子节点的层次不是很深, 所以仍然使用层次化的比较方法. 比较时分别使用各个节点ID属性作为关键字进行查找匹配,如果查找到对应的节点, 则进一步比较它们的属性和内容.

3 基于最长公共子序列的逻辑节点比较算法

由于逻辑节点(LN)由多个DO节点组成, DO节点由多个DA节点组成, DA有由多个基本数据类型节点组成, 并且每一层节点都是使用XML文件格式定义,层次结构较多. 如果仍然使用结构化的方法比较, 比较结果会显得冗长, 比较效率会比较低. 因此使用基于最长公共子序列的文本化比较算法来比较逻辑节点的内容. 首先给出序列、子序列和最长公共子序列的定义.

3.1 概念定义

定义1. 序列: 表示排列成一列的元素列表, 元素之间相对位置是确定的[9].

定义2. 子序列: 由一个序列通过去除某些元素但不破坏余下元素的相对位置而形成的新序列[9].

如果序列A通过删除零个或多个元素可以得到序列B, 那么B就是A的一个子序列.

子序列与子串的的相同之处: 无论B是A的子序列还是子串, A和B中对应的元素出现的顺序是一致的.

子序列与子串的区别: 如果B是A的子串, 那么B中的元素在A中是连续出现的; 而如果B是A的子序列, 那么B中的元素在A中可以不连续出现.

例如: 对于序列“compare”, “par”是一个子串, 同时也是一个子序列, 而“opre”只是一个子序列.

定义3. 最长公共子序列(LCS): 序列A和序列B的最长公共子序列就是在两个序列中都出现的子序列中的最长的一个子序列[9].

比较两个逻辑节点的内容时, 实际上是比较两段文本的内容. 可以把每一段文本类比成一个序列, 文本中的每一行类比成一个元素. 那么比较两个逻辑节点的问题就可以转化为比较两个序列的问题. 比较两段文本时希望找出两段文本中最多的匹配部分, 也就是要找出两个序列中最多的匹配部分. 因此可以通过计算两个序列的最长公共子序列(LCS), 来找到这两个序列的最多匹配部分.

定义4. LCS(A, B): 表示序列A和序列B的最长公共子序列的长度.

假设序列A = a1a2……aM, 即A是由a1a2……aM这M个元素顺序组成. a1a2……ai表示A的前i个元素组成的子序列.

假设序列B = b1b2……bN, 即B是由b1b2……bN这N个元素顺序组成. b1b2……bj表示B的前j个元素组成的子序列.

定义5. LCS(i, j): 表示序列A的前i个元素组成的子序列a1a2……ai和序列B的前j个元素组成的子序列b1b2……bj的最长公共子序列的长度.

即LCS(i, j) = LCS(a1a2……ai, b1b2……bj), 其中1≤ i ≤ M, 1 ≤ j ≤ N.

那么LCS(M, N) = LCS(a1a2……aM, b1b2……bN) = LCS(A, B).

3.2 计算最长公共子序列

假设序列A和序列B的最长公共子序列为S = s1s2……sK

若aM= bN,

则sK= aM= bN, 且s1s2……sK-1是a1a2……aM-1和b1b2……bN-1的最长公共子序列.

此时LCS(M, N) = LCS(M-1, N-1)+1

若aM≠ bN, sK≠ aM, sK= bN,

则s1s2……sK是a1a2……aM-1和b1b2……bN的最长公共子序列.

此时LCS(M, N) = LCS(M-1, N)

若aM≠ bN, 且sK= aM, sK≠ bN,

则s1s2……sK是a1a2……aM和b1b2……bN-1的最长公共子序列.

此时LCS(M, N) = LCS(M, N-1)

若aM≠ bN, 且sK≠ aM, sK≠ bN,

则s1s2……sK是a1a2……aM-1和b1b2……bN-1的最长公共子序列.

此时LCS(M, N) = LCS(M-1, N-1)

由数学归纳法的思想可以得到如下计算公式:

＜公式一＞ 对于1≤ i ≤N, 1≤ j ≤M,

若ai= bj, 则LCS(i, j) = LCS(i-1, j-1) + 1

若ai≠ bj, 则LCS(i, j) = Max(LCS(i-1, j-1), LCS(i-1, j), LCS(i, j-1))

由以上计算方法可以得出: 序列A和序列B的最长公共子序列是由A的子序列和B的子序列的最长公共子序列所决定的. 因此需要计算A的所有子序列和B的所有子序列之间一一对应的最长公共子序列, 这样才能获得A和B的最长公共子序列.

3.3 计算匹配矩阵

对于序列A和序列B, 定义一个M*N的匹配矩阵来计算A和B中所有子序列的最长公共子序列的长度.矩阵中第i行、第j列的元素值即表示A的子序列a1a2……ai和B的子序列b1b2……bj的最长公共子序列的长度.

假设序列A = GGATCGA, 序列B = GATTCAGTTA. 定义匹配矩阵, 并将矩阵中的第0列和第0行的元素值初始化为0, 然后从矩阵的左上角到右下角, 根据＜公式一＞依次计算第1行第1列至第7行第11列的各个元素值, 计算结果如图6所示.

图6 计算匹配矩阵

3.4 计算回溯路径

计算得到两个序列的匹配矩阵后, 再从矩阵的右下角往左上角进行回溯. 假设当前位于矩阵的第i行第j列, 则根据＜公式一＞得到的回溯规则如下:

若ai= bj, 则回溯到当前元素的左上角元素.

若ai≠ bj, 则回溯到当前元素的左上角元素、上边元素和左边元素中值最大的一个. 若存在相等的情况,则可以取其中的任意一个.

若当前元素位于矩阵的第一行, 则回溯到当前元素的左边元素.

若当前元素位于矩阵的第一列, 则回溯到当前元素的上边元素.

依据回溯规则对匹配矩阵进行回溯, 得到一条回溯路径如图7所示.

图7 回溯匹配矩阵

3.5 根据回溯路径获得最优匹配

根据回溯路径, 可以计算得到序列A和序列B的分别对应的具有最多公共部分的匹配序列A’和B’. 序列A’和B’表示了原始序列A和B的一个最优匹配, 即在对应位置上具有最多相同内容.

沿着回溯路径(图7中黄色的部分)从右下角往左上角移动, 假设当前元素位于矩阵的第i行第j列.

如果回溯路径上的下一个元素在当前元素的左上角(第i-1行第j-1列), 则将ai-1添加到A’的开始位置,将bj-1添加到B’ 的开始位置.

如果回溯路径上的下一个元素在当前元素的左边(第i行第j-1列), 则将一个空元素添加到A’ 的开始位置, 将bj-1添加到B’ 的开始位置.

如果回溯路径上的下一个元素在当前元素的上边(第i-1行第j列), 则将ai-1添加到A’ 的开始位置, 将一个空元素添加到B’ 的开始位置.

按照上述方法, 沿着回溯路径从右下角回溯到左上角后, 就可以得到A’和B’, 分别如下所示, 其中“_”表示一个空元素. 通过序列A’和B’可以直观地看出原始序列A和B的相同部分(并且是最多的相同部分)和不同部分.

这也是比较两个逻辑节点的内容时, 所希望得到的结果. 把逻辑节点的文本内容转化为一个序列, 即文本中的每一行表示一个元素, 如图8所示.

图8 逻辑节点的文本内容转化为序列

然后使用上述基于最长公共子序列的比较算法,可以得到两个逻辑节点内容的比较结果, 即可以得到两个逻辑节点中最多的相同部分, 又可以显示出不同的部分, 并且保留了原有逻辑节点内容的顺序, 进行对齐匹配, 处理流程如图9所示.

图9 逻辑节点内容比较流程

4 算法验证

基于这种结构化比较方法和计算最长公共子序列的文本比较方法相结合的比较方法, 实现了一个SCD文件的比较工具. 工具可以对两个SCD文件进行比较,并且显示总体结构的比较结果, 以及各个节点的详细比较结果, 见附录A. 对于逻辑节点等结构比较复杂,嵌套层次比较多的节点, 使用基于最长公共子序列的文本比较算法进行比较, 比较结果见附录B.

5 结语

本文提出了一种分层的结构化比较和基于最长公共子序列的文本比较相结合的比较算法, 实现了SCD/ICD文件的差异比较和展示. 使用此算法实现的SCD/ICD文件比较功能已经在保护测控装置配套软件PCS-Explorer中使用[10], 已经广泛应用于智能变电站的工程集成中.

1 IEC/TC57. Communication networks and systems for power utility automation-Part 6: Configuration description language for communication in electrical substation related to IEDs. Ed 2.0. 2009.

2 智能变电站调试规范.国家电网公司企业标准,Q/GDW 689-2012,2012.

3 高磊.IEC61850SCL配置文件比对工具的研究与实现.电力系统自动化,2013,20(10):88–91.

4 马杰,李磊,黄德斌,等.智能变电站二次系统全过程管控平台研究与实践.电力系统保护与控制,2013,41(2):67–72.

5 樊陈,倪益民,窦仁晖,等.智能变电站信息模型的讨论.电力系统自动化,2012,36(13):15–19.

6 笃峻,叶翔,王长瑞,等.智能变电站设计配置一体化功能规范研究及工具开发.电力系统自动化,2014,38(20):85–89.

7 Bergroth L, Hakonen H, Raita T. A survey of longest common subsequence algorithms. International Symposium on String Processing & Information Retrieval. 2000. 39–48.

8 曾波,潘少彬,陆璐,等.改进的LCS方法在测试脚本序列比对中的应用.计算机工程与应用,2011,47(35):71–76.

9 Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill, 2001.

10 陈宏君,刘克金,冯亚东,等.新一代保护测控装置配套工具软件设计与应用.电力系统自动化,2013,37(20):92–96.

SCD File Comparison Algorithm Based on Hierarchy Match and Longest Common Subsequence

XU Rui, CHEN Hong-Jun, ZHANG Lei, ZHOU Lei, WEN Ji-Feng
(NR Electric Co. Ltd., Nanjing 211102, China)

IEC61850 communication has been widely used in electric power system, and SCD file is adopted to describe the Substation Communication System. Hierarchical structure of the SCD file is an XML format, making it not suitable for direct text comparison methods. Meanwhile, the levels of SCD file hierarchy are too many for pure structured comparison methods, which make them lack of time and space efficiency. Based on characteristics of the SCD file, this paper proposes a hierarchical combined approach of structured match and text comparison. Firstly, we abstract critical attribute names with hierarchy information of IED/AccessPoint/LDevice and compare the hierarchy correspondently with structured comparison method which is based on critical attributes. Secondly, we compare the content of LNode with what is based on longest common subsequence algorithm. This combined method could remove invalid differences arising by sequence modification, and could complete the comparison much faster with more accurate and straight forward comparison results.

IEC61850; SCD/ICD file; hierarchy match; longest common subsequence

国家电网公司科技项目(DW1600052)

2016-03-26;收到修改稿时间:2016-05-05

10.15888/j.cnki.csa.005506