XML检索研究综述
刘丹1, 孔少华1, 陆伟2
1.北京大学信息管理系 北京 100871
2.武汉大学信息资源研究中心 武汉 430072
摘要

从信息检索流程对XML检索的研究情况进行综述。主要对XML查询语言、XML索引、XML检索排序方法以及XML检索评价4个方面的研究情况进行评述,并对XML检索研究的一些热点领域进行介绍,最后就需要继续深入研究的问题进行简要说明。

关键词: XML检索; XML查询语言; XML索引; XML检索模型; XML检索评价; XML检索研究热点
Research Review on XML Retrieval
Liu Dan1, Kong Shaohua1, Lu Wei2
1.Department of Information Management, Peking University, Beijing 100871, China
2.Center for Studies of Information Resources, Wuhan University, Wuhan 430072, China
Abstract

This paper reviews the research on XML retrieval from the prospect of information retrieval process. At first, the paper reviews separately on four parts:XML query language, XML indexing, XML retrieval ranking approaches, and evaluation of XML retrieval. Then, a number of XML retrieval hotspots are introduced. At last, it summaries and briefly describes some issues which need further study.

Keyword: XML retrieval; XML query language; XML indexing; XML retrieval models; XML retrieval evaluation; XML retrieval hotspots
1 引 言
1.1 半结构化信息检索

半结构化信息介于结构化和非结构化信息之间,它有严格的结构,但不如结构化的数据库模式严格。XML就是一种典型的半结构化信息。一个正确定义的XML文档有固定的结构,明确地定义了文档的不同语义部分,充分利用这些信息可以为XML文本提供强大而又灵活的检索和访问方式。

半结构化信息的检索方法最初于20世纪80年代后期提出。由于XML在1998年成为W3C推荐标准,人们越来越关注半结构化文本的检索。2002年INEX(INitiative for Evaluation of XML Retrieval)测评会议的成立首次为XML信息检索的研究提供了统一的平台,INEX会议是类似于TREC会议的专门为XML检索不同方法提供统一测评的检索测评活动[ 1]。到目前为止,INEX是最全面、最深入地研究XML检索的活动。

本文跟踪了INEX会议自2002年始至2010年止的所有会议论文,以及ACM SIGIR(Special Interest Group on

Information Retrieval)自2003年始每年关于XML检索的Workshop,并以这些会议论文作者和主要参考文献为源,查阅了自半结构化信息检索提出以来的经典文献(使用Google Scholar查阅被引次数高的文献),在此基础上对XML检索的各方面进行综述性的介绍。

1.2 XML检索问题

对XML文档进行检索(查询)请求的描述有两种方式[ 2]:数据库角度的XML查询方式(XML Query)和信息检索角度的XML查询方式(XML IR)。信息检索角度的XML查询又包括三类:扩展了数据库角度XML查询方式的XML查询;直接将关键词查询延伸至XML查询;直接使用XML片段来描述查询请求。其中,第一种查询方式主要用于支持XML的数据库查询,第二种方式中的第三类查询方式很少使用。本文是从信息检索的角度探讨XML检索,因此谈到的XML检索指的是第二种的第一和第二类的检索方式。

在XML检索中,文档内部各层次的XML元素理论上都是可检索的单元,检索系统对于用户查询的返回结果一般都是文档中具体的XML元素。这种聚焦式的检索有助于对含有大量长文档的信息库和包含多检索主题文档的查询,呈现在用户面前的将是文档中最相关的内容。例如,一本书利用XML将段落、章节标记出来之后,可以在检索时返回与用户查询主题最相关的段落或章节,而不是单纯的整本书。在XML检索中,用户被引导到文档中最相关的部分,从而能够更容易地定位相关内容。这正是XML检索与非结构化文本检索相比的最大优点,即XML检索可以实现元素级的检索。

从信息检索的整个流程来看,XML检索主要研究包括以下几个方面:XML检索目标与用户需求、XML查询语言、XML元素与内容的存储索引、XML检索排序方法、XML结果呈现方式、XML检索评价。其中,XML检索目标与用户需求以及XML结果呈现方式是基于用户研究的;XML查询语言、XML元素与内容的存储索引、XML检索排序方法、XML检索评价是从检索系统角度来研究XML检索。

2 XML查询语言

在XML检索中,考虑到XML文档的结构信息,可以利用文档逻辑结构来检索出更符合检索请求的文档元素。这种文档逻辑结构通过合适的方式可以放到检索语言中,使用户可以直接对文档结构加以利用。XML检索查询语言按照是否加入结构限制分为CO(Content-Only)和CAS(Content And Structure)两大类检索语言。

CO检索语言一直以来是传统信息中的标准检索语言。在用户不知道或不关心XML文档逻辑结构的环境下可以使用这种检索语言。尽管只能从内容上进行检索限定,XML检索系统仍然能够检索出合适的XML层级元素。CO检索语言的例子有:XRANK[ 3],XKSearch[ 4],以及NEXI的CO查询[ 5]

CAS检索语言使用户可以从内容和结构上对检索请求进行限定。结构限定既可以指定在特定元素中查找(如:检索结果必须包含关于某个主题的Section),也可以指定返回结果的类型(如:检索结果应该是Section)。目前来看,CAS检索语言可以分为三类[ 6]:

(1)基于标签的查询语言,其允许用户为关键词指定标签名,从而限定返回元素的类型,如XSEarch[ 7];

