基于文檔對象模型的改進SCL文件解析算法

王友釗,溫 琪,黃 靜

(1.浙江大學數字技術及儀器研究所,杭州310027;2.浙江理工大學信息電子學院,杭州310018)

基于文檔對象模型的改進SCL文件解析算法

王友釗1,溫 琪1,黃 靜2

(1.浙江大學數字技術及儀器研究所,杭州310027;2.浙江理工大學信息電子學院,杭州310018)

基于文檔對象模型(DOM)的變電站配置描述語言(SCL)文件解析算法在解析文件時會將整個SCL文檔內容在內存中展開,并將文件內容轉化為樹狀節點的結構,占用較大的內容空間。針對該問題,對傳統DOM算法進行改進,利用SCL文件的文本節點信息存在冗余的特性,分別使用動態數組、散列表以及二叉平衡查找樹3種數據結構為文本節點建立索引并去除冗余,避免相同的信息重復使用內存。實驗結果表明,對于普通的SCL文件,使用基于二叉平衡查找樹的改進算法能在原算法的基礎上減少46%～66%的內存使用;對于較大的SCL文件,使用基于散列表的改進算法能在原算法的基礎上減少40%～59.8%的內存使用;2種針對不同大小SCL文件的改進算法,能夠在保證SCL文件解析速度的前提下,有效減少DOM算法的內存消耗。

文檔對象模型;變電站配置描述語言;數據結構;索引;解析速度;內存使用率

1 概述

隨著變電站綜合自動化系統的飛速發展,電網的結構日趨復雜。不同智能電子設備之間功能及數據通信協議的多樣性使系統的集成和標準化變得非常困難[1]。為了實現智能設備之間的互操作性,國際電工委員會提出了變電站配置描述語言(Substation Configuration Description Language,SCL)[2]。通過SCL不僅可以實現智能電子設備的基本功能和基本信息的訪問,而且可以實現運行參數的配置。因此,高效的SCL文件解析算法對提高變電站系統的工作效率至關重要。

目前,對SCL文件的解析方案主要有以下3種:

(1)基于SAX(Simple API for XML)的解析方案[3]。該方案對SCL文檔進行順序訪問,并根據讀入的內容生成相應的事件,編寫相應的事件回調函數即可實現對SCL文件的解析。SAX方案的優點是無需將文件一次性讀入內存,內存消耗低,但同時也有讀取速率低及無法修改文檔結構的缺點。

(2)基于虛擬令牌描述符(Virtual Token Descriptor,VTD)[4]的解析方案。VTD方案將整個文件原封不動地讀入內存,將原始信息存儲為不同類型的數組。數組中存儲了對應的原始文件位置以及數據之間上下層關系等信息[5]。該方案通過操作數組來修改文件中的內容。VTD內存使用與原文件大小相當,但是解析速度明顯高于SAX方案。

(3)基于文檔對象模型(Document Object Model, DOM)的解析方案。該方案將整個SCL文件內容一次性讀入內存,配置文件的信息被轉化成對象節點樹。DOM樹生成之后,對節點對象的遍歷、修改、刪除、插入、查詢等所有操作都直接在內存中進行。DOM樹創建后占用的內存空間是VTD方案的3倍～4倍,這極大地增加了計算機內存的開銷,尤其當SCL文件較大時,這種內存開銷會嚴重影響DOM算法的整體性能。DOM的解析速度也要慢于VTD,但由于DOM比較容易編程實現,因此被廣泛采用。

本文在DOM解析算法的基礎上,利用SCL文件中存在的大量重復文本節點信息的特點,借鑒VTD算法和數據延遲裝載[6]的思想,為SCL文件中的文本節點信息建立索引,保證相同或相近的信息在內存中只占用一份存儲空間,從而達到降低DOM算法的內存使用率的目的。

2 SCL文件特點分析

SCL是IEC61850-6[7]標準中規定的描述變電站智能電子設備基本功能以及運行參數等的文件格式規范,用于不同設備之間交換配置信息。SCL基于XML的語言[8],它與XML的文件格式有很大的相似性。

SCL文件包含頭段(Header)、變電站段(Substation)、IED段(IED)、通信段(Communication)及數據類型模塊段(DataTypeTemplate)5個部分。

在SCL文件中,TEXT節點即文本節點占用大量存儲空間。同種設備或同類型設備的信息在SCL文件中多次重復出現,導致TEXT內容存在數據冗余的特點。某種智能電子裝置的部分配置文件描述具體如下:

