王友釗,溫 琪,黃 靜

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

基于文檔對(duì)象模型的改進(jìn)SCL文件解析算法

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

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

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

文檔對(duì)象模型;變電站配置描述語(yǔ)言;數(shù)據(jù)結(jié)構(gòu);索引;解析速度;內(nèi)存使用率

1 概述

隨著變電站綜合自動(dòng)化系統(tǒng)的飛速發(fā)展,電網(wǎng)的結(jié)構(gòu)日趨復(fù)雜。不同智能電子設(shè)備之間功能及數(shù)據(jù)通信協(xié)議的多樣性使系統(tǒng)的集成和標(biāo)準(zhǔn)化變得非常困難[1]。為了實(shí)現(xiàn)智能設(shè)備之間的互操作性,國(guó)際電工委員會(huì)提出了變電站配置描述語(yǔ)言(Substation Configuration Description Language,SCL)[2]。通過(guò)SCL不僅可以實(shí)現(xiàn)智能電子設(shè)備的基本功能和基本信息的訪問(wèn),而且可以實(shí)現(xiàn)運(yùn)行參數(shù)的配置。因此,高效的SCL文件解析算法對(duì)提高變電站系統(tǒng)的工作效率至關(guān)重要。

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

(1)基于SAX(Simple API for XML)的解析方案[3]。該方案對(duì)SCL文檔進(jìn)行順序訪問(wèn),并根據(jù)讀入的內(nèi)容生成相應(yīng)的事件,編寫相應(yīng)的事件回調(diào)函數(shù)即可實(shí)現(xiàn)對(duì)SCL文件的解析。SAX方案的優(yōu)點(diǎn)是無(wú)需將文件一次性讀入內(nèi)存,內(nèi)存消耗低,但同時(shí)也有讀取速率低及無(wú)法修改文檔結(jié)構(gòu)的缺點(diǎn)。

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

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

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

2 SCL文件特點(diǎn)分析

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

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

在SCL文件中,TEXT節(jié)點(diǎn)即文本節(jié)點(diǎn)占用大量存儲(chǔ)空間。同種設(shè)備或同類型設(shè)備的信息在SCL文件中多次重復(fù)出現(xiàn),導(dǎo)致TEXT內(nèi)容存在數(shù)據(jù)冗余的特點(diǎn)。某種智能電子裝置的部分配置文件描述具體如下:

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

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

DOM[9]是W3C(World Wide Web Consortium)提出的一種與語(yǔ)言和平臺(tái)無(wú)關(guān)的API編程接口。DOM將XML文件中的信息表示成節(jié)點(diǎn),并組成樹狀結(jié)構(gòu)。應(yīng)用程序可以調(diào)用相關(guān)API通過(guò)DOM樹對(duì)文檔信息進(jìn)行訪問(wèn)和修改[10]。

標(biāo)準(zhǔn)DOM模型將XML文檔解析為Document, Root,Text,Element及Attribute等多種類型的節(jié)點(diǎn)。因此,DOM樹占用的內(nèi)存空間要比實(shí)際文件的尺寸大。

在DOM解析SCL文件的過(guò)程中,采用以下方法可以避免重復(fù)信息在內(nèi)存中多次出現(xiàn),達(dá)到優(yōu)化算法的目的:

(1)用一種單獨(dú)的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)文本節(jié)點(diǎn)信息;

(2)DOM樹中文本節(jié)點(diǎn)存放實(shí)際內(nèi)容的索引或指針;

(3)DOM每次通過(guò)指針或索引對(duì)SCL文件內(nèi)容進(jìn)行訪問(wèn)或修改。

3.1 基于動(dòng)態(tài)數(shù)組的改進(jìn)算法

在計(jì)算機(jī)中,數(shù)組用連續(xù)的內(nèi)存存儲(chǔ)數(shù)據(jù)。對(duì)數(shù)組中每一個(gè)元素的訪問(wèn)或修改都通過(guò)索引進(jìn)行。用數(shù)組來(lái)存儲(chǔ)SCL中文本節(jié)點(diǎn)信息,能夠快速地訪問(wèn)并修改索引指向的節(jié)點(diǎn)。

數(shù)組分為靜態(tài)數(shù)組和動(dòng)態(tài)數(shù)組2種。靜態(tài)數(shù)組在聲明時(shí)需要確定固定的存儲(chǔ)空間,動(dòng)態(tài)數(shù)組在使用時(shí)可以根據(jù)需要?jiǎng)討B(tài)增加數(shù)組的容量。由于對(duì)SCL文件進(jìn)行解析時(shí),無(wú)法預(yù)先得知所需的存儲(chǔ)空間,因此采用動(dòng)態(tài)數(shù)組存儲(chǔ)文本節(jié)點(diǎn)信息比較合理。

