XML文档语义检索方法研究

莫正波，宋 玲，吕 强，邓 薇

1.青岛理工大学 理学院，山东 青岛 266033

2.山东建筑大学 计算机科学与技术学院，济南 250101

3.国网技术学院 电网检修培训部，济南 250002

4.山东科技大学 基础课部，山东 泰安 271021

XML是一种元标记语言，它提供描述结构化资料的格式，可用于创建标记语言。它以其良好的数据存储格式、可扩展性、高度结构化、便于网络传输等优势在许多领域得到广泛应用，XML便于网页信息组织，不仅能满足不断增长的网络应用需求，而且还能够确保在与网络进行交互时，具有良好的可靠性与互操作性。XML具有可扩展性、灵活性以及自描述性。随着XML的数据存储、网络信息交互、数据发现和挖掘、XML版本控制、半结构数据的整合、以及XML文档检索的蓬勃发展，使得XML的检索目前来说始终是一个研究重点。

XML文档可以被模型化为有序标签树，一个XML文档的例子及其树模型如图1所示。对应一个XML文档的所有路径组成的集合叫做XML文档的路径集，如图1（b）的路径集为{articles/article/title/Data Mining，articles/article/author/Febio，articles/article/keywords/Data Mining Algorithms}。

图1 一个XML文档及其树表示

1 相关研究

XML信息检索技术可划分为以下几种研究方向：基于XML数据查询语言XPATH[1]、XQuery[2]的检索；基于关键词的面向XML文档内容的检索[3]；以及基于XML文档结构以及内容的检索[4-5]。其中最后一种检索由于同时考虑了XML的文档结构以及语义特点，是目前研究的一个主要方向，在该类方法的研究中一般采用编码或者建立索引的方式考虑内容方面，通过路径考虑结构方面的检索[6-7]。基于用户查询（将用户查询可以描述为一个XML文档）和XML文档之间相似度的方法是将用户的查询与XML文档集中的每个XML文档都计算相似度，并根据相似度值返回检索结果。对于XML文档相似度的计算，许多学者进行了广泛的研究，文献[8]将这些方法分为三类：基于编辑距离的方法、基于信息检索的方法以及其他方法。基于编辑距离的方法基本思想是将两棵树之间的距离定义为利用编辑操作实现一棵树到另一棵树转换所需的代价。显然，距离和相似度之间成反比关系，树之间的距离越小，则相似度越大。树之间的编辑操作主要有三种：插入、删除和替换[9-10]，但它们的复杂度比较高。在文献[11-12]中，研究者不但把插入、删除操作限制在叶节点上，还增加了一种重定位子树的移动操作。然而，这种算法并不能保证最优的结果。Chawathe的方法把插入、删除操作限制在文档树的叶节点上，并且允许在树的任何地方重定义节点标签，Chawathe算法的总体复杂度为O(N2)，其中N是参与比较的标签树中拥有最多节点的树的节点数。该算法的性能和效率较高[13]。Nierman和Jagadish在计算XML结构相似度尤其是子树相关的相似度中，具有更好的精度并且能保持在二次方的复杂度[14]。以上基于编辑距离的相似度方法适用于结构严谨的数据型（data-centric）XML，而基于信息检索的相似度方法适用于结构松散的文档型（document-centric）XML，主要应用于排序的XML查询（ranked XML querying）。Fuhr和Großjohann对 XML文档元素或不相交的子树进行索引[15]。为了满足用户对于XML文档中的部分检索要求，Grabs和Schek提出块索引方法[16]。为了能体现XML文档的结构，Schlieder和Meuss提出了一种拓展的向量空间模型，把词条的标准概念拓展成了结构词条，一个结构词条表示一棵标签树[17]；Pokorny和Rejlek把XML用标签树来表示，并且应用了路径这一概念，把XML抽象成了一个矩阵而不是简单的向量，查询和文档之间的相似度也就转化成了相应矩阵之间的相似度计算[18]。其他的XML相似度方法包括标签相似度、边匹配[19]、路径相似度[20-21]等。但目前这种相似度的检索方法用得比较少，主要原因在于用户的查询请求很少用XML文档直接描述，其次如果将用户的查询与XML文档集中的每个XML文档在充分考虑文档结构和语义内容的情况下计算相似度，并根据相似度值返回检索结果，这种方法的计算复杂性比较高。

