基于分層匹配和最長公共子序列的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