在DOM樹構(gòu)建過(guò)程中,改進(jìn)算法利用動(dòng)態(tài)數(shù)組將原算法中文本節(jié)點(diǎn)的信息替換為索引,實(shí)際的文本信息存儲(chǔ)在動(dòng)態(tài)數(shù)組中,數(shù)組中不存在重復(fù)的元素。第2節(jié)中部分SCL文件使用動(dòng)態(tài)數(shù)組優(yōu)化算法展開的包含索引的樹狀結(jié)構(gòu)如圖1所示。圖中的數(shù)字為實(shí)際文本信息的索引,其對(duì)應(yīng)的動(dòng)態(tài)數(shù)組結(jié)構(gòu)如圖2所示。圖2顯示動(dòng)態(tài)數(shù)組中存儲(chǔ)了實(shí)際文本信息的字符串,相同的字符串在內(nèi)存中只占一份存儲(chǔ)空間。對(duì)于文本信息重復(fù)概率較大的SCL文件,動(dòng)態(tài)數(shù)組可以在很大程度上減少由數(shù)據(jù)重復(fù)造成的內(nèi)存浪費(fèi),優(yōu)化DOM算法的內(nèi)存使用效率。

圖1 包含索引的樹狀結(jié)構(gòu)

圖2 動(dòng)態(tài)數(shù)組結(jié)構(gòu)

在索引樹構(gòu)建完成之后,查詢某一節(jié)點(diǎn)的文本信息內(nèi)容可以直接利用數(shù)組的下標(biāo)進(jìn)行索引,所需要的時(shí)間復(fù)雜度為O(1)。

基于動(dòng)態(tài)數(shù)組索引的算法對(duì)傳統(tǒng)DOM算法的空間復(fù)雜度起到了優(yōu)化作用,查詢時(shí)間的時(shí)間復(fù)雜度與DOM算法一致。然而,在構(gòu)建樹的過(guò)程中,在添加一個(gè)節(jié)點(diǎn)的字符串信息時(shí),首先要遍歷字符串?dāng)?shù)組,驗(yàn)證數(shù)組中是否已經(jīng)存在相同字符串,若不存在,則向動(dòng)態(tài)數(shù)組中添加新元素,返回新元素的索引,否則返回已存在的索引。顯然,該算法添加全部節(jié)點(diǎn)所需的時(shí)間復(fù)雜度為O(n2)。在節(jié)點(diǎn)信息較多的情況下,該算法會(huì)犧牲大量的時(shí)間,影響整個(gè)算法的效率。

3.2 基于散列表的改進(jìn)算法

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

散列表以哈希值作為索引,查詢修改元素的操作與數(shù)組執(zhí)行相同操作的時(shí)間復(fù)雜度相同。散列表在添加元素時(shí),首先判斷散列值對(duì)應(yīng)的元素是否為空,再?zèng)Q定是否插入新值,不需要從頭至尾遍歷表中元素,該算法要優(yōu)于基于動(dòng)態(tài)數(shù)組的改進(jìn)算法。

基于散列表的DOM索引算法的優(yōu)化步驟為:

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

(2)讀取文本節(jié)點(diǎn)信息,計(jì)算散列值,查找散列表。

(3)若對(duì)應(yīng)的內(nèi)容為空,在內(nèi)存中建立新的字符串,存入散列表并返回節(jié)點(diǎn)內(nèi)容指針,否則直接返回散列表中內(nèi)容指針。

(4)將指針存入DOM樹狀結(jié)構(gòu),繼續(xù)步驟(2)直到所有節(jié)點(diǎn)都創(chuàng)建完成。

該算法將動(dòng)態(tài)數(shù)組每次插入查詢的時(shí)間復(fù)雜度O(n)降低為O(1),在很大程度上優(yōu)化了DOM樹的構(gòu)造時(shí)間。但是,散列表在初始化時(shí)要提前分配數(shù)據(jù)空間,在數(shù)據(jù)量未知的情況下,散列表必須申請(qǐng)足夠大的空間以便可以容納將要存儲(chǔ)的數(shù)據(jù)?？臻g分配過(guò)小,散列表就要頻繁移動(dòng)數(shù)據(jù),加大時(shí)間上的開銷;空間分配過(guò)大,會(huì)造成內(nèi)存浪費(fèi)。所以,合理分配散列表的初始內(nèi)存空間有利于提高內(nèi)存利用率。

3.3 基于二叉平衡查找樹的改進(jìn)算法

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

圖3 普通的二叉查找樹

圖4 不理想的二叉查找樹

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

帶平衡條件的二叉查找樹,例如紅黑樹[12],可以保證樹中所有子樹的左右子樹深度差的絕對(duì)值不超過(guò)1。當(dāng)插入節(jié)點(diǎn)后引起左右子樹平衡條件被破壞時(shí),平衡樹會(huì)對(duì)不滿足平衡條件的最高子樹進(jìn)行左旋右旋等調(diào)整,使樹重新滿足平衡條件,這種局部調(diào)整的時(shí)間復(fù)雜度為O(1),所以,不會(huì)影響整個(gè)操作的時(shí)間界。