(2)基于路径的查询语言,该类型语言往往是基于XPath定义的,典型的如:XIRQL[ 8]、XXL[ 9]、FlexPath[ 10]以及NEXI的CAS查询[ 5]等;

(3)基于从句的查询语言,该类型语言使用层叠的从句来表达检索条件,类似于SQL语言,如XQuery[ 11]、XQuery Full-Text[ 12]等,其中XQuery最具代表性,XQuery Full-Text则是在XQuery的基础上加入了谓词(如近似查询和相关排序)扩展。

3 XML索引

信息检索中经典的索引方法存储了词项统计信息以便于在检索过程中衡量一个词在文本中的重要性,进而区分相关内容和不相关内容。XML索引也需要存储类似的信息,但是需要对每一个元素的相应信息都进行存储。因为XML检索中没有预定义的返回单元大小,整篇文档、某个章节、或是一个孤立的段落均有可能满足检索要求。

在XML索引中,目前主要有如下三种策略:忽略结构和元素层级信息,将XML文档作为扁平文档进行索引;针对每个元素进行单独的索引;利用XML树的结构信息来对元素间关系进行索引。

3.1 扁平文档索引

扁平文档索引把XML文档看成是线性的字符序列,完全不考虑XML文档的结构信息。结构标签信息也被当作索引词。这种索引可以直接用现有的文本索引工具进行索引,很方便。这一方法主要适用于目前的文本检索实践,特别是Web搜索引擎中。Web搜索引擎在处理异构文档时把它们都当成了扁平的文档。

3.2 元素索引

元素索引考虑了XML文档的结构信息,把元素当成传统意义上的一个文档来用现有的文本索引工具进行索引。可以对每一种元素建立一个单独的索引,并行在每个索引上检索然后归并检索结果[ 13]。由于XML的元素大小有很大差别,长度太小的元素往往不是符合要求的检索结果,因此可以在索引之前选择长度大于某一制定阈值的元素来索引[ 14],或者根据检索式元素被用户指定的频率大小为依据,挑选频率大的来索引[ 14, 15]。由于XML文档的嵌套结构,元素之间具有大量的重复,而且所有文本信息均存在于叶子节点中,因此可以仅仅对叶子节点进行索引,非叶子节点的各种信息可以通过其叶子节点进行计算[ 16],元素之间的关系在后续检索过程中进行处理。这是一种折中的方法,既可以利用现有文本索引工具的成熟性,也可以得到XML文档的结构信息。

3.3 XML文档特有的索引

XML文档特有的索引考虑了结构信息,并且设计了针对XML的索引结构。以下提到的XML索引指的就是XML文档特有的索引。Luk等[ 17]根据索引中包含的结构信息把XML索引分为半结构索引和结构索引。

(1)半结构索引

半结构索引是指除了内容索引外,还索引了部分的结构信息,用于不是所有的结构信息都有必要索引的情况。半结构索引的实现方式有三种:

①基于域的索引(Field-based Indexing),它是最简单的半结构索引方法,其将一篇XML文档表示成一个域集合,如作者域、标题域等,域信息通过对XML文档的解析抽取获得;

②基于段落的索引(Segment-based Indexing),其将结构化文本分为几个不重叠的区域然后索引;

③基于XML树的索引(Tree-based Indexing),其把文档看成是一棵K叉树,为每一个节点赋以唯一的ID值,通过比较ID值可以得到节点之间的父子、兄弟关系,进而索引这些节点。

(2)结构索引

结构索引是指除了内容索引外,还索引了完整的结构信息,主要用于需要使用到完整的XML文档结构的时候。结构索引可以使检索结果非常精确,主要包括如下4种:

①信息检索/数据库索引(IR/DB Indexing)

信息检索/数据库索引最基本的就是使用关系数据库进行索引,可以将XML文档中抽取的信息(一般是元素)存入数据库,这样可以利用数据库方便地进行查询处理。

利用关系数据库实现XML结构的索引一般是根据XML文档的树结构特点设计数据库表项,将XML元素看成是XML树的节点或是边,然后将这些节点或边的信息存储到关系数据库中[ 18, 19]。一般来说,针对节点或边建立的表结构一般包含以下几项内容:

(元素标识,位置信息,元素内容)

其中,元素标识即为元素名称,位置信息根据对元素位置信息的不同记录方式而有所不同,而元素位置信息的记录方式直接影响到结构化检索的实现方式。一般来说,元素位置信息的存储主要有两种方式:用序号对形式(pre, post)来记录[ 20],pre表示节点的上一节点编号(或边的起始节点编号),post表示节点的下一个节点编号(或边的终止节点编号),为方便检索,经常还加入元素所在层信息(Level);对元素的信息进行编码,用码值来表示元素的位置信息,例如Dewey编码及其变种就广泛使用于各种支持XML的商业数据库之中。利用关系数据库实现XML的结构化检索主要是为了利用关系数据库已有的精确检索功能,在检索时,将XML查询请求转换成同等的SQL语句来执行数据库查询。

还有一种结合信息检索系统和关系数据库的方法,把关系数据库的每一个记录当成是信息检索系统的一篇文档,对这些记录进行索引。这样不仅可以利用数据库方便的优点,而且信息检索系统可以计算检索结果的相关度。

②基于路径的索引(Path-based Indexing)

基于路径的索引保持了两类索引:内容信息和结构信息。结构信息存储的是元素的路径信息。路径信息可以通过元素名称及其位置信息来表示,也可以直接通过元素的XPath路径表达式来表示[ 21]

