论文部分内容阅读
随着网络上的数据量逐日剧增,HTML的缺陷逐渐明显,传统的Web技术已不能满足Internet发展的需求。半结构化语言XML的出现,攻克了这一难题。XML语言,具有超强的扩展性和易读性,能够有效的解释数据,在数据发布和数据交换等应用领域里发挥着越来越重要的作用。数据挖掘和数据库等数据处理领域需要对XML进行支持。而XML文档相似性研究,则是文档聚类、数据挖掘和信息检索的基础,成为当前的研究热点。本文的研究目标是研究XML文档相似性算法。目前已经发表了很多XML相似性算法,可以分为三类:基于编辑距离(ED)的方法,基于信息检索(IR)的方法,采用不同技术来比较XML的其它方法。基于ED的方法是将XML文档转换成XML文档树,然后利用动态规划技术,找到树结构的编辑距离。其中大多数算法的目的都是为了实现文档和文档的比较。它们针对数据中心的XML,并且通常有精细的粒度。它们主要用于对XML文档结构相似度有精确要求的应用,例如数据集成、以及XML分类/聚类应用。ED算法有产生编辑脚本的特点,通过相似度值所对应的编辑脚本,可以描述树的转换过程。现今已有的算法中,编辑图算法由于快速有效等特点,成为研究编辑距离算法的出发点,本文也选择了编辑图算法。本文首先简单介绍了数据挖掘的概念和挖掘过程,XML的相关概念和特点,然后详细的阐述了编辑图算法原理,与该算法有关的知识都做了介绍,包括表示模型,编辑图的概念等。编辑图算法是核心思想是将XML文档树按照特殊的标准排列成序列,将序列的相似性作为XML文档的相似性。排序过程中对兄弟节点的顺序有非常强的依赖性,这正和数据中心XML文档的特点相悖,从而影响了最后结果的准确性。本文分析了编辑图算法的特点和不足,提供改进的方向。最后,根据编辑图算法和路径算法的思想提出拆分编辑图算法。这个算法仍然属于编辑距离算法。首先将待比较的2棵树分别拆分成子路径集,然后比较2个子路径集的相似度,最后将子路径集的相似度作为XML文档的相似度。本文通过举例说明算法的计算过程,对算法的特点和不足之处进行分析。通过实验,将拆分编辑图算法和编辑图算法进行比较,实验结果表明该算法降低了传统编辑图算法中对同层节点出现顺序的依赖性,具有更高的准确度,可以记录编辑脚本,描述改变过程,比编辑图算法更适合于数据中心XML文档。该算法要求在拆分过程中将节点进行编码,以保证能够区分标记相同但位置不同的节点。由于内部节点经过拆分会出现在多条子路径上,所以算法中要保证对每个节点操作的唯一性。最后,对拆分编辑图算法的前景进行了展望,作为一个拥有较高准确性的相似性算法,它可以广泛应用到XML聚类、挖掘、索引等诸多领域。随着新的子路径比较方法的出现,它还可以进一步变化,拥有较强的扩展性。