從以上的SCL文件中可以看出,類似“TCTR”,“INT32”等的文本信息在文中多次出現,這種重復不是局部的偶然現象,整個SCL文件都存在這樣的特點,這種冗余的文本信息為DOM算法空間復雜度的優化提供了可能。

3 基于DOM的SCL文件解析算法

DOM[9]是W3C(World Wide Web Consortium)提出的一種與語言和平臺無關的API編程接口。DOM將XML文件中的信息表示成節點,并組成樹狀結構。應用程序可以調用相關API通過DOM樹對文檔信息進行訪問和修改[10]。

標準DOM模型將XML文檔解析為Document, Root,Text,Element及Attribute等多種類型的節點。因此,DOM樹占用的內存空間要比實際文件的尺寸大。

在DOM解析SCL文件的過程中,采用以下方法可以避免重復信息在內存中多次出現,達到優化算法的目的:

(1)用一種單獨的數據結構存儲文本節點信息;

(2)DOM樹中文本節點存放實際內容的索引或指針;

(3)DOM每次通過指針或索引對SCL文件內容進行訪問或修改。

3.1 基于動態數組的改進算法

在計算機中,數組用連續的內存存儲數據。對數組中每一個元素的訪問或修改都通過索引進行。用數組來存儲SCL中文本節點信息,能夠快速地訪問并修改索引指向的節點。

數組分為靜態數組和動態數組2種。靜態數組在聲明時需要確定固定的存儲空間,動態數組在使用時可以根據需要動態增加數組的容量。由于對SCL文件進行解析時,無法預先得知所需的存儲空間,因此采用動態數組存儲文本節點信息比較合理。

在DOM樹構建過程中,改進算法利用動態數組將原算法中文本節點的信息替換為索引,實際的文本信息存儲在動態數組中,數組中不存在重復的元素。第2節中部分SCL文件使用動態數組優化算法展開的包含索引的樹狀結構如圖1所示。圖中的數字為實際文本信息的索引,其對應的動態數組結構如圖2所示。圖2顯示動態數組中存儲了實際文本信息的字符串,相同的字符串在內存中只占一份存儲空間。對于文本信息重復概率較大的SCL文件,動態數組可以在很大程度上減少由數據重復造成的內存浪費,優化DOM算法的內存使用效率。

圖1 包含索引的樹狀結構

圖2 動態數組結構

在索引樹構建完成之后,查詢某一節點的文本信息內容可以直接利用數組的下標進行索引,所需要的時間復雜度為O(1)。

基于動態數組索引的算法對傳統DOM算法的空間復雜度起到了優化作用,查詢時間的時間復雜度與DOM算法一致。然而,在構建樹的過程中,在添加一個節點的字符串信息時,首先要遍歷字符串數組,驗證數組中是否已經存在相同字符串,若不存在,則向動態數組中添加新元素,返回新元素的索引,否則返回已存在的索引。顯然,該算法添加全部節點所需的時間復雜度為O(n2)。在節點信息較多的情況下,該算法會犧牲大量的時間,影響整個算法的效率。

3.2 基于散列表的改進算法

散列表(hash table)[11]是一個包含關鍵字的固定大小的數組,不同的關鍵字通過散列函數映射到數組中的不同單元。插入和查找數據時,散列表通過散列函數計算數據對應的散列值,并以此作為數組的索引對數組的元素進行查詢或修改,計算散列值的操作需要花費常數時間,因此散列表插入和查詢數據的算法時間復雜度都為O(1)。

散列表以哈希值作為索引,查詢修改元素的操作與數組執行相同操作的時間復雜度相同。散列表在添加元素時,首先判斷散列值對應的元素是否為空,再決定是否插入新值,不需要從頭至尾遍歷表中元素,該算法要優于基于動態數組的改進算法。

基于散列表的DOM索引算法的優化步驟為:

(1)建立并初始化散列表。

(2)讀取文本節點信息,計算散列值,查找散列表。

(3)若對應的內容為空,在內存中建立新的字符串,存入散列表并返回節點內容指針,否則直接返回散列表中內容指針。

(4)將指針存入DOM樹狀結構,繼續步驟(2)直到所有節點都創建完成。

