基于节点相对路径的XML模式抽取算法

《基于节点相对路径的XML模式抽取算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第31卷第1期2009年2月湖州师范学院学报JournalofHuzhouTeachersCollegeVoL31No.1Feb..2009基于节点相对路径的XML模式抽取算法•孙霞，程宏斌°(常熟理工学院计算机科学与工程学院，江苏常熟215500)摘要:结合XML文档树结构提出了一种基于节点相对路径的模式抽取算法，通过使用SAX解析器对XML文档进行一遍扫描•提取出XML文档节点及其相对路径来实现XML文档模式的抽取.该算法有效地解决了XML文档中存在的环路及缺边问题•计算结果模式的代价较低•效率絞高.关■词：模式抽取；XML,SAX,相对路径中图分类号:TP391文献标识码：A文童如

2、号：1009-1734(2009)01-0076・050引言XML以其合理的数据组织结构和可扩展的特性，成为各种复杂数据特别是半结构化数据表示和处理的良好工具•由于没有受到强制性模式的限制•使得半结构化数据具有很大的灵活性•能够满足网络这种复杂分布环境的需要，但同时也给数据处理带来了很大的困难.目前，与半结构化数据相关的研究方向有很多，如新的数据模型、相关的査询语言、存储技术以及査询优化技术等•在众多的研究课题中，对半结构化数据模式的研究是一令非常重要的方向⑴.模式抽取在半结构化数据研究领域中具有重要意义•在半结构化数据中进行数据査询、知识发现以及对Internet上巨大数鼠的数据进行数

3、据挖掘，首要的步骤就是对半结构化数据进行模式抽取，模式抽取是研究半结构化数据的基础⑵.1相关工作XML数据模式在实际的数据处理中有着很广泛的用途，对于无模式的XML文档，如何高效准确地获得其模式信息是XML技术研究者关注的重要问题.XML模式提取技术正是为了解决这个问题而成为XML技术领域的研究热点卩~“•许多研究者对自动提取XML模式的工具进行研究并取得了一定的成果.XTRACT、DDbE.DTD-Miner都是自动提取XML文档DTD的工具；在XMLSchema成为标准之后，XStruct⑸用来自动提取XMLSchema.这些模式抽取系统所采用的一般方法是：对XML文档进行解析.在内

4、存中创建一棵DOM树，将XML树模型转换为用OEM模型描述的图模型,通过对图模型的操作来提取模式信息.上述系统存在着以下缺点:①当使用DOM解析XML文档时，会将整个XML文档都读入到一个树•状结构中，并存储于内存•若遇到XML文档较大时,需要大量的内存空间，从而使解析速度明显变慢，效率很低•②未能解决半结构化数据中带有环路的情况•③基于OEM模型图的模式抽取中容易产生缺边问题.④系统运行的时间和空间代价较大.本文提出一种基于SAX解析方式的节点相对路径模式抽取算法.使用SAX解析器对XML文档进行解析时•不需要把整个文档加载到内存•而是根据已经定义好的事件处理器来决定当前所解析的部分(

5、元素、属性或时元素内容)是否有必要记录并存储.对XML文档进行一遍扫描•根据本文提岀的模式抽取算法•可以高效地提取模式信息.该算法有以下优点:①不需要预先定义参数;②计算结果模式的代价较低；③克服了其他一些算法不能解决环路以及缺边的问题;④效率较高.2基于节点相对路径的模式抽取2.1基本概念2.1.1XML丈档树XML文档可以用节点及节点的相对路径来表示•一个XML文档T可表示为一棵带标记的节点树，T=(R,N.E,P),其中，N为节点集，每个节点对应文档中的一个元素或属性■节点用其元素名或属性名作标记,T中的毎个节点都根据其在数据中岀现的顺序被赋予一个独有的序号OID；R为T的根节点•

6、所有节点都是R的子孙节点；E是有向边的集合，边上的序号表示节点之间的相对路径汙为节点的相对路径构成的集合•在文档树中相对路径表示节点间的父子关系•若节点M经过序号d指向节点N-即P=Jment“paraipo：zipYNamePerwnPenonPerson)(PersonDuetofact—I^njgfr

7、Dbkfr29213Market!23.TitleNameEM&ilStcveKleiCT2.1.2环如果XML文档树中存在〈Md・N2〉・〈Md.NJN-dh.M〉.則称文档树中存在环路•在图1中•存在一个环Department•14■Person)9•