二叉查找樹的節(jié)點(diǎn)是動(dòng)態(tài)創(chuàng)建的,不需要提前分配存儲(chǔ)空間,節(jié)點(diǎn)之間通過(guò)指針連接,不需要連續(xù)的存儲(chǔ)空間。二叉平衡查找樹每次查找、添加文本節(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(log(n)),因此,構(gòu)造整棵樹的時(shí)間復(fù)雜度為O(nlog(n))。對(duì)于DOM算法的改進(jìn),使用二叉查找樹結(jié)構(gòu)在理論上優(yōu)于使用動(dòng)態(tài)數(shù)組和散列表的改進(jìn)。3種改進(jìn)算法創(chuàng)建所有文本節(jié)點(diǎn)所需要的時(shí)間和空間復(fù)雜度見表1。

表1 算法復(fù)雜度比較

4 實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

本文在Windows平臺(tái)下,以Visual Studio 2010作為開發(fā)環(huán)境,編程實(shí)現(xiàn)了改進(jìn)算法,圖5為程序運(yùn)行截圖。

圖5 程序運(yùn)行截圖

為了檢驗(yàn)算法的質(zhì)量,實(shí)驗(yàn)選取了大小不同的SCL文件。對(duì)算法的內(nèi)存使用情況及模擬構(gòu)建整個(gè)DOM樹所消耗的時(shí)間進(jìn)行比較,結(jié)果如表2所示。

表2 算法的內(nèi)存使用情況和時(shí)間消耗比較

由表2的實(shí)驗(yàn)結(jié)果數(shù)據(jù)可知,傳統(tǒng)DOM算法將整個(gè)文件以節(jié)點(diǎn)對(duì)象的方式在內(nèi)存中展開,內(nèi)存消耗為原始文件大小的3倍～4倍,在4種算法中占用內(nèi)存最多;基于動(dòng)態(tài)數(shù)組的算法(A-DOM)和基于二叉平衡查找樹的算法所占用的內(nèi)存空間與SCL文件中有效文本信息所占用空間相對(duì)應(yīng),提高了內(nèi)存利用率,相對(duì)于傳統(tǒng)DOM算法,其優(yōu)化程度與SCL文件的大小和文本節(jié)點(diǎn)的重復(fù)率有關(guān);基于散列表的DOM算法使用散列表的數(shù)據(jù)結(jié)構(gòu),需要分配大于實(shí)際存儲(chǔ)數(shù)據(jù)的內(nèi)存空間,所以,該算法內(nèi)存消耗略高于基于動(dòng)態(tài)數(shù)組和二叉平衡查找樹的DOM算法。

在時(shí)間消耗上,傳統(tǒng)DOM算法一切操作均在完整的SCL文件映射的樹狀結(jié)構(gòu)上進(jìn)行,時(shí)間消耗最短;基于散列表的DOM算法多出計(jì)算散列函數(shù)的常數(shù)時(shí)間;基于二叉平衡查找樹的DOM算法要額外查找索引樹,隨著文件增大,該查找時(shí)間會(huì)變長(zhǎng);基于動(dòng)態(tài)數(shù)組的DOM算法每次插入新數(shù)據(jù)都要查詢整個(gè)索引數(shù)組,時(shí)間消耗急劇增加,該算法的時(shí)間消耗代價(jià)遠(yuǎn)超過(guò)對(duì)內(nèi)存的優(yōu)化效果,所以,基于動(dòng)態(tài)數(shù)組的算法不可取。

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

圖6 時(shí)間消耗比較

圖7 內(nèi)存使用情況比較

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

圖8 改進(jìn)算法與VTD算法的內(nèi)存使用情況比較

5 結(jié)束語(yǔ)

本文主要研究基于DOM的SCL解析算法,通過(guò)對(duì)DOM算法的研究并結(jié)合SCL文件文本信息冗余性的特點(diǎn),通過(guò)建立文本節(jié)點(diǎn)索引以減少DOM樹內(nèi)存使用的2種改進(jìn)算法:基于散列表的DOM算法和基于二叉平衡查找樹的DOM算法。實(shí)驗(yàn)結(jié)果表明,改進(jìn)算法實(shí)現(xiàn)了對(duì)傳統(tǒng)DOM算法的優(yōu)化,能夠在保證SCL文件解析速度的前提下,有效減少DOM算法的內(nèi)存消耗。

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

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

[3] 范書義,李 巖,孟 晨.XML文件解析中SAX和DOM的結(jié)合應(yīng)用[J].微型電腦應(yīng)用,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實(shí)現(xiàn)的技術(shù)研究[J].計(jì)算機(jī)科學(xué),2006,33(6):274-277.

[7] 譚文恕.變電站通信網(wǎng)絡(luò)和系統(tǒng)協(xié)議IEC61850介紹[J].電網(wǎng)技術(shù),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] 蔚曉娟,冉 靜,李愛(ài)華,等.基于DOM的XML解析與應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展,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.算法導(dǎo)論[M].殷建平,徐 云,王 剛,等,譯.北京:機(jī)械工業(yè)出版社,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

國(guó)家自然科學(xué)基金資助項(xiàng)目(51375459)。

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

2013-10-09

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