基于文档对象模型的改进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