一种节点加权的相似重复XML数据检测算法

点赞:5060 浏览:14242 近期更新时间:2024-01-11 作者:网友分享原创网站原创

摘 要:XML类型的数据成为当前主流的数据形式,本文提出一种检测XML数据相似性的方法,即将XML文档转换成树结构的基础上,对树结构的节点加权,并结合树编辑距离算法.通过XML带权树各属性权值计算的相似度对数据进行粗略匹配与聚集,而在重新聚集的集合中使用树编辑距离算法更直接的进行相似性检测.由于XML数据集合范围的缩小,树编辑距离算法操作的次数减少,从而节省了一定的时间.

关 键 词:XML数据;节点加权;树编辑距离;相似性

中图分类号:TP391.1

随着网络快速发展,由于结构化的XML类型数据可扩展且跨平台而成为当前网络数据的主流形式.XML文档的迅速增多并集成统一平台后,会产生不被需要的“脏数据”,而对这些数据的清洗变的更加重要.这些“脏数据”使轻则会使获得的信息不准确,重则获得完全错误的信息.为了使XML数据源中的数据能发挥最正确的作用,清洗平台中的“脏数据”成为一个组要解决的问题.

非一致性转换、相似性判定、信息抽取等3方面是当前XML数据清理的主要关注点.如韩恺等人提出的在上下文语义影响下的XML文档的匹配方法[1],Flesca等人将结构化的XML文档与时间序列、脉冲等内容联系起来进行相似性检测[2].以上两篇文章关于XML数据清理方法考虑了不同DTD树间的匹配算法,其中文档内容提到较少,部分方法设计思想很好,但实践可行性有限.

首先,将一个XML文档转化为一棵树或一个图,然后通过度量这两棵树(图)间的距离来体现XML文档间的相似度.在众多树相似度匹配的研究工作中,普遍接收和采用的既是树编辑距离算法[3-6].Tai[3]最早将编辑距离的方法应用到检测两颗树间的相似性.以他的理论为基础,提出的一系列树编辑距离算法及相关的改进算法等.

1相似重复记录

信息集成中,数据清洗和提高数据质量是检测和消除集成数据中的相似重复记录中最需要解决的问题之一.相似重复记录的概念是指虽然在现实世界中表述的是同一个实体,但由于拼写错误或表达方式的不同,而导致数据库管理系统不能将其识别为重复的记录.这些重复记录的产生导致决策者在最终决策时由于依据的信息不正确而产生较大的影响.以此为基础,重复记录检测在信息的抽取、转换、加载的过程中显得更加重要.目前研究的主要方向体现在西文、中文字符集的相似重复记录的检测,已有了一定研究.但对于半结构化的XML数据的重复记录检测算法的研究还有待进一步提高.

XML数据在网络中使用的增多以及在数据库中的使用,使得这种数据类型在数据清理中越来越重要.实际多种XML数据被认为不一致,例如拼写错误等导致字符串属性不一致,从而使得此字符串类型数据不一致.另外,实际相同的XML数据由于结构上不同被认为是不同的数据.即使数据源具有相同的DTD结构,属性个数不同、属性值拼写不同均可导致XML数据不一致.

2树编辑距离

在XML数据的ETL中,主要摒弃其中的“脏数据”,也就是检测出相似记录合并,普遍采用的方式即将XML文档转换成树结构,转换的过程中要将树中的节点与数据元素相对应,即节点名为元素标签名.编辑距离方法分为两种,字符串编辑距离算法用判定两个字符串是否相似,而通过树编辑距离方法时大家更清晰的认识到带标号有序树间差异.以下给出与树编辑距离相关的概念定义.

2.1基本概念

目前对于数据相似性的检测主要采用编辑距离的方式,而此方式又分为两种,字符串编辑距离主要用于字符串领域,树编辑距离主要应用于两棵树或图的差异检测,以下给出具体概念描述.

(1)字符串编辑距离:定义字符串S1、S2,当S1转换为S2时所需要的编辑操作的最小数目,此转换指单个字符上的转换,而操作主要指插入、修改、删除.此概念普遍应用于字符串的相似性检测.

(2)树编辑距离:定义两棵树T1、T2,当T1转换到T2时所需要的书编辑操作的最小代价,此转换指节点的转换.而节点的插入、删除、修改三种操作称为树编辑操作:

1)修改(替换):节点改变;

2)删除:删除某一节点的同时,将该节点的儿子节点重新定义为兄弟节点并插入到其父节点的子树中;

3)插入:插入某一节点的子节点,而该节点的原部分子节点转换为新插入节点的子节点.

2.2树编辑距离的相似性检测

树编辑距离体现了在两个树转化的过程中树编辑操作的最小次数,而实际编辑操作次数计算方式可以通过映射这一概念来体现,将整个求解过程解释为树之间的映射过程,称为编辑映射.

(1)树编辑距离算法:定义两个树T1和T2,在两个树之间建立一映射,直接体现了树与树节点间的对应关系.在树与树之间建立映射需要满足一系列的条件,首先给出两组对应关系属于此映射,分别为(i1,j1),(i2,j2),其中1≤i、j的值≤树的节点数,则,当且仅当j1≤j2时,i1≤i2;另外当且仅当节点j1是节点j2的祖先是,节点i1是节点i2的祖先,从而将树编辑距离的计算转换为映射的计算,在计算过程中,最好的结果即是所付的代价最小.

(2)树编辑距离相似性检测:XML类型数据相似性的检测可以分两步走,首先计算文档转换为树结构时,数据所对应的节点元素字符串间的差异,然后把字符串差异的计算合并到树编辑距离的计算之中来.树编辑距离的值越小,则两颗XML树越相似,此过程中给出阈值的概念作为评判的标准,当值小于设定的阈值时,认为两个XML数据相同.