索引信息以文件形式存储。同数据库存储XML结构化索引一样,一般也存储以下几项内容:

(元素标识,位置信息,元素内容)

其中,位置信息一般采用(start, end, level)来表示。

③基于位置的索引(Position-based Indexing)

基于位置的索引也称为空间索引,索引标签的起始坐标或终止坐标。这里的坐标信息是基于某种图形结构表示的XML文本的起始位置(见图1),从左边框所标识的区域可以记录每个元素的起始坐标,相应地,从右边框所标识的区域可以记录每个元素的结束坐标。从记录元素的空间位置信息可以得到元素间的关系,比如title和author起始横坐标值相同,那么它们是兄弟节点。这样进行检索时元素的结构信息就可以解释为它们的空间位置信息。

图1 XML文本结构

④多维索引(Multi-dimensional Indexing)

以上提到的所有索引都是以单个属性为单位的,而多维索引中索引粒度更大。

多维索引的思想类似多维数据库中的联机分析处理(OLAP)和数据立方(Data Cubes)。数据立方是一种表示多维数据的方式,可以循着每一个维度对数据进行聚类。Oracle 8i就是一种多维数据库[ 17]

多维索引在处理数据时,把数据以块为单位划分,或者划分为语义片段,以对数据进行分析处理。在处理数据时,可以对每一个块或者语义片段进行并行处理,这样总体性能会有提升。

在XML中,每一个XML文档就是一个块,XML文档之间通过XLinks和XPointers相关联。

对XML文档进行多维索引的步骤是:预处理器装载XML文档到多维数据库,基于一些标准属性(时间、地址、类别)和信息检索相关属性(词条、词频等)进行多维索引。

进行多维索引之后,通过多维表达式(类似SQL语句)来检索出满足要求的XML文本集合以用于进一步的文档内检索。这种方法在互联网环境下快速提取用于进一步检索的XML文档集合时很有效[ 17, 22]

4 XML检索排序方法

XML检索旨在提供尽可能精确的信息给用户,因此,检索结果可以是任意粒度的元素,只要它在内容上与查询是相关的。所以,XML检索与非结构化文本信息检索的最大不同点是:XML检索不仅要对元素根据其与查询的相关度进行打分,而且要决定合适的返回元素的大小。因此,XML检索在对结果进行排序时至少要有两步:计算元素得分;选择合适大小的元素返回。如果检索式是CAS类型,进行得分计算时还需要考虑结构限制,这时还需要有结果限制处理这一步。下面对这三步主要解决的问题及现有的解决方法分别进行介绍。

4.1 元素得分的计算

在XML检索中,传统基于TF×IDF的方法在应用时,词频等统计数字不再是文档级别的,而是元素级别的,因此在计算元素得分时如何对元素级别的统计信息进行建模是一个主要的问题。很多用于无结构文本的检索模型通过适当的改进都能应用于XML检索之中,例如:向量空间模型、BM25、统计语言模型等。同时也有很多针对XML检索设计的排序方法。至今为止,还没有公认的XML检索模型。下面介绍一些有代表性的计算元素得分的方法。

(1)向量空间模型

Mass和Mandelbrod[ 13, 23, 24]在XML检索中对向量空间模型进行了扩展。文档D和查询Q之间的相关性定义为查询向量和文档向量之间的Cos值,如公式(1)[ 13, 23, 24]所示:

Sim(Q,D)= (1)

其中:

wx∈{Q,D}(t)=log(TFx(t)×log( )) (2)

N是数据集中文档总数;词频TFD(t)是关键词t在文档D中的出现频率;文档频率DF(t)是包含关键词t的文档总数。

为了检索XML元素而不是整篇文档,需要对N、词频以及文档频率进行重新定义。N定义为数据集中元素总数;词频TFC(t)是关键词t在元素C中的出现频率;元素频率CF(t)是包含关键词t的元素总数。由于XML的元素是嵌套式的,因此在实际计算时,只有词频使用元素词频TFC(t),N和DF(t)依旧使用文档级统计结果。

(2)BM25

Lu等[ 25, 26]在XML检索中对BM25概率模型进行了扩展。针对文档级的检索,定义了BM25F模型,该模型在计算词频时对XML文档中不同的域进行了加权,模型具体计算公式参见文献[25]和[27]。针对元素级的检索,定义了BM25E模型,该模型将元素当作XML文档,同样也对元素进行加权,模型具体计算公式参见文献[25]和[28]。

(3)统计语言模型

Sigurbjörnsson等[ 14, 29, 30]在XML检索中对统计语言模型进行了扩展。他们使用多项语言模型,配以Jelinek-Mercer平滑方法,每一个元素都有一个语言模型。元素的语言模型如公式(3)[ 14, 29, 30]所示:

p(e|q)∝p(e)×p(q|e) (3)

假定查询q中各个关键词(t1, t2,…,tk)相互独立,则公式(3)可以转化为:

p(e|q)∝p(e)× p(ti|e) (4)

为了防止出现数据稀疏的问题,对元素的语言模型用另外两个语言模型进行了线性插值,一个是元素所在文档的语言模型,一个是数据集的语言模型。这时,p(ti|e)可以表示为[ 14, 29, 30]:

p(ti|e)=λe×pmle(ti|e)+λd×pmle(ti|d)+(1-λed)×pmle(ti) (5)

