信息检索中效率的研究.ppt

信息检索(IR)的基本概念(一)
信息检索和数据库管理系统(DBMS)的区别:
DBMS处理对象是结构化数据,IR处理大量的非结构化数据。
DBMS只是管理数据,IR要管理数据的内容——内容管理(content management)。
DBMS的每次事务的结果是确定的,IR系统的任务是找到用户需要的信息,其结果是不精确的。
信息检索(IR)的基本概念(二)
信息检索的两大问题:效率(efficiency)、效果(effectiveness)。
效果指标:查准率(precision)和查全率(recall)。
效率指标:响应时间(response time)和吞吐量(throughput)。
文本信息检索效果的提高依赖于自然语言处理(NLP);信息的指数增长使得检索效率也成为不可忽略的问题。
信息检索(IR)的基本概念(三)
信息检索系统的组成部分:
信息检索(IR)的基本概念(四)
基本用户查询(query):
逻辑操作(AND,OR,NOT)。
位置邻近查找(Proximity Search),短语查找(Phrase Search)。
对原始信息创建索引加快检索速度:
Inverted file , signature file等。
倒排文件是最广泛使用的技术,它组织结构灵活,可以满足多种查询方式。
对文档的预处理
在英语等语言中做“stem”,索引单词的“主干”。——可以提高查全率,降低查准率。
汉字之间没有空格,可以对汉字字符索引,也可以索引做切词处理后的词组。
现代汉语中大部分是两个字的词组,单个的字符表示的意义很不确定,所以对词组建索引可以提高查询的效果。切词对查询效率也有重大影响。
倒排文件的组织
将文档分割成独立的单词项(term),按单词项索引形成倒排文件。
单词tj对应的posting lists是{( di , fi, a*)+( di+k , fi+k, a*)+…},fi表示tj在di的出现次数,也是后面a的数量。这是倒排文件的全文本索引(full-text inverted file)形式,它记录了每次出现的位置等信息,要占用较多的存储空间。如果去掉位置信息,仅可以支持逻辑查询形式。
词典的组织(一)
索引单词项的集合构成词典,系统通过查找词典定位该单词对应的posting lists,这是从单词到指针的映射。有两种词典的组织方式:
直接用B+树等方式组织单词的字符串。
用哈希(hash)的方式——速度更快,可以将所有单词装入内存中。
词典的组织(二)
“天网”中用哈希的方法实现从单词字符串到单词标识(TermID,整数)的转换,单词的标志是在每次创建索引是赋予的(不是固定的),所有单词的标志是从零开始的连续整数。
如果维护一个全局稳定的词典(固定单词的标识,便于维护),系统的TermID可能成为稀疏的整数,可以组织成B+树实现从TermID到指针的映射。
数据组织(一)
倒排文件中单词对应的posting lists部分必须存储在磁盘中,不同单词的posting lists 长度差别很大,可以区别对待。
存储管理的方法在DBMS已经有深入研究。在倒排文件中,每个单词的posting lists的访问模式是顺序扫描(sequential scanning) ,作为一个对象看待最合适。关系数据库管理系统(RDBMS)用于倒排文件的缺点是不太灵活,而且SQL语句的开销比较大。
数据组织(二)
面向对象的概念更能简洁地描述倒排文件的结构,采用面向对象数据库系统(OODBS)是更好的选择。下面是两个被一些IR系统使用的例子:
用持久对象存储(Persistent Object Store)Mneme管理倒排文件,Mneme不但提供基于对象的数据缓存和良好的磁盘空间分配策略,还可以用它高度的可扩展性,根据数据的特性定制存储。
ObjectStore是商业上最成功的面向对象数据库系统之一,它用内存映射技术实现持久对象存储,和程序语言(C,C++,JAVA)完全集成,既有程序设计语言的灵活,又可以高效的存储数据,是另一个很好的索引管理工具。