該算法將動態數組每次插入查詢的時間復雜度O(n)降低為O(1),在很大程度上優化了DOM樹的構造時間。但是,散列表在初始化時要提前分配數據空間,在數據量未知的情況下,散列表必須申請足夠大的空間以便可以容納將要存儲的數據。空間分配過小,散列表就要頻繁移動數據,加大時間上的開銷;空間分配過大,會造成內存浪費。所以,合理分配散列表的初始內存空間有利于提高內存利用率。

3.3 基于二叉平衡查找樹的改進算法

樹狀結構能有效地利用分治算法處理問題。DOM樹本身是一種樹狀結構。圖3是一棵普通的二叉查找樹,從中可以看出,樹中任意節點左邊所有子節點的值都小于該節點的值,右邊所有子節點的值都大于該節點的值。對于圖3,若要查找節點“5”,則只需要做3次比較。圖3中二叉查找樹的查找、插入的時間復雜度都為O(log(n))。如果構造二叉查找樹時,根節點選取的不合適,查找和插入的時間復雜度就會超出log(n)的下界。一棵不理想的二叉查找樹如圖4所示,該二叉查找樹查找和插入的時間復雜度為O(n)。

圖3 普通的二叉查找樹

圖4 不理想的二叉查找樹

為了保證一棵二叉查找樹的查找和插入的時間復雜度為O(log(n)),需要保證它的左子樹與右子樹的深度差的絕對值不超過1。

帶平衡條件的二叉查找樹,例如紅黑樹[12],可以保證樹中所有子樹的左右子樹深度差的絕對值不超過1。當插入節點后引起左右子樹平衡條件被破壞時,平衡樹會對不滿足平衡條件的最高子樹進行左旋右旋等調整,使樹重新滿足平衡條件,這種局部調整的時間復雜度為O(1),所以,不會影響整個操作的時間界。

二叉查找樹的節點是動態創建的,不需要提前分配存儲空間,節點之間通過指針連接,不需要連續的存儲空間。二叉平衡查找樹每次查找、添加文本節點的時間復雜度均為O(log(n)),因此,構造整棵樹的時間復雜度為O(nlog(n))。對于DOM算法的改進,使用二叉查找樹結構在理論上優于使用動態數組和散列表的改進。3種改進算法創建所有文本節點所需要的時間和空間復雜度見表1。

表1 算法復雜度比較

4 實驗驗證與結果分析

本文在Windows平臺下,以Visual Studio 2010作為開發環境,編程實現了改進算法,圖5為程序運行截圖。

圖5 程序運行截圖

為了檢驗算法的質量,實驗選取了大小不同的SCL文件。對算法的內存使用情況及模擬構建整個DOM樹所消耗的時間進行比較,結果如表2所示。

表2 算法的內存使用情況和時間消耗比較

由表2的實驗結果數據可知,傳統DOM算法將整個文件以節點對象的方式在內存中展開,內存消耗為原始文件大小的3倍～4倍,在4種算法中占用內存最多;基于動態數組的算法(A-DOM)和基于二叉平衡查找樹的算法所占用的內存空間與SCL文件中有效文本信息所占用空間相對應,提高了內存利用率,相對于傳統DOM算法,其優化程度與SCL文件的大小和文本節點的重復率有關;基于散列表的DOM算法使用散列表的數據結構,需要分配大于實際存儲數據的內存空間,所以,該算法內存消耗略高于基于動態數組和二叉平衡查找樹的DOM算法。

在時間消耗上,傳統DOM算法一切操作均在完整的SCL文件映射的樹狀結構上進行,時間消耗最短;基于散列表的DOM算法多出計算散列函數的常數時間;基于二叉平衡查找樹的DOM算法要額外查找索引樹,隨著文件增大,該查找時間會變長;基于動態數組的DOM算法每次插入新數據都要查詢整個索引數組,時間消耗急劇增加,該算法的時間消耗代價遠超過對內存的優化效果,所以,基于動態數組的算法不可取。

圖6、圖7為表2中數據曲線表示。從曲線圖的變化趨勢可以得出以下結論:基于散列表的DOM算法(H-DOM)和基于二叉平衡查找樹的DOM算法(T-DOM)均能改善內存使用情況,其中基于散列表的DOM算法減少了原DOM算法40% ～59.8%的內存使用,基于二叉平衡查找樹的DOM算法減少了原DOM算法46%～66%的內存使用,因此,基于二叉平衡查找樹的DOM算法要優于基于散列表的DOM算法,隨著文件的增大,基于二叉平衡查找樹的DOM算法消耗的時間開始增加,因此,對于普通的SCL文件,適合采用基于二叉平衡查找樹的DOM算法,而對于較大的SCL文件,尤其當文件大小超過幾十MB時,適合采用基于散列表的DOM算法。

