徐 睿, 陳宏君, 張 磊, 周 磊, 文繼鋒

(南京南瑞繼保電氣有限公司, 南京 211102)

基于分層匹配和最長(zhǎng)公共子序列的SCD文件比較算法①

徐 睿, 陳宏君, 張 磊, 周 磊, 文繼鋒

(南京南瑞繼保電氣有限公司, 南京 211102)

IEC61850通信已經(jīng)在電力系統(tǒng)中廣泛使用, 其中變電站通信系統(tǒng)使用SCD文件進(jìn)行描述. SCD文件是XML格式的層次化結(jié)構(gòu), 不適合直接用文本按行對(duì)比來(lái)分析差異. 同時(shí)由于SCD文件層次結(jié)構(gòu)多, 使用純結(jié)構(gòu)化的比較方法, 會(huì)導(dǎo)致比較結(jié)果冗長(zhǎng), 執(zhí)行效率低. 本文基于SCD文件的特征, 提出了分層匹配的半結(jié)構(gòu)化半文本比較思路. 先按照智能電子設(shè)備、連接接入點(diǎn)、邏輯設(shè)備等層次結(jié)構(gòu), 提取關(guān)鍵屬性名, 進(jìn)行對(duì)齊匹配. 之后在邏輯設(shè)備范圍內(nèi), 針對(duì)邏輯節(jié)點(diǎn)的內(nèi)容, 采用最長(zhǎng)公共子序列的匹配算法對(duì)比局部文本內(nèi)容, 該算法可去除僅調(diào)整順序不影響實(shí)體內(nèi)容的無(wú)效差異, 比較速度快, 比較結(jié)果準(zhǔn)確直觀.

IEC61850; SCD/ICD文件; 層次比較; 最長(zhǎng)公共子序列

IEC61850通信已經(jīng)在電力系統(tǒng)中被廣泛使用, 其中SCD(substation configuration description)文件和ICD(IED capability description)文件在智能變電站的建設(shè)過(guò)程中起到了至關(guān)重要的作用. 由各個(gè)設(shè)備廠商提供IED設(shè)備的ICD文件, 由集成商實(shí)例化各個(gè)IED設(shè)備, 并且配置相關(guān)通信參數(shù)以及虛端子連接后, 形成全變電站的SCD文件[1,2]. 在整個(gè)配置建模的過(guò)程中,由于需求的變化或功能的調(diào)整, SCD和ICD文件也會(huì)發(fā)生變化. 因此需要能夠方便的對(duì)比查看修改前后文件的差異, 便于工程調(diào)試和版本管理.

SCD文件采用XML層次結(jié)構(gòu)進(jìn)行描述, 并且各個(gè)層次的節(jié)點(diǎn)都具有特定的語(yǔ)義, 如果使用純文本的比較方法, 難以正確地、清晰地表示文件的差異[3-6].文獻(xiàn)[3]提出了一種基于鍵/值的SCL文件比較方法,即對(duì)關(guān)鍵節(jié)點(diǎn)定義鍵值和比較判據(jù), 形成帶主鍵的二維表結(jié)構(gòu), 比對(duì)文件的差異. 文獻(xiàn)[4]提出了一種根據(jù)每個(gè)層次節(jié)點(diǎn)的屬性遍歷查找, 進(jìn)行比對(duì)的方法. 這兩種方法都是純結(jié)構(gòu)化的比較方法, 需要遍歷查找整個(gè)文件的層次結(jié)構(gòu). 由于SCD文件結(jié)構(gòu)復(fù)雜, 節(jié)點(diǎn)層次多, 每個(gè)層次的節(jié)點(diǎn)所具有的屬性都不同, 很難抽象出一種統(tǒng)一的比較模式. 因此結(jié)構(gòu)化的比較方法效率會(huì)比較低, 并且對(duì)于比較結(jié)果的展示不是很直觀.