其中,pmle (·|e)是对元素e的建模,pmle (·|d)是对文档d的建模,pmle (·)是对数据集的建模。λe和λd是插值参数,即平滑参数。三种对象的建模均采用最大似然估计来计算。

此外,p(e)可以表示为[ 14, 29, 30]:

p(e)= (6)

其中,|e|是指元素e的大小。

另外,Ogilvie 和Callan[ 31, 32, 33]也在XML检索中对统计语言模型进行了扩展。他们使用一种树结构形式的有生殖能力的语言模型来计算元素得分[ 31]。树中每一个节点对应了一个语言模型。其中,叶子节点的语言模型通过该节点的内容来建模;非叶子节点则通过对其子元素的模型使用线性插值的方法来建模。最后形成的建模树中,每一个节点有一个语言模型,每一条边有一个权值,该权值在线性插值过程中给出。后来,他们将建模过程进一步规则化为层次统计语言模型[ 33]

除了从信息检索基本模型进行扩展外,还可以针对XML检索设计其独特的得分计算方法,下面介绍一些典型的方法。

①段落检索

Huang等[ 34]将段落检索(Passage Retrieval)思想应用于XML元素检索中:使用固定大小窗格将XML文档分割成一个个有重复的或无重复的片段,一个片段只要含有一个检索词就认为是相关片段。得到这些片段的起始位移和终止位移之后,定义它们的公共祖先(Common Element Ancestor)为含有这些片段的最小元素,然后通过这些片段的得分来计算元素得分。片段得分则采用传统信息检索中的检索模型来计算。

②基于阅读收益和阅读努力的方法

Shimizu和Yoshikawa[ 35]提出了一种基于阅读收益(Benefit)和阅读努力(Reading Effort)的XML检索排序方法。假定一个元素的阅读收益大于或者等于它所有子元素的阅读收益之和;一个元素的阅读努力小于或者等于它所有子元素的阅读努力之和。检索结果按照获得收益的效率来排序,即:benefit / reading effort。

元素e的阅读收益定义为[ 35]:

e.benefit= × tf×ief (7)

ief=ln (8)

其中,tf是查询q检索词的词频;ief是逆元素频率;n是元素e和查询q共同包含的检索词个数;|q|是查询q包含的检索词个数;N是数据集中元素的个数;ef是数据集中包含检索词t的元素个数。

元素的阅读努力与元素的大小有关,与查询q无关。因此,Shimizu和Yoshikawa将阅读努力定义为元素大小的简单函数。

③得分传递方法

Geva[ 36, 37, 38, 39]定义了一种得分传递方法,先对叶子节点计算得分,非叶子节点得分由其子元素得分的叠加而得。

Geva[ 36]定义的叶子节点的相关度计算公式如下:

L=Kn-1× (9)

其中,n是叶子节点中所包含的不同检索关键词个数;K是参数;ti是第i个检索关键词在叶子节点中的频率,fi是第i个检索关键词在数据集中的频率。

非叶子节点的相关度计算公式定义为[ 36]:

R=D(n)× Li (10)

其中,n是该节点的子元素个数;如果n为1,那么D(n)取值为0.49,否则取值为0.99;Li是第i个子元素。

4.2 选择合适元素返回

由于XML文档是嵌套式的结构,检出元素可以是任意层次结构的,因此如果子元素符合检索要求,则父元素也符合检索要求,有时父元素信息全面,子元素只是片面地含有部分信息;有时子元素中的冗余信息较少,父元素反而含有更多的不相关信息。所以,在计算元素得分并按照得分高低进行排序之后,需要对元素进行去重处理,对相互嵌套的检索结果选择合适的元素大小返回。目前主要有以下几种方法:

(1)选择得分最高的元素

最简单的方法就是直接选择得分最高的元素返回[ 16, 37]。这种方法把元素之间看成是相互独立的,没有考虑不同元素之间的关系。

(2)考虑元素间关系进行选择

根据元素间关系来进行重复元素去除的方法主要有以下几种:

①Shimizu和Yoshikawa[ 35]将重复元素定义为两种:包含(Contain,包含一个得分更高的子元素)和被包含(Contained,被包含于一个得分更高的父元素)。如果是包含的,那么去掉已经检索出来的被包含的子元素;如果是被包含的,那么直接忽略该条结果。

②Clarke[ 40]则对包含或者包含于得分更高元素中的元素进行了得分调整。

③Mass等[ 24]和Lu[ 28]考虑了同一篇文章中所选出元素的分布情况以及元素得分情况。

④综合多种因素,不仅仅是得分大小。Mihajlovic等[ 41]定义了一种效用函数(Utility Function),根据元素中相关内容的比例、元素得分及其长度来度量元素有用性的大小。对于元素E,其效用函数定义为[ 41]:

U(E)=(1- )×p(E)×size(E) (11)

其中,p(E)是由检索模型计算得到的元素相关性得分;nrch(E)是元素E中不相关子元素集合。

4.3 结构限制的处理

用户对结构限制的指定分为两种:限制检索,即对目标元素结构进行限制;减少查询的元素范围,即对待检元素结构进行限制。对两种限制都存在模糊解释和严格解释两种。因此,对结构限制的解释按照对待检索元素的模糊/严格解释和目标元素的模糊/严格解释两部分共存在4种不同的解释方式[ 42],后来Trotman和Lalmas[ 43]通过对INEX 2005的各种不同解释方式进行相关度分析,得出了对待检元素的结构限制与检索效果好坏没有关系的结论,因此后续几年仅对于目标元素进行不同方式的解释。以下介绍对目标元素进行模糊解释的几种方法。

