第十四期(4月19日): 产品与技术
半年版名: 产品与技术
半年栏目: 专题报道
出版日期: 19990419
检索模型
--WWW上的信息发现与检索技术之二
南京大学软件新技术国家重点实验室 邹涛
文档的索引与检索模型是WWW索引与检索系统的核心,检索模型的优劣直接影响到系
统的效果。文本信息检索模型主要分为两大类:全文检索和基于内容的文本检索。
全文检索模型
全文检索(Full Text Retrieval)是指以文档的全部文本信息作为检索对象的一种信
息检索技术。全文检索的关键是文档的索引,即如何将源文档中所有基本元素的信息以适
当的形式记录到索引库中。在中文文档中,"基本元素"可以是单个汉字,也可以是词或词
组。根据索引库中索引的元素不同,可以将全文检索分为基于字表的全文检索和基于词表
的全文检索两种类型。
1. 字表法
字表法是对每个单字的出现位置进行索引,并依据单字的位置信息进行检索的文本检
索方法。字表法索引库的主要部分是每个字的字表信息,索引库中的字表结构如图1所示
。其中字符i对应的字表记录了该字符在源文档中所出现的位置Pix,出现位置通常用字符
相对于文档头的偏移字节数表示。建立字表索引时,需要扫描整个源文档,对出现的每一
个有效字符,计算其在文档中出现的位置,并将该位置的值加入到对应的字表中。
字表记录了对应字符在源文档中的所有位置信息。考察一个字符串,例如两个字的字
符串XY(其中X、Y表示任意的汉字字符),假设X的位置为Px,如果字符串XY在源文档中出现
,则Y的位置Py必定等于Px+2(2为两个汉字间的字节距离)。在索引库中,X的字表中将包含
Px,而Y的字表中也必然包含Px+2。进行检索时,扫描X和Y各自对应的字表,若文档中有该
词出现,则必定有X对应的字表中存在位置值Px,Y对应的字表中存在位置值Py,使得Py=Px
+2成立,每查到一对这样的位置值,就是检索到了字串XY一次。扫描完两字字表,就可以检
索出字符串的所有。
表1
2. 词表法
与字表法相似,词表法是以能表达一定意义的词为基本检索单位,并根据词的出现位
置进行索引和检索的文本检索方法。建立索引时,首先需要对源文档进行词条的切分,然
后对切分后的文档词条进行统计,记录每一个出现的词条及其出现的位置。
3. 字表法与词表法的比较
字表法和词表法各有优缺点,有各自适用的场合和处理的对象。字表法是以单字为基
础进行检索的方法,其缺点是生成的索引库庞大(索引文件的长度往往大于源文档的长度
,需要对索引库进行压缩处理),检索速度低,错检率高,例如检索"华人"一词时,往往会检
索出类似"中华人民共和国"这样的错误结果;其优点是适应性强,应用范围广,索引的生成
简单,比较适用于内容复杂、新词汇和特殊词汇多的文档的检索。
词表法是以词为基本元素进行索引与检索的,它需要对被索引文档进行词条切分,索
引的建立较复杂,漏检率较高,且不能进行单字和任意字符串的检索;其优点是对于大规模
应用,索引库规模小,检索的处理速度快,同义、反义等概念检索的实现较为简单,比较适
用于特定领域中或内容相对固定的文档的全文检索。
基于内容的文本检索技术
基于字表和基于词表的全文检索方法,不考虑文档的具体内容,而仅判断是否包含被
检索元素的检索方法。基于内容的检索是能够根据文档的内容处理类似"检索出属于多媒
体类且包含通信内容的文档"等涉及文档内容查询的检索技术,此种检索模型侧重于文档
的主要内容,而舍弃了局部的细节,生成的索引库较小(索引库长度通常为源文档的几十分
之一或几百分之一),检索速度快,较为接近人的查询习惯。其中使用较多的是布尔检索模
型、向量空间模型与概率模型。
1. 布尔模型
布尔模型是一种简单的严格匹配模型(Exact Match Model),它定义了一个二值变量
集合来表示文档,这些变量对应于文档中的特征项,一般是由训练文档集中的词条或短语
组成。如果词条对文档内容有贡献,则赋予True,否则置为False。检索时,根据用户提交
的检索条件在文档表示中的逻辑关系是否满足,将检索文档分为两个集合:匹配集和非匹
配集。因匹配结果的二值性,而无法在匹配结果集中进行查询结果的相关性排序。
布尔模型实现简单,检索速度快,在许多检索系统中得到应用,Yahoo!、搜狐等诸多著
名网络检索站点均采用了布尔检索模型。但布尔模型的文档表示能力差,无法区分特征项
对文档内容贡献的重要程度,并且逻辑表达式过于严格,往往会因为一个条件未满足而忽
略了其他全部特征,造成大量的漏检。
p范数模型是对布尔模型的扩展,它克服了简单布尔模型匹配函数过于严格而导致漏
检率高的致命缺陷。在p范数模型中,假设文档D可表示为D=(d1,d2, Λ,dn), 用户查询可表
示为Q=(q1,q2, Λ,qn), 其中di和qi分别表示第i个特征词条对文档内容和查询内容的贡献
程度,di、qi在[0,1]的区间上取值。定义文档与查询间的相似度:
算式1
其中1p∞。根据具体应用改变di、qi和p的取值即可达到不同的检索效果。当p
=∞,且di的取值为0或1,q1=q2= Λ=qn=1 时,p范数模型则退化为简单布尔模型。在实际使
用中p的取值由实验得出,取值范围一般为[2,5]。
2. 向量空间模型
向量空间模型(VSM: Vector Space Model)是近年来使用较多且效果较好的一种信息
检索模型。在VSM中,将文档看作是由相互独立的词条组(T1,T2…Tn)构成,对于每一词条
Ti,都根据其在文档中的重要程度赋以一定的权值Wi,并将T1,T2…Tn看成一个n维坐标系
中的坐标轴,W1,W2…Wn为对应的坐标值。这样由(T1,T2…Tn)分解而得的正交词条矢量组
就构成了一个文档向量空间,文档则映射成为空间中的一个点。对于所有文档和用户查询
都可映射到此文本向量空间,用词条矢量(T1,W1,T2,W2…Tn,Wn)来表示,从而将文档信息
的匹配问题转化为向量空间中的矢量匹配问题。假设用户查询为Q,被检索文档为D,两者
的相似程度可用向量之间的夹角来度量,夹角越小,说明相似度越高,相似度计算公式如下
算式2
表示矢量中词条Ti及其权值Wi的选取被称为特征提取,特征提取是利用向量空间模型
进行信息检索的关键步骤。在自然语言文档中,各词条在不同内容的文档中所呈现的频率
分布是不同的,因此可根据词条的频率特性用统计的方法进行特征提取。在文档中,词条
的重要性与词条的文档内的频数成正比,与训练文档集中出现该词条的文档频数成反比,
因而可构造词条权值评价函数:
算式3
其中tfik表示词条Tk在文档Di中的出现频数,N表示用于特征提取的全部训练文本的
文档总数,nk表示词条Tk的文档频数。在实际应用中,为避免因文档长度引起的频数变化
,还应对词条权值评价函数作规范化处理:
算式4
3. 概率模型
布尔模型和向量空间模型都将文档表示词条视为是相互独立的项,忽略了表示词条间
的关联性,而概率模型则考虑到了词条、文档间的内在联系,利用词条间和词条与文档间
的概率相依性进行信息检索。
二值独立检索模型(BIR :Binary Independence Retrieval)是一种实现简单且效果
较好的概率检索模型。在BIR中,假设文档D和用户查询Q都可用二值词条向量(x1,x2, Λ,
xn) 表示,如果词条Ti∈D,则xi=1,否则xi=0。利用Bayes公式并经过简化后可得到文档与
用户查询间的相关函数:
算式5
其中Pi=ri/r,qi=(fi-ri)/(f-r),f表示训练文档集中的文档总数,r表示训练文档集
中与用户查询相关的文档数,fi表示在训练文档集中包含词条Ti的文档数,ri表示r个相关
文档中包含词条Ti的文档数。
4. 概率推理网络
概率推理网络是近年被提出并深受重视的一种新型检索模型。推理网络模拟人脑的
推理思维模式,将文档内容与用户查询匹配的过程转化为一个从文档到查询的推理过程。
基本的文本检索推理网络包含文本网络与用户查询网络两部分,如图2所示。图中每个节
点表示一个文档、一个查询或者一个概念,其中Di为文本节点,Ti为文本表示节点,Ri为文
本概念节点,Ci为用户提问概念节点,Q为用户查询节点,有向边表示节点间的概率相依性
。网络中文档节点与查询节点间的相关性可以表示为:只要给定文档节点的先验概率和中
间节点的条件概率,就可计算出查询节点的后验概率。如要估算用户查询Q与文档Di间的
概率相关性P(R|Q,Di),则应先将文档节点Di置为True,然后依次计算P(Q=True)的相依节
点的概率即可。
推理网络同其他概率模型相比有很多优点,推理网络能够将其他许多概率模型映射到
网络中,并能够采用多种检索形式和由其他知识源得到的统计数据或经验数据,进行综合
检索。
图1
信息检索评价
一般用查全率(Recall)和精度(Precision)来衡量文档表示和检索的效果。查全率为
检索出的相关文档数与实际相关文档数之比,查询精度为检索结果集中的相关文档数与结
果集文档数之比。一个优秀的索引、检索系统应同时拥有较高的查全率和查询精度。