本文提出一種半結(jié)構(gòu)化半文本的比較方法. 首先使用結(jié)構(gòu)化的比較方法比較SCD文件的主體結(jié)構(gòu), 即不比較所有層次的節(jié)點(diǎn), 只比較Header節(jié)點(diǎn)、IED節(jié)點(diǎn)、AcessPoint節(jié)點(diǎn)、LDevice節(jié)點(diǎn)等主干節(jié)點(diǎn). 然后使用基于最長(zhǎng)公共子序列的比較算法, 比較邏輯節(jié)點(diǎn)的內(nèi)容. 計(jì)算最長(zhǎng)公共子序列(Longest Common Subsequence, LCS)的算法在數(shù)據(jù)差異分析、文件版本控制、生物信息分析、圖像處理等方面具有廣泛的應(yīng)用[7-9]. 本文將參與比較的兩個(gè)邏輯節(jié)點(diǎn)的內(nèi)容轉(zhuǎn)換成兩個(gè)序列, 通過(guò)計(jì)算這兩個(gè)序列最長(zhǎng)公共子序列實(shí)現(xiàn)對(duì)這兩個(gè)序列的比較, 從而完成邏輯節(jié)點(diǎn)內(nèi)容的比較.使用這種半結(jié)構(gòu)化半文本的比較方法既可以在保持文件主體結(jié)構(gòu)不變的情況下去除僅調(diào)整順序不影響實(shí)體內(nèi)容的無(wú)效差異, 又可以快速準(zhǔn)確地比較具體內(nèi)容,直觀地展現(xiàn)比較結(jié)果.

1 SCD文件結(jié)構(gòu)

SCD/ICD文件采用XML層次化結(jié)構(gòu)描述, 其結(jié)構(gòu)如圖1所示, 頂層結(jié)構(gòu)包括: 文件頭(Header)、通信配置(Communication)、智能電子設(shè)備(IED)、數(shù)據(jù)模板(DataTypeTemplates)[1].

圖1 SCD模型文件層次結(jié)構(gòu)示例圖

其中IED是SCD模型文件核心部分(可包括1-N個(gè)), IED包括若干連接接入點(diǎn)(AccessPoint), 連接接入點(diǎn)包括若干邏輯設(shè)備(LDevice), 邏輯設(shè)備由1個(gè)公用邏輯節(jié)點(diǎn)(LLN0)、代表具體功能的若干邏輯節(jié)點(diǎn)(LN)組成. 邏輯節(jié)點(diǎn)由若干數(shù)據(jù)對(duì)象實(shí)例(DOI)組成, 數(shù)據(jù)對(duì)象由若干數(shù)據(jù)類(lèi)的實(shí)例組合(DAI)組成.

在數(shù)據(jù)結(jié)構(gòu)上, SCD和ICD差異體現(xiàn)在IED的個(gè)數(shù), 故SCD的比較算法也適用于ICD比較. 本文重點(diǎn)以SCD為例, 介紹實(shí)現(xiàn)方案.

2 層次化比較方法

對(duì)于兩個(gè)SCD文件, 使用結(jié)構(gòu)化分層向下的比較方法比較總體結(jié)構(gòu). 首先把文件按照層次結(jié)構(gòu)進(jìn)行分層. 然后對(duì)于同一層的節(jié)點(diǎn), 以能夠區(qū)分不同節(jié)點(diǎn)的內(nèi)容作為關(guān)鍵字, 進(jìn)行查找匹配. 如果查找到對(duì)應(yīng)的節(jié)點(diǎn), 則比較它們的內(nèi)容以及它們的子節(jié)點(diǎn). 比較子節(jié)點(diǎn)時(shí), 同樣以能夠區(qū)分不同節(jié)點(diǎn)的內(nèi)容作為關(guān)鍵字,進(jìn)行查找匹配, 這樣一層層遞歸向下進(jìn)行比較. 子節(jié)點(diǎn)的比較結(jié)果會(huì)影響父節(jié)點(diǎn)的比較結(jié)果.

SCD文件的頂層節(jié)點(diǎn)主要包括四個(gè): 文件頭(Header)節(jié)點(diǎn)、通信配置(Communication)節(jié)點(diǎn)、智能電子設(shè)備(IED)節(jié)點(diǎn)和數(shù)據(jù)模板(DataTypeTemplates)節(jié)點(diǎn).總體比較流程如圖2所示.

圖2 SCD文件總體比較流程

對(duì)于Header/Communication等內(nèi)容簡(jiǎn)單的節(jié)點(diǎn),直接比較它們的屬性和內(nèi)容, 就可以得到兩個(gè)文件中對(duì)應(yīng)的節(jié)點(diǎn)是否相同.