但是在一些情况下，当用户的查询请求通过XML文档很清晰地描述出来，这时基于相似度的检索在排序方面就具有了一种明显的优势，基于该应用背景，本文提出一种有效的XML文档检索的方法，主要贡献是提出了粗糙过滤和精确匹配的思想，具体如下：（1）过滤阶段，利用签名技术，将大量无关的XML文档进行过滤，得到可能与用户查询相关的文档，该方法大大缩减XML数据查询集，降低精确匹配过程中的计算复杂度。（2）精确匹配阶段，综合考虑了元素的相似度和路径的结构信息，计算XML文档之间的相似度。

2 语义检索方法框架

给定XML文档集D和用户查询q，XML检索即是从D中查找出符合q的XML文档。为了提高计算效率，同时考虑XML文档的结构和语义，本文在计算用户查询与XML文档相似度的过程中包括三个阶段：（1）用户的语义查询扩展阶段，利用本体对用户的查询路径进行同义词扩展。（2）过滤阶段，利用查询词的签名逐一与各个XML文档签名进行匹配，查找可能相似的XML文档，此处所得到的一系列XML文档并不一定就是用户所希望得到的，但是数据集中所有与用户查询相关的文档都包含在了这些小范围的XML文档中。此步操作是进行正式搜索的预处理工作，目的是大大缩减XML数据查询集，降低算法的复杂度提高算法性能和效率。（3）精确计算阶段，综合考虑了元素的相似度和路径的结构信息，精确计算查询与文档之间的相似度。

算法的主要思路如图2所示，该算法分为三步：首先，基于WordNet对用户查询q进行同义词扩展得到q'；然后，将q'和D中的每一篇XML文档都进行数字签名，并通过签名之间的匹配对D进行有效过滤，除去大量不符合用户查询的文档，得到一个文档子集 D′,D′⊆D；最后，对q'与D'中的文档进行精确匹配得到检索结果。

图2 算法流程图

3 XML文档过滤

3.1 布隆过滤器

布隆过滤器是一个很长的二进制向量和一系列随机映射函数，用于检索一个元素是否在一个集合中。其基本思想就是用一个或多个hash函数对数据集中的每个成员做映射，映射结果不是存在完整的hash表中，而是一个位向量（bit vector）中。位向量所有位初始都为0，根据hash结果将位向量中相应位置1。对数据集中的所有成员的hash计算完成后，就得到了该数据集的位向量。当需要判断一个元素是否属于该数据集时，也用相同的hash函数对其映射得到它的位向量，然后将其位向量上所有为1的位与数据集位向量上相应位比较，如果发现数据集的位向量上某个位为0的话，可以判断这个元素不属于该数据集，这样的一个结果是肯定的。而如果所有相应位都为1的话，那么该元素可能属于这个数据集。

如果由布隆过滤判断某个元素属于一个集合，但事实上却不是，那就是误判。假如集合成员数为n，用k个函数映射后，m位向量上某个位为0的概率为：(1-1/m)k×n,某个位为1的概率就是(1-1/m)k×n,而如果要判断一个数是否属于该集合，其所有映射位和集合向量的所有匹配的概率就是(1-(1-1/m)k×n)k。从上式看出，当m越大，误算的概率就越低。但是m越大，所占空间就越大。

3.2 用户查询词的语义扩展

对于用户所给的查询词，即关键字，首先要经过查询扩展处理。通常不能因为两篇文档缺乏公共关键字就断定它们一定是不相关的。同样在用户利用关键词进行查询时，某一文档不包含用户枚举的关键字时也未必说明此文档不符合用户的查询要求。如，用户想了解关于“car”的信息，但是某一文档中所涉及内容为“motor”，则此文档也极有可能符合用户的需求，也就是说要得到良好的查询结果应该把语义考虑进来。在本文中，先把查询词进行同义扩展，即利用WordNet[21]这一工具查找出用户给定的关键字的所有同义词，并利用所得到的同义词和原来关键字一并作为新的关键字进行查询。WordNet是由Princeton大学设计的一种基于认知语言学的英语词典。语言中的词汇是按照同义词类组织在一起的，每个词类都对应一种“潜在的概念”，词类与词类之间通过不同的方式联系，将单词按照其意义组成一个“单词的网络”，它是研究语义相关性的有力工具。如用户输入查询“author/Fabio”，利用WordNet将“author”语义扩展为“writer，generator，source”。

3.3 用户查询及XML文档的布隆过滤器签名

用户在进行查询时，通过多条查询路径，构成路径查询集。如用户的查询是author为Fabio并且title为data mining，对用户查询集中的每个词进行同义词查询扩展并逐一进行签名获得其对应的向量。

解析数据集中的每个XML，把它的所有标签节点、属性节点、值节点全部解析出来，得到对应的文本文档，将其通过与以上类似的方法利用布隆过滤器进行数字签名。

