I
import
Unregistered / Unconfirmed
GUEST, unregistred user!
第十四期(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,
半年栏目: 专题报道
出版日期: 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,