比較IED節(jié)點(diǎn)時(shí), 以一個(gè)文件中的IED名稱(chēng)作為關(guān)鍵字, 在另一個(gè)文件中查找相同名稱(chēng)的IED節(jié)點(diǎn).如果有對(duì)應(yīng)的節(jié)點(diǎn), 則將這兩個(gè)節(jié)點(diǎn)對(duì)齊, 并且比較屬性和子節(jié)點(diǎn)(AccessPoint節(jié)點(diǎn)). 如果它們的屬性和子節(jié)點(diǎn)都相同, 則這兩個(gè)IED節(jié)點(diǎn)被標(biāo)記為相同. 如果沒(méi)有對(duì)應(yīng)的節(jié)點(diǎn), 則在沒(méi)有的文件中插入一個(gè)空節(jié)點(diǎn).

比較AccessPoint節(jié)點(diǎn)時(shí), 以一個(gè)文件中的接入點(diǎn)名稱(chēng)作為關(guān)鍵字, 在另一個(gè)文件中的匹配的 IED節(jié)點(diǎn)下查找相同名稱(chēng)的AccessPoint節(jié)點(diǎn). 如果有對(duì)應(yīng)的節(jié)點(diǎn), 則將這兩個(gè)節(jié)點(diǎn)對(duì)齊, 并且比較屬性和子節(jié)點(diǎn)(LDevice節(jié)點(diǎn)). 如果它們的屬性和子節(jié)點(diǎn)都相同, 則這兩個(gè)AccessPoint節(jié)點(diǎn)被標(biāo)記為相同. 如果沒(méi)有對(duì)應(yīng)的節(jié)點(diǎn), 則在沒(méi)有的文件中插入一個(gè)空節(jié)點(diǎn).

圖3 比較AccessPoint節(jié)點(diǎn)

比較LDevice節(jié)點(diǎn)時(shí), 以一個(gè)文件中的邏輯設(shè)備實(shí)例名作為關(guān)鍵字, 在另一個(gè)文件中匹配的AccessPoint節(jié)點(diǎn)下查找相同實(shí)例名的LDevice節(jié)點(diǎn).如果有對(duì)應(yīng)的節(jié)點(diǎn), 則將這兩個(gè)節(jié)點(diǎn)對(duì)齊, 并且比較它們的屬性和子節(jié)點(diǎn)(LN節(jié)點(diǎn)). 如果它們的屬性和子節(jié)點(diǎn)都相同, 則這兩個(gè)LDevice節(jié)點(diǎn)被標(biāo)記為相同.如果沒(méi)有對(duì)應(yīng)的節(jié)點(diǎn), 則在沒(méi)有的文件中插入一個(gè)空節(jié)點(diǎn).

圖4 比較LDevice節(jié)點(diǎn)

比較LNode節(jié)點(diǎn)時(shí), 以一個(gè)文件中的邏輯節(jié)點(diǎn)的類(lèi)型+實(shí)例號(hào)作為關(guān)鍵字, 在另一個(gè)文件中對(duì)應(yīng)的LDevice節(jié)點(diǎn)下查找具有相同類(lèi)型+實(shí)例號(hào)的LNode節(jié)點(diǎn). 如果有對(duì)應(yīng)的節(jié)點(diǎn), 則將這兩個(gè)節(jié)點(diǎn)對(duì)齊, 并且比較它們的屬性和內(nèi)容, 使用下一節(jié)介紹的方法進(jìn)行比較. 如果它們的屬性和內(nèi)容都相同, 則這兩個(gè)LNode節(jié)點(diǎn)被標(biāo)記為相同. 如果沒(méi)有對(duì)應(yīng)的節(jié)點(diǎn), 則在沒(méi)有的文件中插入一個(gè)空節(jié)點(diǎn).

圖5 比較LNode節(jié)點(diǎn)

對(duì)于DataTypeTemplates節(jié)點(diǎn), 分別比較它的四個(gè)子節(jié)點(diǎn)(LNodeType節(jié)點(diǎn)、DOType節(jié)點(diǎn)、DAType節(jié)點(diǎn)和EnumType節(jié)點(diǎn))的內(nèi)容. 由于這四個(gè)子節(jié)點(diǎn)的層次不是很深, 所以仍然使用層次化的比較方法. 比較時(shí)分別使用各個(gè)節(jié)點(diǎn)ID屬性作為關(guān)鍵字進(jìn)行查找匹配,如果查找到對(duì)應(yīng)的節(jié)點(diǎn), 則進(jìn)一步比較它們的屬性和內(nèi)容.

