一种基于结构耦合度的推断目标节点的方法

李瑞霞，苏守宝，周先存

（皖西学院信息工程学院，安徽 六安 237012）

近年来XML关键字检索的方法大量用于信息检索中，主要得益于它带给用户很多便利，用户不必了解XML文档的结构或者掌握复杂的查询语言，就可以获得比较理想的结果.许多研究都注重如何有效地获得关键字匹配的节点（XSEarch，SLCA）［1－2］返回查询结果.然而这只是解决了信息检索问题的一个方面.即返回结果可能是有意义的，却不一定是用户所期望的.因此，问题的另一个方面就是如何准确地推断用户的查询意图.在一篇文档中一个关键字可能会有多个意义，例如，用户输入的查询关键字是｛volume，11｝，在一篇文章中“11”可能表示文章所在的页面，也可能表示该文章于第“11”期出版，到底用户的目标节点是什么呢？往往是很难判断的.

为了解决关键字的二义性，文献［3］通过一种改进的TF－IDF排序模型，利用关键字出现的频率来推断用户的查询目标节点.文献［4］将关键字出现的位置进行分别考虑，即分别对元素节点和文本节点赋予不同的系数，进而结合文档的层次改进了XReal的方法.但是以上的方法都是强调了关键字出现的频率，没有考虑文档的结构，尽管分别涉及了关键字所在的层次，但是因子r是不变的.文献［5］针对XReal方法提出了动态调节因子r的方法，虽然查询精度有所改变，但没有考虑XML中的结构耦合度对目标节点的影响.本文提出一种考虑文档结构耦合度的推断目标节点的方法，该方法一方面考虑关键字出现的频率，同时也考虑了关键字所在路径的层次，通过对某一路径中重复的路径数进行分析，准确地推断用户的目标节点.

1 相关方法

1.1 XML文档的表示

一篇XML文档通常可以看作由连接节点和叶子节点组成的无序树结构，其中连接节点表示元素或者属性节点，叶子节点指的是文本节点即元素或者属性的值.图1展示了一个XML文档的树结构.

定义1：节点类型，本文用root表示一棵树的根节点即文档的根元素，节点n的类型就是从根节点到节点n的路径.如果n是一个叶子节点，则它的路径用其双亲的路径来表示.

一个节点的类型准确地表示了该节点的意义.如图1所示，author节点的类型即路径（sigmord Record，issue，articles，article，author）.为了描述简单起见，本文在余下的部分将用节点名称代替其路径来表示节点的类型.

关键字查询指的是获取由查询关键字组成的有限集合，例如，给定一个关键字查询｛k1，k2｝和一篇文档，用t表示文档的树结构.关键字查询就是在树t中查找所有的连接节点和叶子节点中包含关键字｛k1，k2｝的节点片段.

图1 SigmodRecord数据集部分结构

1.2 XReal

XReal作为一个获取目标节点的典型方法，利用一个实例来简要阐述其主要思想.一般来讲，每一次查询只可能有一个期望的目标节点，在XReal中利用下面的方法获得目标节点.

1.3 耦合度

耦合度是软件设计中各个构件之间相互关联程度的一种度量［6］.耦合度的强弱往往取决于各构件间的接口复杂性、进入或调用模块的位置、方式以及通过接口传送数据的多少等，在设计一个软件时应该追求尽可能松散耦合的系统.通常在面向构件的软件设计中，构件的内聚度体现的是构件各成分间相互的紧密程度.也就是说，它可以度量单个构件所完成的各类任务在功能上的相互关联程度.随着面向构件技术的广泛应用，面向构件系统的内聚度和耦合度概念已成为一个重要的研究方向.

文献［7］在获取用户查询目标节点的方法中也涉及了结构耦合的概念，本文为了能准确地推断目标节点的类型，将耦合度的概念应用到树结构中来，首先对路径之间的耦合关系进行分析，然后，引入结构耦合度的概念，最后，提出一种基于结构耦合度的目标节点推断方法.

2 目标节点推断方法

2.1 结构耦合度

从以上的分析中可以看出，XReal方法在结构树中层次比较多的时候，一些目标节点可能因为指数函数递减过快而导致得分小于它的祖先节点，因此，最后返回给用户的就是一些无意义的信息.究其根源主要是公式的第二部分不能起到很好的抑制作用.本文将借鉴软件工程中耦合度的概念分析树结构中路径的耦合度，以此对XReal方法中的抑制因子进行适度的调节.

如图2所示的树结构中对于给定的查询｛k1，k2｝，图中A1，A2和A3都可以作为目标节点返回，并且3个结构中查询节点出现的频率相同，路径的层次也相同，然而，A1和A3的结构为一个紧耦合的结构，A1和A3类型的路径中重复的路径比较多，因此我们通常认为，A1和A3比A2更能准确地反映用户的查询意图.

