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

信息检索中效率问题的研究报告人:赵江华北京大学计算机科学与技术系网络与分布式系统实验室 2002 年4月21日信息检索( 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), 按单词项索引形成倒排文件。单词 t j对应的 posting lists 是{( d i , f i, a * )+( d i+k , f i+k, a * )+…},f i表示 t j在d i的出现次数,也是后面 a的数量。这是倒排文件的全文本索引( full-text inverted file) 形式,它记录了每次出现的位置等信息,要占用较多的存储空间。如果去掉位置信息,仅可以支持逻辑查询形式。词典的组织(一) ?索引单词项的集合构成词典,系统通过查找词典定位该单词对应的 posting lists ,这是从单词到指针的映射。有两种词典的组织方式: –直接用 B+ 树等方式组织单词的字符串。–用哈希( hash )的方式——速度更快,可以将所有单词装入内存中。词典的组织(二) ?“天网”中用哈希的方法实现从单词字符串到单词标识( TermID ,整数)的转换, 单词的标志是在每次创建索引是赋予的(不是固定的),所有单词的标志是从零开始的连续整数。?如果维护一个全局稳定的词典(固定单词的标识,便于维护),系统的 TermID 可能成为稀疏的整数,可以组织成 B+ 树实现从 TermID 到指针的映射。数据组织(一) ?倒排文件中单词对应的 posting lists 部分必须存储在磁盘中,不同单词的 posting lists 长度差别很大,可以区别对待。?存储管理的方法在 DBMS 已经有深入研究。在倒排文件中,每个单词的 posting lists 的访问模式是顺序扫描( sequential scanning ),作为一个对象看待最合适。关系数据库管理系统( RDBMS )用于倒排文件的缺点是不太灵活,而且 SQL 语句的开销比较大。