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

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

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

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

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

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

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

IEC61850; SCD/ICD文件; 層次比較; 最長公共子序列

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

SCD文件采用XML層次結(jié)構(gòu)進(jìn)行描述, 并且各個層次的節(jié)點(diǎn)都具有特定的語義, 如果使用純文本的比較方法, 難以正確地、清晰地表示文件的差異[3-6].文獻(xiàn)[3]提出了一種基于鍵/值的SCL文件比較方法,即對關(guān)鍵節(jié)點(diǎn)定義鍵值和比較判據(jù), 形成帶主鍵的二維表結(jié)構(gòu), 比對文件的差異. 文獻(xiàn)[4]提出了一種根據(jù)每個層次節(jié)點(diǎn)的屬性遍歷查找, 進(jìn)行比對的方法. 這兩種方法都是純結(jié)構(gòu)化的比較方法, 需要遍歷查找整個文件的層次結(jié)構(gòu). 由于SCD文件結(jié)構(gòu)復(fù)雜, 節(jié)點(diǎn)層次多, 每個層次的節(jié)點(diǎn)所具有的屬性都不同, 很難抽象出一種統(tǒng)一的比較模式. 因此結(jié)構(gòu)化的比較方法效率會比較低, 并且對于比較結(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). 然后使用基于最長公共子序列的比較算法, 比較邏輯節(jié)點(diǎn)的內(nèi)容. 計(jì)算最長公共子序列(Longest Common Subsequence, LCS)的算法在數(shù)據(jù)差異分析、文件版本控制、生物信息分析、圖像處理等方面具有廣泛的應(yīng)用[7-9]. 本文將參與比較的兩個邏輯節(jié)點(diǎn)的內(nèi)容轉(zhuǎn)換成兩個序列, 通過計(jì)算這兩個序列最長公共子序列實(shí)現(xiàn)對這兩個序列的比較, 從而完成邏輯節(jié)點(diǎn)內(nèi)容的比較.使用這種半結(jié)構(gòu)化半文本的比較方法既可以在保持文件主體結(jié)構(gòu)不變的情況下去除僅調(diào)整順序不影響實(shí)體內(nèi)容的無效差異, 又可以快速準(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個), IED包括若干連接接入點(diǎn)(AccessPoint), 連接接入點(diǎn)包括若干邏輯設(shè)備(LDevice), 邏輯設(shè)備由1個公用邏輯節(jié)點(diǎn)(LLN0)、代表具體功能的若干邏輯節(jié)點(diǎn)(LN)組成. 邏輯節(jié)點(diǎn)由若干數(shù)據(jù)對象實(shí)例(DOI)組成, 數(shù)據(jù)對象由若干數(shù)據(jù)類的實(shí)例組合(DAI)組成.

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

2 層次化比較方法

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

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

圖2 SCD文件總體比較流程

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

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

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

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

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

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

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

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

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

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

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

3.1 概念定義

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

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

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

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

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

例如: 對于序列“compare”, “par”是一個子串, 同時也是一個子序列, 而“opre”只是一個子序列.

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

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

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

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

假設(shè)序列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 計(jì)算最長公共子序列

假設(shè)序列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)

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

＜公式一＞ 對于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的最長公共子序列是由A的子序列和B的子序列的最長公共子序列所決定的. 因此需要計(jì)算A的所有子序列和B的所有子序列之間一一對應(yīng)的最長公共子序列, 這樣才能獲得A和B的最長公共子序列.

3.3 計(jì)算匹配矩陣

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

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

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

3.4 計(jì)算回溯路徑

計(jì)算得到兩個序列的匹配矩陣后, 再從矩陣的右下角往左上角進(jìn)行回溯. 假設(shè)當(dāng)前位于矩陣的第i行第j列, 則根據(jù)＜公式一＞得到的回溯規(guī)則如下:

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

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

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

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

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

圖7 回溯匹配矩陣

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

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

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

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

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

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

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

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

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

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

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

4 算法驗(yàn)證

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

5 結(jié)語

本文提出了一種分層的結(jié)構(gòu)化比較和基于最長公共子序列的文本比較相結(jié)合的比較算法, 實(shí)現(xiàn)了SCD/ICD文件的差異比較和展示. 使用此算法實(shí)現(xiàn)的SCD/ICD文件比較功能已經(jīng)在保護(hù)測控裝置配套軟件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ī)范.國家電網(wǎng)公司企業(yè)標(biāo)準(zhǔn),Q/GDW 689-2012,2012.

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

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

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

6 篤峻,葉翔,王長瑞,等.智能變電站設(shè)計(jì)配置一體化功能規(guī)范研究及工具開發(fā).電力系統(tǒ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方法在測試腳本序列比對中的應(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 陳宏君,劉克金,馮亞東,等.新一代保護(hù)測控裝置配套工具軟件設(shè)計(jì)與應(yīng)用.電力系統(tǒ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

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

2016-03-26;收到修改稿時間:2016-05-05

10.15888/j.cnki.csa.005506