3.4 用户查询及XML文档签名匹配

利用查询词的签名向量逐一与各个XML文档向量进行匹配查找可能的目的XML文档，此处所得到的一系列XML文档并不一定就是用户所希望得到的，但是数据集中所有与用户查询相关的文档都包含在了这些小范围的XML文档中。此步操作目的是大大缩减XML数据查询集，接下来再对这些小范围XML数据集进行搜索查询即可。

4 用户查询与XML文档相似度的计算

用户查询与XML文档之间的相似度与它们之间的共性和差别相关，它们所拥有的共性越多，则相似度越大，差异越多，则相似度越小。由于XML文档可扩展性和高度结构化的特点，XML文档之间相似度比较至少要涉及到两个层次：结构的比较以及标签（label）名和内容的比较。因为路径能够部分表示XML的拓扑结构，所以可以基于路径来表示文档的结构信息，并考虑路径上标签的语义信息来计算XML文档间的相似度。概括来说，首先将XML文档解析成标签树，将标签树分解为从根到叶子节点的路径集，因此通过比较路径集之间的相似度得到文档之间的相似度。对于路径之间相似度比较需要考虑路径元素之间的语言相似性和结构位置的相对有序性。在以往的工作中，提出了一种计算基于XML结构特征和语义内容特征计算XML文档相似度的方法[22-23]，方法描述如下：

对于路径Pa={ea1/ea2/…/eam}和路径Pb={eb1/eb2/…/ebn},s[i,j]被定义为子序列Pai(Pai={ea1/ea2/…/eai}(i≤m))和Pbj(Pbj={eb1/eb2/…/ebj},j≤n)的路径相似度，则Pa和Pb的相似度值为s[m,n]，公式（1）递归地求解路径之间相似度。

其中ESim(xi,yj)为节点xi,yj之间的编辑相似度和语义相似度的最大值。由于在XML文档中，层次高的节点（离根节点更近的节点）往往比层次低的节点（离根节点较远的节点）更能反映文档的结构信息，在计算相似度时，必须把节点所处的层次考虑在内。为了反映这一特点，本文对路径中各个节点赋不同的权值，越靠近根节点，被赋予的权值越大，也就意味着对路径相似度的贡献越大。有权路径就是对路径中的每个节点都赋给一个非负数的权值。路径p的最大深度为h，对于节点x位于第m层（从叶子节点到x的路径长度），那么x的权重就被赋值为γh-m(0＜γ≤1),其中γ为一参数。

为了便于比较，对于路径Pa={ea1/ea2/…/eam}和路径Pb={eb1/eb2/…/ebn}，公式（2）将公式（1）归一化到区间[0，1]。

令d为一个XML文档，Pd为其对应的路径集，Q为路径查询集。d和Q的相似度定义如公式（3）所示：

5 实验

为了测试本文提出的方法，本文XML实验数据集来自于（Niagara，http：//www.cs.wisc.edu/niagara/data/）和 IBM XML generator（http：//www.alphaworks.ibm.com/tech/xmlgenerator），共有1 039个文档，为了测试XML文档的语义和结构，从1 039个文档中拷贝了600个文档，将这600个文档通过标签名或内容语义替换或结构删除的方式进行了改变，共得到1 639个文档。

用户查询通过5个在校大学生获得，首先给用户一些包含在XML文档中的内容信息的一些例子，如图3所示。这些信息没有结构，要求用户从这些例子中生成用户查询，自由选择结构和标签名，通过XML文档来描述得到的30个用户查询。

图3 用来生成查询的例子

为了测试本文提出的方法，实现了文献[24]中提到的相似度方法，在文本将之记为XMLSim，并用来进行测试比较。本文对用户查询和1 639个XML文档首先离线签名，通过粗糙过滤后，然后利用QXMLSim计算用户查询与相关XML文档的相似度，并排序输出结果。为了对结果进行评价，本文采用前k个检索结果的查准率以及算法运行时间作为评价标准，如图4和图5所示。

图4 经过粗糙过滤以及QXMLSim相似度计算与XMLSim的检索运行时间比较

图5 经过粗糙过滤以及QXMLSim相似度计算与XMLSim的平均查准率比较

通过图4可以观察到随着数据量的逐渐增大，经过粗糙过滤以及QXMLSim相似度计算两个步骤的运行时间大大降低，通过分析可以得出通过粗糙过滤可以有效地提高运行时间的结论。通过图5，可以发现本文提出的方法在top k查准率略有提高，主要原因是利用了WordNet进行查询扩展。