3 基于最長(zhǎng)公共子序列的邏輯節(jié)點(diǎn)比較算法

由于邏輯節(jié)點(diǎn)(LN)由多個(gè)DO節(jié)點(diǎn)組成, DO節(jié)點(diǎn)由多個(gè)DA節(jié)點(diǎn)組成, DA有由多個(gè)基本數(shù)據(jù)類(lèi)型節(jié)點(diǎn)組成, 并且每一層節(jié)點(diǎn)都是使用XML文件格式定義,層次結(jié)構(gòu)較多. 如果仍然使用結(jié)構(gòu)化的方法比較, 比較結(jié)果會(huì)顯得冗長(zhǎng), 比較效率會(huì)比較低. 因此使用基于最長(zhǎng)公共子序列的文本化比較算法來(lái)比較邏輯節(jié)點(diǎn)的內(nèi)容. 首先給出序列、子序列和最長(zhǎng)公共子序列的定義.

3.1 概念定義

定義1. 序列: 表示排列成一列的元素列表, 元素之間相對(duì)位置是確定的[9].

定義2. 子序列: 由一個(gè)序列通過(guò)去除某些元素但不破壞余下元素的相對(duì)位置而形成的新序列[9].

如果序列A通過(guò)刪除零個(gè)或多個(gè)元素可以得到序列B, 那么B就是A的一個(gè)子序列.

子序列與子串的的相同之處: 無(wú)論B是A的子序列還是子串, A和B中對(duì)應(yīng)的元素出現(xiàn)的順序是一致的.

子序列與子串的區(qū)別: 如果B是A的子串, 那么B中的元素在A中是連續(xù)出現(xiàn)的; 而如果B是A的子序列, 那么B中的元素在A中可以不連續(xù)出現(xiàn).

例如: 對(duì)于序列“compare”, “par”是一個(gè)子串, 同時(shí)也是一個(gè)子序列, 而“opre”只是一個(gè)子序列.

定義3. 最長(zhǎng)公共子序列(LCS): 序列A和序列B的最長(zhǎng)公共子序列就是在兩個(gè)序列中都出現(xiàn)的子序列中的最長(zhǎng)的一個(gè)子序列[9].

比較兩個(gè)邏輯節(jié)點(diǎn)的內(nèi)容時(shí), 實(shí)際上是比較兩段文本的內(nèi)容. 可以把每一段文本類(lèi)比成一個(gè)序列, 文本中的每一行類(lèi)比成一個(gè)元素. 那么比較兩個(gè)邏輯節(jié)點(diǎn)的問(wèn)題就可以轉(zhuǎn)化為比較兩個(gè)序列的問(wèn)題. 比較兩段文本時(shí)希望找出兩段文本中最多的匹配部分, 也就是要找出兩個(gè)序列中最多的匹配部分. 因此可以通過(guò)計(jì)算兩個(gè)序列的最長(zhǎng)公共子序列(LCS), 來(lái)找到這兩個(gè)序列的最多匹配部分.

定義4. LCS(A, B): 表示序列A和序列B的最長(zhǎng)公共子序列的長(zhǎng)度.

假設(shè)序列A = a1a2……aM, 即A是由a1a2……aM這M個(gè)元素順序組成. a1a2……ai表示A的前i個(gè)元素組成的子序列.

假設(shè)序列B = b1b2……bN, 即B是由b1b2……bN這N個(gè)元素順序組成. b1b2……bj表示B的前j個(gè)元素組成的子序列.

定義5. LCS(i, j): 表示序列A的前i個(gè)元素組成的子序列a1a2……ai和序列B的前j個(gè)元素組成的子序列b1b2……bj的最長(zhǎng)公共子序列的長(zhǎng)度.

即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 計(jì)算最長(zhǎng)公共子序列

假設(shè)序列A和序列B的最長(zhǎng)公共子序列為S = s1s2……sK

若aM= bN,

則sK= aM= bN, 且s1s2……sK-1是a1a2……aM-1和b1b2……bN-1的最長(zhǎng)公共子序列.

此時(shí)LCS(M, N) = LCS(M-1, N-1)+1

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

