XML文档数模型和树路径模型算法比较

摘要:本文对传统的XML文档树模型和树路径模型算法进行了研究,在准确率、召回率和平均时间消耗上进行了比较,对两模型算法的特点和不足进行了总结。

关键词:XML;树模型;树路径模型;算法

中图分类号:TP311.1 文献标识码:A文章编号:1007-9599 (2010) 05-0000-02

XML Document Tree Model&Tree Path Model Comparison

Su Huiqun

(Shuda College of Hunan Normal University,Changsha410012,China)

Abstract:In order to compute the structure similarity of XML effectively,XML document tree model and tree path model are studied,the precision,recall and average time consumed on a comparison of the two model characteristics and shortcomings of the algorithm are summarized.

Keywords:XML;Tree Model;Tree Path Model;Algorithm

XML(Extensible Markup Language)已经成为Internet环境中数据表示和交换的标准。随着XML越来越被广泛地应用,基于XML数据管理和查询的研究受到了人们的重视,并且取得了丰硕的成果。

一个XML文档可以模型化为一棵树或一个图,两个XML文档间的相似度可以用这两棵树(图)间的距离来度量。在XML出现之前,已有许多工作[1-5]研究了两棵树(图)的相似测度的问题,其中最自然和应用最广的测度是树的编辑距离。Tai[1]最早提出了利用编辑距离来度量两棵树(图)间的差异。在Tai的工作的基础上,Zhang和Shaha[2-4]等提出了计算两棵树间的各种编辑距离的算法。

Sachindra Joshi[6]等人提出了用DOM树中的对应的路径来表示文档的结构信息,称为树路径模型,并给出了相应的相似度计算方法。

一、树模型与动态规划算法

XML文档可以用一棵带标记的树表示,树中每个结点对应文档中的一个元素,结点标记对应元素名。这棵带标记的树也称为DOM树(文档对象模型树)。

而XML文档之间的相似度计算的问题就可以转化为树之间相似度的计算。

Tai[1]最早使用编辑距离来计算两棵树间的相似度。其基本思想是将两棵树间的距离定义为利用编辑操作将一棵树转化为另一棵所需的代价。并且定义了三种操作称为编辑操作。Zhang和Shasha等给出了一个求两棵无序树间的受限ED距离的动态规划算法,时间复杂度为 ,其中与分别表示树 和 的高度叶子数。有了两棵树的ED距离,便可很快求出两棵树间的相似度[1],具体算法请看参考文献[1-5]。

二、树路径模型算法

XML文档还可以用一个多重集合(集合元素可重复)表示:该多重集合所有元素为XML文档对应的DOM树中所有从根结点到叶结点的路径。

对于不同的叶结点,若对应路径上各节点的标记相同,则路径也相同。假设有 个待比较的文档,定义 为这 个文档所对应的n棵DOM树集合,为简单起见, 表示文档 , 为 中叶子结点个数, 中路径集合记为 。 为 个文档所有路径 的集合, 。

(一)路径的选择和权重的赋值

当文档数很大时,路径集 里路径数也会很大,相似度计算中如果这些路径都参与计算,则计算量会很大。

考虑到不同的路径在相似度计算中发挥的作用是不一样的,因此,所有的路径没有必要都参与相似度计算。我们需要对路径进行选择,并对它们赋予不同的权重,其原理和文本分类中关键词的权重的计算和特征的选择一样,这里不再做冗余介绍。

(二)相似度计算方法

文档 用一个 维向量表示 ,其中 , 定义为路径 在文档 中出现频率,其中 。每条路径根据出现频率不同,可以设置不同的权重 [10]。比较文档 , 结构相似度大小,计算公式为:

(2.2.1)

三、树模型与树路径模型比较

(一)两模型特性

树模型考虑了XML文档的结构特征,但是当树要描述全部结构信息时,树的结构将会很复杂庞大,这样很难处理,更重要的是它的时间复杂度很大,还有,对于文档中存在的元素重复和元素可选问题树模型不能很好处理。

树路径模型比树模型要简单,而且时间复杂度要低很多,在文档类别数很少,且不同类别的文档的结构相差较大的情况时,取得了良好的聚类效果,而且处理了文档中重复元素问题。再者,对每一条路径赋予不同的权重,使计算结果更合理,更符合人的直观理解。

对于计算两个文档的相似度的时间,由公式(2.2.1)易知,为 , 为经过路径选择后 中路径的数目,不过在计算两个文档相似度之前需要进行预处理,即计算 和 ,时间复杂度为 ,其中 为文档数, 表时 个文档平均的叶结点数(即路径数)。

树路径模型虽然弥补了树模型部分缺陷,但自身也有很多的不足:

首先,树路径模型只考虑了结点的父子关系,却忽略了同父兄弟结点之间的关系,即路径出现的先后顺序未被考虑,没有考虑到各种路径的权重,而且比较路径相似度时用的是路径的完全匹配,不能在不完全匹配时更精确的描述路径之间的相似度。当文档路径组成大致相同而顺序不同时,树路径模型无法描述真实情况而得到合理结果。

其次,树路径模型需要一个训练文档集用于进行预处理计算 ,使得计算结果依赖于训练文档,通用性大大减弱。

(二)实验结果

下面通过实验来验证这两个模型及其相关算法的有效性,一共选取三个实验数据集,一个是SIGMOD Record文档集,另外两个是CADLIS的内部数据集,下面是这三个数据集的具体情况:

表1 实验数据集信息说明

文档集编号 文档集 文档数 平均大小 类别数

1 SIGMOD Record 924 2KB 3

2 CADLIS 1 450 54KB 9

3 CADLIS 2 1000 33KB 10

我们进行树模型的动态规划算法和树路径模型算法的比较,实验环境是Eclipse,JAVA1.5,具体结果如下表:

表2 XML文档结构相似度算法比较结果

文档集编号 算法 准确率 召回率 时间平均消耗(ms)

1 树模型的动态规划算法 0.997078 0.995623 1

树路径模型算法 0.788372 0.707950 1

2 树模型的动态规划算法 1.0 0.805555 286

树路径模型算法 0.736343 0.722222 43

3 树模型的动态规划算法 0.963421 0.95 210

树路径模型算法 0.792063 0.71 46

从上表中我们可以看到,随着文档数的增加,树模型的动态规划算法在准确率、召回率方面始终优于树路径模型算法,但时间平均消耗上大大多于树路径模型算法。

四、结束语

本文阐述了树模型和树路径模型在计算XML文档相似度时算法,通过实验对两模型算法的特点进行了比较,总结了两模型算法存在的问题。

参考文献:

[1]Tai K C. The tree to tree correction problem. Journal of the ACM, 1979,26(3): 422-433.

[2]Wang J T-L,Zhang K.Exact and approximate algorithms for unordered tree matching. IEEE Transactions on Systems,Man and Cybernetics,1994,24(4): 668-678.

[3]Zhang K, Shasha D. On the editing distance between unordered labeled trees. Information Processing Letters,1992, 43(3): 133-139.

[4]Zhang K.A constrained editing distance between unordered labeled trees.Journal of Algorithmica,1996,15(3):205-222.

[5]Wang J T-L,Shasha D et al. Structural matching and discovery in document databases. Sigmod Record,1997,26(2):560-564.

[6]Sachindra Joshi,Neeraj Agrawal, Raghu Krishnapuram and Sumit Negi. A Bag of Paths Model for Measuring Structural Similarity in Web Documents. SIGKDD’03, August 24-27, 2003