3优化的XML相似重复数据检测算法

时间复杂度体现了完成操作所需要付出的代价,而针对上述的树编辑距离算法其时间复杂度跟树的节点数以及树的高度有直接的关系.因此,当XML文档的数据量足够大的时候,计算代价会成倍增长,这在实践过程中是无法忍受的,因此,必须采用优化措施来减少树编辑距离计算.本文优化树编辑距离算法,在整个过程中,首先通过树节点的权值进行第一次匹配,将相似性更大的数据聚集到一个集合中,在此集合中采用树编辑距离方法进一步匹配,从而减少时间复杂度.3.1带权树的生成

由于XML文档可以转化为多种树表示形式,针对XML文档通过SAX(SimpleAPIforXML)解析器进行解析,将XML文档转化为XML树结构,并具有相应的可行匹配方法.根据解决问题的侧重点不同,XML带权树的属性在XML文档中具有不同的重要程度.通过XML带权树的权值的大小来表示属性的重要性.根据权值本身的设置特点,在带权树中,设置相同根节点的同一层次上的节点权值之和等于1.

3.2相似性粗略匹配

针对完全展示XML文档的信息的带权树,通过权值的不同体现每个元素重要程度的不同.通过权值进行粗略匹配主要体现在XML树的属性相同时,权值是否相同,权值差异越小,则判断树的相似性越高.在整个判断的过程中,还需要考虑到属性的多少,即树分支数目.

通过实际情况分析推测出重复记录相似度的计算方法如下:带权树Ta和Tb,N代表两树所有节点的个数,a1a2等aN,b1b2等bN分别代表权值,其体现了属性的重要程度.另外,当某一属性仅存在于一棵树中时,则设定此属性的权值为0,相似度的计算公式见(1)[7]:

S(Ta,Tb)等于(N-(a1-b1+a2-b2+等+aN-bN))/N

等于1-((ai-bi))/N(1)

上述公式作为相似度计算的工具,可以很好的计算出任意XML带权树之间的相似性,通过具体的数据来体现差异的大小,从而进行简单的匹配,节省时间.


根据以上描述给出XML类型数据相似性检测的伪代码算法描述如下:

(1)将输入的XML数据集转换为XML带权树;

(2)通过节点权值来计算两棵带权树间的相似度,从而粗略匹配数据;

根据上述思想给出粗略匹配的伪代码描述.

(a)从所有的XML树中任取其中一棵树;

(b)以所取树为基准,通过相似性度量公式计算基树与其它树之间的相似度,目的为了得到所有的相似度值;

(c)将上述相似度值与系统输入的相似度量λ进行比较,若大于等于λ;

(d)将相似度值大于等于λ的XML树聚合成新的集合C1;

(e)任取一不在集合C1中的带权树Tb;

(f)重复执行步骤(b);

(g)直到所有的带权树均存在于一个集合中.

(3)在经过第(2)步聚集的所有新集合中使用树编辑距离算法,当计算后的距离值小于给定的阈值δ时,认为两个是相似的XML数据.

4结束语

本文首先介绍了一系列概念定义,包括相似重复记录,两种编辑距离,并详细描述了树编辑距离相似性检测算法及相关问题.在此基础上,提出一种检测XML数据相似性的方法,即将XML文档转换成树结构的基础上,对树结构的节点加权,并结合树编辑距离算法.通过XML带权树各属性权值计算的相似度对数据进行粗略匹配与聚集,而在重新聚集的集合中使用树编辑距离算法更直接的进行相似性检测.该方法可以大大减少不必要的树编辑距离操作.

#65306;

[1]韩恺,岳丽华等.基于上下文的异构文档类型定义匹配[J].小型微型计算机系统,2005,26(02):256-260.

[2]FlescaS,MancoG,MasciariEetal.DetectingstructuralsimilaritiesbetweenXMLdocuments.In:FernandezMF,PapakonstantinouY,eds.Proc.oftheInt’lWorkshopontheWebandDatabases(WebDB).2002:55-60.

[3]TaiKC.Thetree-to-treecorrectionproblem.JournaloftheACM,1979,26(03):422-433.

[4]DidT.Barnard,GwenClarkeetal.Tree-to-treeCorrectionforDocumentTrees,1995.

[5]ZhangK,ShashaD.SIMPLEFASTALGORITHMORTHEEDITINGDISTANCEBETWEENTREESANDRELATEDPROBLEMS,1989,18(06):1245-1262.

一种节点加权的相似重复XML数据检测算法参考属性评定
有关论文范文主题研究: 关于节点的论文例文 大学生适用: 专科毕业论文、学士学位论文
相关参考文献下载数量: 31 写作解决问题: 怎么撰写
毕业论文开题报告: 论文提纲、论文题目 职称论文适用: 刊物发表、职称评副高
所属大学生专业类别: 怎么撰写 论文题目推荐度: 经典题目

[6]ZhangK.Algorithmortheconstrainededitingdistancebetweenorderedlabeledtreesandrelatedproblems,1995,28(03):463-474.

[7]江曼,陈继明,潘金贵.基于XML的层次式过滤研究[A].2006年全国体育仪器器材与体育系统仿真学术报告会论文集[C].2006.

作者简介:孙娜(1984-),女,辽宁海城人,2009年毕业于沈阳航空工业学院,专业计算机应用技术,教师,助教,硕士,主要研究方向:管理信息系统与数据库;吴兰兰(1983-),女,满族,辽宁海城人,2010年毕业于沈阳航空工业学院,专业计算机应用技术,教师,讲师,硕士,主要研究方向:个性化推荐技术.

作者单位:沈阳航空航天大学北方科技学院,沈阳110136