(1)全部忽略:最简单的方法就是直接忽略掉结构限制。

(2)构建等价标签集:为了对结构限制进行模糊处理,最直接的方法就是构建等价标签集。如Mass和Mandelbrod[ 24]事先挑选出合适大小的元素并对每种元素进行单独的索引。检索是同时在每种元素的单独索引上分别进行的。通过与等价标签列表进行比较,实现了结构限制的模糊解释。Mihajlovic等[ 41]则使用INEX的人工相关性评测结果来自动构建等价标签集。

(3)利用结构限制:Theobald等[ 44]和Geva[ 37]利用结构限制进行得分计算。他们先计算元素的内容相关性得分,然后根据元素与结构限制的匹配程度来增加得分。这种方法可以看作是间接的模糊处理。

(4)放松路径限制:当使用数据库实现XML检索时[ 41, 44],可以通过放松查询式路径限制来达到模糊处理结构限制的目的。

5 XML检索评价

利用以上的各种方法进行XML检索研究或者开发的系统大都在INEX中进行过测评。可以说,INEX会议评价方法的发展体现了XML检索评价的研究发展,因此本节将介绍INEX会议中所使用的评价方法。对检索排序方法进行评价,需要有标准结果集来做对比。INEX通过每年子任务完成之后的人工相关性评测(Relevance Assessment)过程来获得标准结果集。

信息检索中相关性通常被理解为一条检索结果与用户查询的联系强弱。INEX XML检索评价中对检索结果与用户查询关系的相关性衡量,从两个维度进行了定义:

(1)Exhausitivity:也叫Topical Relevance,即主题相关性,定义元素对检索主题要求的满足度;

(2)Specificity:也叫Component Coverage,即主题专指度,元素中与检索主题相关的内容的多少。

Exhausitivity是信息检索中的标准指标,Specificity则是元素内相关部分和不相关部分大小的比例。Exhausitivity一般规定有4个等级:0:Irrelevant;1:Marginally Relevant;2:Fairly Relevant;3:Highly Relevant。Specificity 的4个等级定义为:N:No Coverage;L:Too Large;S:Too Small;E:Exact Coverage。

在进行人工评测的时候,Specificity可以由检索出的人工评价为相关的区域的大小比上检出片段的总大小来获得。

INEX 2005及以前几届会议定义了量化函数来综合Exhausitivity和Specificity的得分,如下所示[ 45]:

Q(rel,cov)= (12)

Oglive和Lalmas[ 45]通过调查INEX 2005的评测结果发现,使用Exhausitivity与不使用时的检索效果类似,因此自2006年起,INEX放弃了Exhausitivity这一维度。

INEX 2005针对Focused任务设计了XCG(eXtended Cumulated Gain)评测方法[ 46];2006年,多种新的评价方法被引进[ 47],包括:HiXEval, BEPD和EPRUM等。

XML的不同检索任务有不同的检索要求,因此也需要制定不同的评价指标,例如对需要找到最佳阅读入口点(Best Entry Point)的XML检索任务,进行评价时需要考虑最佳入口点和正确结果之间的距离大小。INEX 2005和2006中提出了一些新的评价方法,并且对往届的评价方法进行了很多改进,这两年的评价方法最为丰富[ 46, 47]。INEX 2007和2008对INEX 2005和2006的一些比较复杂的方法进行了适当简化,并逐步趋于成熟[ 48, 49]。下面以2007年的INEX为例,介绍Ad-Hoc各项子任务所采用的评价方法[ 48]

5.1 Focused Task

假定:Pr是排序为r的XML元素片段,rsize(Pr)是Pr中包含的高亮部分的字符数。size(Pr)是Pr中包含的总字符数。Trel是文档集中高亮部分的总字符数,表示所有相关文档的相关片段的大小size。

在排序为r的地方的查准率Precision[ 48]:

P[r]=

(13)

即:为了达到更高的查准率,系统应该返回尽可能少的不相关片段。

在排序为r的地方的查全率Recall定义为[ 48]:

R[r]= × rsize(Pi) (14)

即:为了达到更高的查全率,系统应该返回尽可能多的相关片段。

定义rel(Pr)为一个系数,如果片段p包含有高亮片段,则取值为1;如果不包含则取值为0。R则为1 500,因为官方设定的返回结果数为1 500个。检索结果的平均查准率(Average Precision)定义为[ 48]:

AP= ×

= ×R[|R|](15)

其计算方法是:首先在每一个Recall的地方计算查准率Precision,如果某一个Recall的地方没有相关部分,则查准率为0。

5.2 Relevant in Context Task

该方法假设:用户认为每一个相关文档都是同等重要的。则单篇文章的得分计算公式是[ 48]:

P(d)= (16)

P是文档d的部分。

定义Trel(d)为文档d中的高亮区域的大小,则Recall为[ 48]:

R(d)= (17)

定义文档的F值为[ 48]:

F(d)= (18)

文档最终得分是[ 48]:

S(d)=F(d) (19)

5.3 Best Entry Point(BEP) Task

单篇文章的得分是字符距离d的线性函数。

假定s(x,b)计算的是系统返回的BEP和真实的BEP之间的距离,值为1时表示两者相吻合,最小值为0。d(x,b)表示它们之间的字符距离,L是文档长度,A是调和参数,A越大,长度的影响就会越小。则单篇文档的得分计算方法是[ 48]:

