论文部分内容阅读
由于有着标准化、简洁、结构严谨和可高度扩展等优点,可扩展标记语言XML在飞速发展的互联网中逐渐成为网络数据表示和交换的标准格式。现今网络上出现了大量的XML文档,这些文档有些被很好地组织存放在XML数据库里,有些则分散在各个站点、服务器上。怎样更好地管理这些文档或者从这些文档中发现有用的信息、知识,已经成了数据库、信息检索和数据挖掘等领域的研究热点。XML文档的相似性计算是其中的一个热点,得到了国内外众多学者的广泛研究。通过检测XML文档之间的相似性,可以对数据仓库中的XML文档进行版本控制、变化管理,可以将从不同数据源获取的文档进行数据集成、分类或者聚类,亦可以对XML检索结果进行排序等。
与传统的文档不同,XML文档是结构化的文档,既包含文本信息,又包含结构信息。XML文档可以用树形结构表示。研究学者提出了许多方法(例如基于树的编辑距离方法,将传统的信息检索方法进行扩展的带结构信息检索模型,边集比较法,快速傅里叶变换方法等)来检测结构化文档的相似性,并取得了很大的研究成果。然而,在时间效率和精度等方面并没有做到最好,还有一些可以改进的空间。
本文提出了一种扩展边集比较法来计算XML文档之间的相似性。此方法不仅生成父子节点之间的普通边,还生成祖先和子孙节点之间的拓扑边,给不同层和类型的边赋予不同的权值。并且定义了完全匹配,拓扑匹配和重复匹配三种匹配方式。在边集匹配过程中,算法可以检测出两条边之间是属于哪种匹配,并对每种匹配赋予不同的权值,以更合理地计算相似性。扩展边集比较法不仅可以计算XML文档的结构相似性,还可以结合语义相似性算法实现XML文档的结构和语义相似性计算。本文主要使用XML文档聚类分析实验来验证算法的有效性。实验证实扩展边集比较法能获得比现有的基于编辑距离的方法更优的聚类结果。除此之外,本文还进行了语义相似性实验以及RNA二级结构数据聚类分析实验。算法的时间复杂度为O(N2),有着较好的运行效率。在需要快速计算XML文档的结构相似性时,可以通过为边集建立哈希表以降低算法复杂度。