則s1s2……sK是a1a2……aM-1和b1b2……bN的最長(zhǎng)公共子序列.

此時(shí)LCS(M, N) = LCS(M-1, N)

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

則s1s2……sK是a1a2……aM和b1b2……bN-1的最長(zhǎng)公共子序列.

此時(shí)LCS(M, N) = LCS(M, N-1)

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

則s1s2……sK是a1a2……aM-1和b1b2……bN-1的最長(zhǎng)公共子序列.

此時(shí)LCS(M, N) = LCS(M-1, N-1)

由數(shù)學(xué)歸納法的思想可以得到如下計(jì)算公式:

＜公式一＞ 對(duì)于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))

由以上計(jì)算方法可以得出: 序列A和序列B的最長(zhǎng)公共子序列是由A的子序列和B的子序列的最長(zhǎng)公共子序列所決定的. 因此需要計(jì)算A的所有子序列和B的所有子序列之間一一對(duì)應(yīng)的最長(zhǎng)公共子序列, 這樣才能獲得A和B的最長(zhǎng)公共子序列.

3.3 計(jì)算匹配矩陣

對(duì)于序列A和序列B, 定義一個(gè)M*N的匹配矩陣來(lái)計(jì)算A和B中所有子序列的最長(zhǎng)公共子序列的長(zhǎng)度.矩陣中第i行、第j列的元素值即表示A的子序列a1a2……ai和B的子序列b1b2……bj的最長(zhǎng)公共子序列的長(zhǎng)度.

假設(shè)序列A = GGATCGA, 序列B = GATTCAGTTA. 定義匹配矩陣, 并將矩陣中的第0列和第0行的元素值初始化為0, 然后從矩陣的左上角到右下角, 根據(jù)＜公式一＞依次計(jì)算第1行第1列至第7行第11列的各個(gè)元素值, 計(jì)算結(jié)果如圖6所示.

圖6 計(jì)算匹配矩陣

3.4 計(jì)算回溯路徑

計(jì)算得到兩個(gè)序列的匹配矩陣后, 再?gòu)木仃嚨挠蚁陆峭笊辖沁M(jìn)行回溯. 假設(shè)當(dāng)前位于矩陣的第i行第j列, 則根據(jù)＜公式一＞得到的回溯規(guī)則如下:

若ai= bj, 則回溯到當(dāng)前元素的左上角元素.

若ai≠ bj, 則回溯到當(dāng)前元素的左上角元素、上邊元素和左邊元素中值最大的一個(gè). 若存在相等的情況,則可以取其中的任意一個(gè).

若當(dāng)前元素位于矩陣的第一行, 則回溯到當(dāng)前元素的左邊元素.

若當(dāng)前元素位于矩陣的第一列, 則回溯到當(dāng)前元素的上邊元素.

依據(jù)回溯規(guī)則對(duì)匹配矩陣進(jìn)行回溯, 得到一條回溯路徑如圖7所示.

圖7 回溯匹配矩陣

3.5 根據(jù)回溯路徑獲得最優(yōu)匹配

根據(jù)回溯路徑, 可以計(jì)算得到序列A和序列B的分別對(duì)應(yīng)的具有最多公共部分的匹配序列A’和B’. 序列A’和B’表示了原始序列A和B的一個(gè)最優(yōu)匹配, 即在對(duì)應(yīng)位置上具有最多相同內(nèi)容.

沿著回溯路徑(圖7中黃色的部分)從右下角往左上角移動(dòng), 假設(shè)當(dāng)前元素位于矩陣的第i行第j列.

如果回溯路徑上的下一個(gè)元素在當(dāng)前元素的左上角(第i-1行第j-1列), 則將ai-1添加到A’的開(kāi)始位置,將bj-1添加到B’ 的開(kāi)始位置.

如果回溯路徑上的下一個(gè)元素在當(dāng)前元素的左邊(第i行第j-1列), 則將一個(gè)空元素添加到A’ 的開(kāi)始位置, 將bj-1添加到B’ 的開(kāi)始位置.

如果回溯路徑上的下一個(gè)元素在當(dāng)前元素的上邊(第i-1行第j列), 則將ai-1添加到A’ 的開(kāi)始位置, 將一個(gè)空元素添加到B’ 的開(kāi)始位置.