s(x,b)= (20)

另一种计算方法是[ 48]:

s(x,b)= (21)

其中,n=1 000 表示在屏幕上文档的可见部分的字符数。文档得分公式为:

S(d)=s(x,b) (22)

6 XML检索研究热点领域

INEX会议是XML检索界最著名的测评会议。从INEX每年的任务设置可以明显地看出XML检索不断变化的发展方向和研究的热点问题。从其近6年INEX开设的所有任务(见表1)可以看出,Relevance Feedback、Natural Query Language、 Multimedia等任务已经没有了,这些领域或是已经研究成熟,或是已经不再吸引研究者,或是转移到了更合适的地方,例如Multimedia于2008年转移到专门的图像检索国际会议之中。另外,INEX每年都有新的任务加入。

表1 2004-2009年INEX任务开设情况[ 50]

2008、2009年INEX提供的任务完全相同,包括[ 50]:Ad-Hoc, Book Search, Efficiency, XML Entity Ranking, Interactive (iTrack), Question Answering (QA@INEX), Link the Wiki, XML-Mining。

其中,Ad-Hoc检索是自2002年起一直举办至今的一项最主要的任务,该任务是对图书馆检索的一种模拟,主要研究静态文档集的检索。Ad-Hoc每年的任务要求都在不断变化,2008年的Ad-Hoc检索包括关键词检索和结构化检索。其中,结构化检索的具体任务经历了一系列的变革:从最初的严格结构限制 (Strict CAS,SCAS)[ 51],到2003年引入了模糊解释 (Vague CAS,VCAS)[ 52],2005年又将对结构限制的解释分解为对待检索元素的模糊/严格解释和目标元素的模糊/严格解释两部分,包括VVCAS, VSCAS, SSCAS和SVCAS四大类[ 42],后来Trotman和Lalmas[ 43]通过对INEX 2005的各种不同解释方式进行相关度分析得出了对待检元素的结构限制与检索效果好坏没有关系的结论,因此后续几年仅对于目标元素进行不同方式的解释。Ad-Hoc检索对关键词检索和结构化检索又分别开设了多项子任务,以2007年的三项子任务最有代表性:Focused, Relevant in Context, Best in Context。这三项子任务是不同的XML检索策略,Focused的检索结果以XML片段显示,Relevant in Context的检索结果以每篇文章及所有其相关部分的形式显示,Best in Context是以最佳入口点的形式显示。2004以来,Ad-Hoc检索的子任务都是从检索用户需求的角度来设置的。2008年的子任务则是专门研究元素级的检索:分为Element Retrieval和Passage Retrieval两个子任务,对元素的定义也不再仅仅是物理显示的元素,也包含了内容上相关的元素 (Passage Retrieval)。

Efficiency和Question Answering任务是2008年新增的两项任务。Efficiency任务是基于真实的环境(使用真实的数据集和真实的检索主题)来综合考察XML检索系统的检索速度和检索效果,主要为吸引数据库领域的研究人员进入INEX,以进一步比较数据库方法和信息检索方法在进行XML检索时的优劣。Question Answering则一直是信息检索领域的热点研究内容,INEX引入这一检索任务主要是为了比较问答系统、XML片段检索系统和自动文摘系统在处理百科全书式的数据集(例如:维基百科)时的效果。

Interactive任务是自2004年开始设置的,主旨包含两方面:研究XML检索中的用户交互行为;研究在基于用户的环境下进行元素检索的有效方法。

XML-Mining任务是自2005年开始设置的,主要考察机器学习技术在半结构化的XML数据集中的应用情况和遇到的问题。

Entity Ranking任务是自2006开始设置的,该任务是参照TREC会议的专家检索任务[ 29]而设置,其检索结果不再是文档和文档片段,而是实体。

Link the Wiki和Book Search两项任务是自2007年开始设置的。其中,Link the Wiki任务是针对维基百科的实际需求设置的任务,主要考察自动为维基百科词条添加链接的技术。给定一篇新的维基百科文档,需要分析该文档并推荐一系列的链入和链出链接,而且要链接到一个明确的目的地,即要指定链入之后用户开始阅读的最佳入口点。Book Search任务旨在促进跨学科研究活动,Book Search可以支持用户对电子图书进行阅读、检索和导航浏览,为科学研究的交流提供方便。

7 结 语

本文所探讨的XML检索是指对以文本为中心的XML文档进行的检索。从XML查询语言、XML索引、XML检索排序方法、XML检索评价以及XML检索研究热点领域共5个方面对XML检索进行了介绍。

以上各方面均有很多需要继续深入研究的问题:

(1)查询语言方面:主要是需要结合用户,要考虑用户对数据集结构的了解程度,设计出方便使用的查询界面。

(2)索引方面:目前主要根据不同检索方法而设计了对应的索引方法,若产生了新的检索方法则需要对现有索引策略进行相应的调整。

(3)检索排序方法方面:至今还没有统一的检索模型,XML检索涉及的点比较多,所以如何将这些点纳入到建模过程中是待解决的问题之一。另外,结构限制方面,INEX之外[ 11]研究了一些其他表达形式更丰富的查询语言,并对其结构限制的处理方法进行了很详细的探讨,如何将这些表达丰富的检索查询式与INEX结合也值得深入研究。

(4)XML评价方面:针对每年INEX的不同任务,组织者都在对评价方法进行不断的改进。