6 结束语

本文提出一个通过空间换时间的一种有效的检索方法，将检索过程分为两步，首先是过滤阶段，利用签名技术，将大量无关的XML文档进行过滤，得到可能与用户查询相关的文档，该方法大大缩减XML数据查询集，降低精确匹配过程中的计算复杂度。其次在精确匹配阶段，综合考虑了元素的相似度和路径的结构信息，计算XML文档之间的相似度。通过实验表明本文提出的方法在运行时间上有了较大的提高，查准率也略有提高。

[1]XPath：XML path language（XPath）2.0.[EB/OL].[2011-12-18].http：//www.w3.org/TR/xpath20/.

[2]XQuery 1.0：an XML query language（Second Edition）[EB/OL].[2011-12-18].http：//www.w3.org/TR/xquery/.

[3]孔令波，世渭，杨冬青，等.XML信息检索中最小子树根节点问题的分层算法[J].软件学报，2007，18（4）：919-932.

[4]万常选，鲁远.基于权重查询词的XML结构查询扩展[J].软件学报，2008，19（10）：2611-2619.

[5]刘喜平，万常选，刘德喜，等.有效的XML模糊内容与结构检索和计分[J].计算机研究与发展，2010，47（6）：1070-1078.

[6]胡锦南.面向XML文档集的检索技术研究与系统实现[D].合肥：中国科学技术大学，2009.

[7]向永清，邓志鸿，于航，等.面向XML文档的二级索引技术及其在XML关键词检索中的应用研究[J].计算机研究与发展，2009，46（z2）：748-755.

[8]Tekli J，Chbeir R，Yétongnon K.An overview on XML similarity：background，currenttrends and future directions[J].Computer Science Review，2009，3（3）：151-173.

[9]Shasha D，Zhang K.Approximate tree pattern matching[M]//Pattern matching in strings，trees and arrays.[S.l.]：Oxford University Press，1995.

[10]Zhang K，Shasha D.Simple fast algorithms for the editing distance between trees and related problems[J].SIAM Journal of Computing，1989，18（6）：1245-1262.

[11]Chawathe S，Rajaraman A，Garcia-Molina H，et al.Change detection in hierarchically structured information[C]//Proceedings ACM SIGMOD，Canada，1996：26-37.

[12]Cobéna G，Abiteboul S，Marian A.Detecting changes in XML documents[C]//Proceedings of the IEEE International Conference on Data Engineering，2002：41-52.

[13]Chawathe S.Comparing hierarchical data in external memory[C]//Proceedings of the VLDB Conference，1999：90-101.

[14]Nierman A，Jagadish H V.Evaluating structural similarity in XML documents[C]//Proceedings of the 5th ACM SIGMOD International Workshop on the Web and Databases（WebDB），2002：61-66.

[15]Fuhr N，Großjohann K.XIRQL：a query language for information retrieval[C]//Proceedings of ACM-SIGIR，New Orleans，2001：172-180.

[16]Grabs T，Schek H J.Generating vector spaces on-thefly for flexible XML retrieval[C]//Proceedings of ACM SIGIR’02 Workshop on XML and Information Retrieval，2002：4-13.

[17]Schlieder T，Meuss H.Querying and ranking XML documents[J].Journal of the American Society for Information Science，2002，53（6）：489-503.

[18]Pokorny J，Rejlek V.A matrix model for XML data[C]//the 6th International Baltic Conference DB&IS，2005：53-64.

[19]Kriegel H P，Schönauer S.Similarity search in structured data[C]//Proceedingsofthe 5th InternationalConference on Data Warehousing and Knowledge Discovery（DaWaK 03），Czech Republic，2003：309-319.

[20]Rafiei D，Moise D，Sun D.Finding syntactic similarities between XML documents[C]//Proceedingsofthe 17th International Conference on Database and Expert Systems Applications（DEXA），2006：512-516.

[21]WordNet[EB/OL].[2011-12-18].http：//wordnet.princeton.edu.

[22]Song Ling，Li Shengen，Lv Qiang，et al.An approach for measuring similarity between XML documents[C]//6th InternationalConferenceon Fuzzy Systemsand Knowledge Discovery，2009，7：410-414.

[23]Song Ling，Ma Jun，Lei Jingsheng，et al.Semantic structural similarity measure for clustering XML documents[C]//Lecture Notes in Computer Science（LNCS），2009：232-241.

[24]Nayak R，Iryadi W.XML schema clustering with semantic and hierarchical similarity measures[J].Knowledge-Based Systems，2007，20（4）：336-349.