本文规定节点所在的层次数减去包含了查询关键字的最低共同祖先节点的层次数来得到某类型节点的结构耦合度［8］.如图2所示，A1和A3的耦合度是2，而A2的耦合度是1.显然结构耦合度越高的节点类型越接近用户的查询目标.因此本文通过结合文章中节点出现的频率、节点所在的层次，同时利用树结构中耦合度来避免因抑制因子递减过快导致错误的推断.

图2 不同耦合度的树结构

2.2 相关度计算模型

经过如上的分析，本文定义目标节点的计算公式为

式中：depth（T）－θ表示结构的耦合度；θ表示k出现的路径中重复的路径数.然后针对结构中有部分或者极少数路径层次比较大的情况，本文为了避免层次不均匀出现的异常情况，对其做如下的处理：

式中：avg－depth表示一个文档树结构平均的路径长度；η是一个取值在［0，1］之间的调节参数.通过引入结构耦合度的概念可以保证目标节点包含足够的信息量.同时对于给定关键字检索，由于XML文档的树形结构特征，使得层次越深的节点很有可能具有更高的计算结果，本文通过一个分段函数来均衡结构不均匀出现的异常，也在一定程度上去掉了冗余的信息.

3 实验分析

本文实验平台采用Windows Server 2000，实验数据分别选择了DBLP和SigmodRecord做测试，利用Java编程实现所提出的方法，对比方法选择了XReal.关键字出现的位置随机测试，可能出现在XML文档中的元素节点，也可能是在属性节点或文本节点上，所使用的测试用例涵盖了这几种关键字出现的位置信息.DBLP和SigmodRecord数据集都记录了关于文章的信息，虽然结构语义较简单，但是信息量相对大一些.部分测试结果见表1.从表1的查询结果可以看出，在数据信息较少的情况下XReal可以较为准确地获得目标节点的类型，但是随着数据量的增大，XReal过度的夸大了词频的作用，在层次较大的结构中，如果结构耦合度比较低，结果导致将目标节点的祖先节点返回.而本文所提出的方法很好地解决了该问题.

表1 2种数据集上的部分测试结果

查准率是衡量信息检索质量的一个重要指标，图3表示的是在2种不同的数据集下，平均的查准率.从图3中可以看出，本文所提出的方法在数据量比较大的情况下优势更为明显.结果更为准确.

图3 2种数据集下的查准率的比较

4 结论

在信息检索中能否准确地推断出用户的查询意图，对查询结果起着至关重要的作用.由于XML数据半结构化的特征和查询关键字的二义性使得推断目标节点成为难题.本文经过分析现有研究的不足，提出了一种目标节点的推断方法，该方法分别结合词频和关键字的路径耦合度推断目标节点.最后对结构不均匀的情况也做了处理，可以去除部分的冗余信息.实验证明，与现有主流算法相比较，本文提出的方法能够更准确地推断出用户的查询意图.我们今后将就检索效率进行研究，以进一步提高本文算法的查询性能.

［1］COHEN S，MAMOU J，KANZA Y，et al.A semantic search engine for XML［C］.In Proceedings of the 29th VLDB Conference，Berlin，Germany，2003：45－56.

［2］LIU Z，CHEN Y.Identifying meaningful return information for XML keyword search［C］.In：Chan C Y，Ooi B C，Zhou A（eds.）.New York：SIGMOD Conference，2007：329－340.

［3］BAP Z，LING TW，CHEN B，et al.Effective XML keyword search with relevance oriented ranking［C］.In：ICDE，IEEE International Conference on Data Engineering，Los Alamitos，2009：517－528.

［4］郭文琪，陈群，娄颖.一种推断 XML关键字检索目标节点的方法［J］.计算机工程，2012，38（8）：41－49.

［5］JIANG LI，JUNHU WANG.Effectively inferring the search－for node type in XML keyword search［J］.Lecture Notes in Computer Science，2010，5981：110－124.

［6］郁湧，张坤.基于结构熵的构件耦合性度量方法［J］.计算机应用与软件，2012，29（6）：33－35.

［7］JIANXIN Li，CHENGFEI LIU，RUI ZHOU.XML keyword search with promising result type recommendations［DB］.World Wide Web，2013：1－33.

［8］XU Y，PAPAKONSTANTINOU Y.Efficient keyword search for smallest LCAs in XML databases［M］.In Ozcan F，ed.Proc of the ACM SIGMOD Int'1Conf on Management of Data，Baltimore：ACM Press，2005：537－538.