随着XML检索研究的不断深入和XML检索在实际中的不断应用,以及信息检索方法在XML检索中的应用将会不断出现很多新的研究领域。

参考文献
[1] Lalmas M, Trotman A. XML Retrieval[R]. Berlin: Springer, 2009. [本文引用:1]
[2] Mannning C D, Raghavan P, Schutze H. Introduction to Information Retrieval[EB/OL]. [2010-02-01]. http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html. [本文引用:1]
[3] Guo L, Shao F, Botev C, et al. XRANK: Ranked Keyword Search over XML Documents[C]. In: Proceedings of the 22nd ACM International Conference on Management ofData. 2003: 16-27. [本文引用:1]
[4] Xu Y, Papakonstantinou Y. Efficient Keyword Search for Smallest LCAs in XML Databases[C]. In: Proceedings of the 24th ACM International Conference on Management of Data, Baltimore, Maryland . New York, NY, USA : ACM, 2005: 527-538. [本文引用:1]
[5] Trotman A, Sigurbjörnsson B. Narrowed Extended XPath I (NEXI)[C]. In: Proceedings of the 3rd Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2005: 16-40. [本文引用:2]
[6] Amer-Yahia S, Lalmas M. XML Search: Languages, INEX and Scoring[C]. In: Proceedings of the 25th ACM International Conference on Management of Data. 2006: 16-23. [本文引用:1]
[7] Cohen S, Mamou J, Kanza Y, et al. XSEarch: A Semantic Search Engine for XML[C]. In: Proceedings of the 29th ACM International Conference on Very Large Data Bases. 2003: 45-56. [本文引用:1]
[8] Fuhr N, Gro-johann K. XIRQL: A Query Language for Information Retrieval in XML Documents[C]. In: Proceedings of the 24th Annual International ACM SIGIRConference. 2001: 172-180. [本文引用:1]
[9] Theobald A, Weikum G. The Index-based XXL Search Engine for Querying XML Data with Relevance Ranking[C]. In: Proceedings of the 8th International Conference on Extending DatabaseTechnology. 2002: 311-340. [本文引用:1]
[10] Amer-Yahia S, Lakshmanan L, Pand it S. FleXPath: Flexible Structure and Full-text Querying for XML[C]. In: Proceedings of the 23rd ACM International Conference on Management of Data. 2004: 83-94. [本文引用:1]
[11] W3C. XQuery 1. 0: An XML Query Language[EB/OL]. [2010-02-01]. http://www.w3.org/TR/xquery/. [本文引用:2]
[12] W3C. XQuery and XPath Full Text 1. 0[EB/OL]. [2010-02-01]. http://www.w3.org/TR/xpath-full-text-10/. [本文引用:1]
[13] Mass Y, Mand elbrod M. Retrieving the Most Relevant XML Components[C]. In: Proceedings of the 2nd Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2004: 53-58. [本文引用:3]
[14] Sigurbjörnsson B, Kamps J, Rijke M. The Effect of Structured Queries and Selective Indexing on XML Re-trieval[C]. In: Proceedings of the 4th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2006: 104-118. [本文引用:6]
[15] Liu J, Lin H, Han B. Study on Reranking XML Retrieval Elements Based on Combining Strategy and Topics Categorization[C]. In: Proceedings of the 6th Initiative on the Evaluation of XML Retrieval Workshop. 2007: 170-176. [本文引用:1]
[16] Sauvagnat K, Hlaoua L, Boughanem M. XFIRM at INEX 2005: Ad-Hoc and Relevance Feedback Tracks[C]. In: Proceedings of the 4th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2006: 88-103. [本文引用:2]
[17] Luk R, Leong H, Dillon T S, et al. A Survey in Indexing and Searching XML Documents[J]. Journal of the American Society for Information Science and Technology, 2002, 53(6): 415-437. [本文引用:3] [JCR: 2.005]
[18] 孔令波, 唐世渭, 杨冬青, . XML数据索引技术[J]. 软件学报, 2005, 16(12): 2063-2079. [本文引用:1]
[19] Gou G, Chirkova R. Efficiently Querying Large XML Data Repositories: A Survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(10): 1381-1403. [本文引用:1] [JCR: 1.892]
[20] Hiemstra D. A Database Approach to Content-based XML Retrieval[C]. In: Proceedings of the 1st Initiative on the Evaluation of XML RetrievalWorkshop. 2003: 111-118. [本文引用:1]
[21] Geva S. GPX-Gardens Point XML Information Retrieval at INEX 2004[C]. In: Proceedings of the 3rd Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2005: 211-223. [本文引用:1]
[22] Lee J, Grossman D, Frieder O, et al. Integrating Structured Data and Text: A Multi-dimensional Approach[C]. In: Proceedings of the International Conference on Information Technology: Coding and Computing. 2000: 264-269. [本文引用:1]
[23] Mass Y, Mand elbrod M. Component Ranking and Automatic Query Refinement for XML Retrieval[C]. In: Proceedings of the 3rd Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2005: 73-84. [本文引用:2]
[24] Mass Y, Mand elbrod M. Using the INEX Environment as a Test Bed for Various User Models for XML Retrieval[C]. In: Proceedings of the 4th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2006: 187-195. [本文引用:4]
[25] Lu W, Robertson S, Macfarlane A. Field-Weighted XML Retrieval Based on BM25[C]. In: Proceedings of the 4th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2006: 126-137. [本文引用:1]
[26] Lu W, Robertson S, MacFarlane A. CISR at INEX 2006[C]. In: Proceedings of the 5th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2007: 57-63. [本文引用:1]
[27] 陆伟, Robertson S. 基于域加权词频法的XML文档级检索实现与评价[J]. 中国图书馆学报, 2006, 32(6): 57-60. [本文引用:1]
[28] 陆伟. 元素级XML检索模型构建的关键问题与解决方案研究[J]. 中国图书馆学报, 2007, 33(6): 58-61. [本文引用:1]
[29] Sigurbjörnsson B, Kamps J, Rijke M. An Element-based Approach to XML Retrieval[C]. In: Proceedings of the 2nd Initiative on the Evaluation of XML RetrievalWorkshop. 2004: 19-26. [本文引用:5]
[30] Sigurbjörnsson B, Kamps J, Rijke M. Mixture Models, Overlap, and Structural Hints in XML Element Retrieval[C]. In: Proceedings of the 3rd Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2005: 196-210. [本文引用:4]
[31] Ogilvie P, Callan J. Language Models and Structured Document Retrieval[C]. In: Proceedings of the 1st Initiative on the Evaluation of XML Retrieval Workshop. 2003: 33-40. [本文引用:2]
[32] Ogilvie P, Callan J. Using Language Models for Flat Text Queries in XML Retrieval[C]. In: Proceedings of the 2nd Initiative on the Evaluation of XML Retrieval Workshop. 2004. [本文引用:1]
[33] Ogilvie P, Callan J. Hierarchical Language Models for XML Component Retrieval[C]. In: Proceedings of the 3rd Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2005: 224-237. [本文引用:2]
[34] Huang W, Trotman A, O’Keefe R A. Element Retrieval Using a Passage Retrieval Approach[C]. In: Proceedings of the 11th Australasian Document ComputingSymposium. 2006: 80-83. [本文引用:1]
[35] Shimizu T, Yoshikawa M. A Ranking Scheme for XML Information Retrieval Based on Benefit and Reading Effort[C]. In: Proceedings of the 10th International Conference on Asian DigitalLibraries. 2007: 230-240. [本文引用:3]
[36] Geva S. GPX - Gardens Point XML Information Retrieval at INEX 2004[C]. In: Proceedings of the 3rd Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2005: 211-223. [本文引用:3]
[37] Geva S. GPX - Gardens Point XML IR at INEX 2005[C]. In: Proceedings of the 4th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2006: 240-253. [本文引用:3]
[38] Geva S. GPX - Gardens Point XML IR at INEX 2006[C]. In: Proceedings of the 5th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2007: 137-150. [本文引用:1]
[39] Geva S. GPX: Ad-Hoc Queries and Automated Link Discovery in the Wikipedia[C]. In: Proceedings of the 6th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2008: 404-416. [本文引用:1]
[40] Clarke C. Controlling Overla Pin Content-Oriented XML Retrieval[C]. In: Proceedings of the 28th Annual International ACM SIGIRConference. 2005: 314-321. [本文引用:1]
[41] Mihajlovic V, Ramirez G, Westerveld T, et al. TIJAH Scratches INEX 2005: Vague Element Selection, Image Search, Overlap, and Relevance Feedback[C]. In: Proceedings of the 4th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2006: 72-87. [本文引用:4]
[42] Malik S, Kazai G, Lalmas M, et al. Overview of INEX 2005[C]. In: Proceedings of the 4th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2006: 1-15. [本文引用:2]
[43] Trotman A, Lalmas M. The Interpretation of CAS[C]. In: Proceedings of the 4th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2006: 58-71. [本文引用:2]
[44] Theobald M, Schenkel R, Weikum G. TopX & XXL at INEX 2005[C]. In: Proceedings of the 4th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2006: 282-295. [本文引用:2]
[45] Oglive P, Lalmas M. Investigating the Exhaustivity Dimension in Content-Oriented XML Element Retrieval Evaluation[C]. In: Proceedings of the 15th ACM International Conference on Information and Knowledge. 2006: 84-93. [本文引用:2]
[46] Kazai G, Lalmas M. INEX 2005 Evaluation Measures[C]. In: Proceedings of the 4th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2006: 16-29. [本文引用:2]
[47] Lalmas M, Kazai G, Kamps J, et al. INEX 2006 Evaluation Measures[C]. In: Proceedings of the 5th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2007: 20-34. [本文引用:2]
[48] Kamps J, Pehcevski J, Kazai G, et al. INEX 2007 Evaluation Measures[C]. In: Proceedings of the 6th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2008: 24-33. [本文引用:11]
[49] Kamps J, Geva S, Trotman A, et al. Overview of the INEX 2008 Ad-Hoc Track[C]. In: Proceedings of the 7th Initiative on the Evaluation of XML Retrieval Workshop. Berlin: Springer, 2009: 1-28. [本文引用:1]
[50] INEX 2009[EB/OL]. [2010-02-01]. http://www.inex.otago.ac.nz/. [本文引用:1]
[51] Govert N, Kazai G. Overview of the Initiative for the Evaluation of XML Retrieval (INEX) 2002[C]. In: Proceedings of the 1st Initiative on the Evaluation of XML RetrievalWorkshop. 2003: 1-18. [本文引用:1]
[52] Fuhr N, Malik S, Lalmas M. Overview of the Initiative for the Evaluation of XML Retrieval (INEX) 2003[C]. In: Proceedings of the 2nd Initiative on the Evaluation of XML Retrieval Workshop. 2004: 15-17. [本文引用:1]