圖6 時間消耗比較

圖7 內存使用情況比較

圖8為基于散列表的DOM算法、基于二叉平衡查找樹的DOM算法與VTD-XML算法的內存使用情況對比。從中可見,2種針對 SCL文件改進的DOM算法在內存使用情況上與VTD-XML的情況相當,并且在文件較大時,改進DOM算法的內存使用率超越了VTD-XML算法,因此,改進的DOM算法在減少解析 SCL文件時內存使用方面的效果顯著。

圖8 改進算法與VTD算法的內存使用情況比較

5 結束語

本文主要研究基于DOM的SCL解析算法,通過對DOM算法的研究并結合SCL文件文本信息冗余性的特點,通過建立文本節點索引以減少DOM樹內存使用的2種改進算法:基于散列表的DOM算法和基于二叉平衡查找樹的DOM算法。實驗結果表明,改進算法實現了對傳統DOM算法的優化,能夠在保證SCL文件解析速度的前提下,有效減少DOM算法的內存消耗。

[1] 羅 彥,方春恩,李 偉.SCL文件的研究和IED配置器與實現[J].西華大學學報:自然科學版,2008,27 (4):17-19.

[2] 尹家凡,王孫安,盛萬興.XML語言在變電站設備描述中的應用[J].計算機工程與應用,2003,39(21): 209-210,224.

[3] 范書義,李 巖,孟 晨.XML文件解析中SAX和DOM的結合應用[J].微型電腦應用,2011,27(12): 42-44.

[4] Zhang J.SimpleXML Processing with VTD-XML [EB/OL].(2012-01-17).http://www.javaworld.com/ javaworld/jw-03-2006/jw-0327-simplify.html.

[5] Tak L,Ding Jianxun,Liu J C.XML Document Parsing: Operationaland Performance Characteristics[J]. Computer,2008,41(9):30-37.

[6] 郭紅艷,楊 波,金蓓弘.高效DOM實現的技術研究[J].計算機科學,2006,33(6):274-277.

[7] 譚文恕.變電站通信網絡和系統協議IEC61850介紹[J].電網技術,2001,25(9):8-11,15.

[8] Pan Yun.Improve SCL File Processing Performance Using Binary Encoding Specification[Z].2011.

[9] W3C.Document Object Model[EB/OL].(2005-01-14).http://www.w3.org/DOM/.

[10] 蔚曉娟,冉 靜,李愛華,等.基于DOM的XML解析與應用[J].計算機技術與發展,2007,17(4):86-88,139.

[11] Weiss M A.Data Structures and Algorithm Analysis in C[M].2nd ed.[S.l.]:Addison-Wesley,2010.

[12] Cormen T H,Leiserson C E,Rivest R L,et al.算法導論[M].殷建平,徐 云,王 剛,等,譯.北京:機械工業出版社,2012.

編輯 陸燕菲

Improved SCL File Parsing Algorithm Based on Document Object Model

WANG You-zhao1,WEN Qi1,HUANG Jing2
(1.Institute of Advanced Digital Technology and Instrument,Zhejiang University,Hangzhou 310027,China;
2.College of Informatics&Electronics,Zhejiang Sci-tech University,Hangzhou 310018,China)

The traditional method of parsing Substation Configuration Description Language(SCL)files based on Document Object Model(DOM)expands the whole file in memory and makes a tree structure which has the defect of height memory utilization.According to the redundancy of text nodes information in SCL,improved algorithms are proposed by using the data structures of dynamic array,hash table and binary balance search tree to build index for the text nodes.Experimental results show that the DOM algorithm based on binary balance search tree can reduce 46%～66% of the memory utilization for the common SCL files,and the DOM algorithm based on hash table can cut down 40%～59.8% of the bigger SCL files.The two improved algorithms all perform well in reducing the memory utilization of parsing SCL files on the premise of guarantee the SCL file parsing speed.

Document Object Model(DOM);Substation Configuration Description Language(SCL);data structure; index;parsing speed;memory utilization

1000-3428(2014)09-0032-05

A

TM734

10.3969/j.issn.1000-3428.2014.09.007

國家自然科學基金資助項目(51375459)。

王友釗(1963-),男,副教授,主研方向:數據處理,智能電網;溫 琪,碩士研究生;黃 靜,教授。

2013-10-09

2013-11-07E-mail:wichine@126.com