按照上述方法, 沿著回溯路徑從右下角回溯到左上角后, 就可以得到A’和B’, 分別如下所示, 其中“_”表示一個(gè)空元素. 通過(guò)序列A’和B’可以直觀地看出原始序列A和B的相同部分(并且是最多的相同部分)和不同部分.

這也是比較兩個(gè)邏輯節(jié)點(diǎn)的內(nèi)容時(shí), 所希望得到的結(jié)果. 把邏輯節(jié)點(diǎn)的文本內(nèi)容轉(zhuǎn)化為一個(gè)序列, 即文本中的每一行表示一個(gè)元素, 如圖8所示.

圖8 邏輯節(jié)點(diǎn)的文本內(nèi)容轉(zhuǎn)化為序列

然后使用上述基于最長(zhǎng)公共子序列的比較算法,可以得到兩個(gè)邏輯節(jié)點(diǎn)內(nèi)容的比較結(jié)果, 即可以得到兩個(gè)邏輯節(jié)點(diǎn)中最多的相同部分, 又可以顯示出不同的部分, 并且保留了原有邏輯節(jié)點(diǎn)內(nèi)容的順序, 進(jìn)行對(duì)齊匹配, 處理流程如圖9所示.

圖9 邏輯節(jié)點(diǎn)內(nèi)容比較流程

4 算法驗(yàn)證

基于這種結(jié)構(gòu)化比較方法和計(jì)算最長(zhǎng)公共子序列的文本比較方法相結(jié)合的比較方法, 實(shí)現(xiàn)了一個(gè)SCD文件的比較工具. 工具可以對(duì)兩個(gè)SCD文件進(jìn)行比較,并且顯示總體結(jié)構(gòu)的比較結(jié)果, 以及各個(gè)節(jié)點(diǎn)的詳細(xì)比較結(jié)果, 見(jiàn)附錄A. 對(duì)于邏輯節(jié)點(diǎn)等結(jié)構(gòu)比較復(fù)雜,嵌套層次比較多的節(jié)點(diǎn), 使用基于最長(zhǎng)公共子序列的文本比較算法進(jìn)行比較, 比較結(jié)果見(jiàn)附錄B.

5 結(jié)語(yǔ)

本文提出了一種分層的結(jié)構(gòu)化比較和基于最長(zhǎng)公共子序列的文本比較相結(jié)合的比較算法, 實(shí)現(xiàn)了SCD/ICD文件的差異比較和展示. 使用此算法實(shí)現(xiàn)的SCD/ICD文件比較功能已經(jīng)在保護(hù)測(cè)控裝置配套軟件PCS-Explorer中使用[10], 已經(jīng)廣泛應(yīng)用于智能變電站的工程集成中.

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 智能變電站調(diào)試規(guī)范.國(guó)家電網(wǎng)公司企業(yè)標(biāo)準(zhǔn),Q/GDW 689-2012,2012.

3 高磊.IEC61850SCL配置文件比對(duì)工具的研究與實(shí)現(xiàn).電力系統(tǒng)自動(dòng)化,2013,20(10):88–91.

4 馬杰,李磊,黃德斌,等.智能變電站二次系統(tǒng)全過(guò)程管控平臺(tái)研究與實(shí)踐.電力系統(tǒng)保護(hù)與控制,2013,41(2):67–72.

5 樊陳,倪益民,竇仁暉,等.智能變電站信息模型的討論.電力系統(tǒng)自動(dòng)化,2012,36(13):15–19.

6 篤峻,葉翔,王長(zhǎng)瑞,等.智能變電站設(shè)計(jì)配置一體化功能規(guī)范研究及工具開(kāi)發(fā).電力系統(tǒng)自動(dòng)化,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 曾波,潘少彬,陸璐,等.改進(jìn)的LCS方法在測(cè)試腳本序列比對(duì)中的應(yīng)用.計(jì)算機(jī)工程與應(yīng)用,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 陳宏君,劉克金,馮亞?wèn)|,等.新一代保護(hù)測(cè)控裝置配套工具軟件設(shè)計(jì)與應(yīng)用.電力系統(tǒng)自動(dòng)化,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

國(guó)家電網(wǎng)公司科技項(xiàng)目(DW1600052)

2016-03-26;收到修改稿時(shí)間:2016-05-05

10.15888/j.cnki.csa.005506