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

信息检索中效率问题的研究 1 信息检索 IR 的基本概念 一 信息检索和数据库管理系统 DBMS 的区别 DBMS处理对象是结构化数据 IR处理大量的非结构化数据 DBMS只是管理数据 IR要管理数据的内容 内容管理 contentmanagement DBMS的每次事务的结果是确定的 IR系统的任务是找到用户需要的信息 其结果是不精确的 2 信息检索 IR 的基本概念 二 信息检索的两大问题 效率 efficiency 效果 effectiveness 效果指标 查准率 precision 和查全率 recall 效率指标 响应时间 responsetime 和吞吐量 throughput 文本信息检索效果的提高依赖于自然语言处理 NLP 信息的指数增长使得检索效率也成为不可忽略的问题 3 信息检索 IR 的基本概念 三 信息检索系统的组成部分 4 信息检索 IR 的基本概念 四 基本用户查询 query 逻辑操作 AND OR NOT 位置邻近查找 ProximitySearch 短语查找 PhraseSearch 对原始信息创建索引加快检索速度 Invertedfile signaturefile等 倒排文件是最广泛使用的技术 它组织结构灵活 可以满足多种查询方式 5 对文档的预处理 在英语等语言中做 stem 索引单词的 主干 可以提高查全率 降低查准率 汉字之间没有空格 可以对汉字字符索引 也可以索引做切词处理后的词组 现代汉语中大部分是两个字的词组 单个的字符表示的意义很不确定 所以对词组建索引可以提高查询的效果 切词对查询效率也有重大影响 6 倒排文件的组织 将文档分割成独立的单词项 term 按单词项索引形成倒排文件 单词tj对应的postinglists是 di fi a di k fi k a fi表示tj在di的出现次数 也是后面a的数量 这是倒排文件的全文本索引 full textinvertedfile 形式 它记录了每次出现的位置等信息 要占用较多的存储空间 如果去掉位置信息 仅可以支持逻辑查询形式 7 词典的组织 一 索引单词项的集合构成词典 系统通过查找词典定位该单词对应的postinglists 这是从单词到指针的映射 有两种词典的组织方式 直接用B 树等方式组织单词的字符串 用哈希 hash 的方式 速度更快 可以将所有单词装入内存中 8 词典的组织 二 天网 中用哈希的方法实现从单词字符串到单词标识 TermID 整数 的转换 单词的标志是在每次创建索引是赋予的 不是固定的 所有单词的标志是从零开始的连续整数 如果维护一个全局稳定的词典 固定单词的标识 便于维护 系统的TermID可能成为稀疏的整数 可以组织成B 树实现从TermID到指针的映射 9 数据组织 一 倒排文件中单词对应的postinglists部分必须存储在磁盘中 不同单词的postinglists长度差别很大 可以区别对待 存储管理的方法在DBMS已经有深入研究 在倒排文件中 每个单词的postinglists的访问模式是顺序扫描 sequentialscanning 作为一个对象看待最合适 关系数据库管理系统 RDBMS 用于倒排文件的缺点是不太灵活 而且SQL语句的开销比较大 10 数据组织 二 面向对象的概念更能简洁地描述倒排文件的结构 采用面向对象数据库系统 OODBS 是更好的选择 下面是两个被一些IR系统使用的例子 用持久对象存储 PersistentObjectStore Mneme管理倒排文件 Mneme不但提供基于对象的数据缓存和良好的磁盘空间分配策略 还可以用它高度的可扩展性 根据数据的特性定制存储 ObjectStore是商业上最成功的面向对象数据库系统之一 它用内存映射技术实现持久对象存储 和程序语言 C C JAVA 完全集成 既有程序设计语言的灵活 又可以高效的存储数据 是另一个很好的索引管理工具 11 数据组织 三 天网 中用多个文件实现倒排文件的存储 优点是实现简单 可以利用文件的缓存机制 缺点是灵活性差 效率也有所损失 嵌入式数据库系统BerkeleyDatabase BerkeleyDB 是一个开放源代码产品 它提供简单高效的功能 三种访问方法B tree hash recno 实现key value的存取 这已完全能满足索引管理的需求 可以替代OODBS 在WebBase项目中使用 12 实现倒排表的随机访问 高频词 Term 的Postinglists长度通常1Mbytes以上 随着文档数据库规模增大 它会快速增长 称作 longPostinglists 如果对它作顺序访问 从磁盘读入内存会耗费很长时间 同时占用系统大量的I O带宽 从而降低整个系统的吞吐量 解决的方法是将对longPostinglists的顺序访问变成随机访问 randomaccessPostinglists longPostinglists被按照 文档号 分割成长度较小的数据块 在 AND 和 Proximitysearch 操作时可以有选择地访问部分数据 不可能相关的文档所在数据块被 跳过 skip 它增加了按照 文档号 索引数据 以空间换取时间 13 信息检索的缓冲区管理 一 利用文件系统的缓存往往不能得到最佳的性能 根据Postinglists的顺序访问模式 可以采用基于对象的缓存 对象持久存储中的双向缓冲区将对象和分页缓存结合起来 是一种更佳的策略 对很高频的单词 由于它对查询准确度的提高很有限 有些系统将它们作为stopword忽略 不建索引 缓存整个它的Postinglists将占用大量内存 少量的高频词就可以耗尽所有的内存 所以缓存高频词的Postinglists将得不偿失 采用randomaccessPostinglists算法 可以将大对象分解成小对象 缓存对小对象的索引数据 提高内存使用效率 14 信息检索的缓冲区管理 二 J nsson Bj rnT Franklin MichaelJ andSrivastava Divesh Interactionofqueryevaluationandbuffermanagementforinformationretrieval 研究了信息检索中缓存管理和查询的相互作用关系 作者提出两种查询时优化利用缓存的策略 buffer awarequeryevaluation和ranking awarebufferreplacement 前者在查询时优先使用在缓存中的数据来减少读磁盘 后一种技术将数据的语义引入到缓存的替换中 例如关键词的Postinglists要被顺序扫描 每次都必须访问第一个数据页 最后一页则未必需要 所以就应该尽量保持它的第一页在内存中 15 查询处理中的FastRanking技术 主要思想 不检索出全部结果集 只需找出现面K个结果 Retrievepartialdocumentallowingerror 要和相关度评价算法 rankingalgorithm 结合 对数据存储的要求是在每个单词的Postinglists中要按照频率排序 认为单词在文档中出现频率越高 相关度越大 FilteredDocumentRetrievalwithFrequency sortedIndexes 由于只需读取部分数据 可以极大提高检索效率 16 倒排文件压缩 一 影响倒排文件查询效率的主要是关键词的Postinglists 所以必须压缩它的长度 压缩以后减少了内存 磁盘空间的占用和I O带宽的使用 同时要对数据编码和解码 增加了CPU时间耗用 考虑到I O是系统的瓶颈 CPU和I O之间不断扩大的性能差距 以时间换取空间是可行的 压缩不仅能提高查询时的效率 还能加快创建索引 从各方面提升系统性能 17 倒排文件压缩 二 关键词对应的Postinglists是整数的序列 包含文档号 d 关键词在文档中的频度 f 和关键词在文档中的一系列出现 a 压缩的方法首先基于 游程编码 runlengthcoding 增量整数序列被变换为差分序列 原来相邻整数之间的增量序列 由于Postinglists中文档号d和出现位置a 都是递增排列 故可以做 游程编码 变换 游程编码本身并不能实现压缩 只是较大的整数被变换成了较小的整数 频度f本来就是小整数 18 倒排文件压缩 三 字节对齐索引压缩 ByteAlignedIndexCompression 字节对齐索引的优点是容易编码和解码 位操作少 占用CPU时间少 缺点是对很小的整数压缩率低 每个整数最少用一个字节的空间 变长索引压缩 VariableLengthIndexCompression 一元编码 unary 编码和 编码进一步优化的方法是根据整数序列的平均游程长度 meanrunlength 对位向量编码增加参数 称作 局部模式 比较简单的一种方法是 一个整数序列的个数是pw 则它的平均游程长度是N pw 设b 0 69N pw 取VG b b b 作压缩向量 前缀用一元编码 后缀是二进制编码 占用个位 19 倒排文件压缩 四 在非全文索引中 Postinglists由文档号d和文档中的词频f组成 一个 d f 平均用1个字节即可表示 单词t的Postinglists平均长度可以根据t的IDF推算出来 在全文索引中 单词出现的位置信息占据索引数据的主要部分 所以忽略文档号d和文档中的词频f 用变长压缩算法 单词出现位置平均可以用少于8bit的位表示 设全部文档分词后的单词总数是TN 那么单词t总的出现次数是TN TF 它的Postinglists平均长度小于TN TF字节 20 结论 一 用户的大部分查询中的单词数量比较少 查询一个主题时用2 3个单词就可以描述 查询文章的题目时可能有10个单词以上 不妨设Lq表示用户查询中的单词个数 估计平均Lq等于5 根据前面得出的现在一个磁盘的IOPS 100 可以计算出在不考虑数据缓存情况下 系统平均每秒钟处理查询的上限是IOPS Lq 20 根据磁盘的可用带宽大约是20MBytes s 得出每个查询的I O应不大于1Mbytes 也就是满足如下条件 TN TF Lq 1MB 代入以上得出的估计参数 有如下结论 l对汉语字符 TN 400MB TF 0 05 Lq 5 l对英语单词 TN 4GB TF 0 005 Lq 5 21 结论 二 由于汉语的一个字符占两个字节 所以如果对汉语字符建索引 要维持每秒20个查询的系统吞吐量 只能索引800MB的文本数据库 英语的一个单词平均占用字节6 8个 包括空格符 故同样情况下可以索引24 32GB的英语文本 汉语切词后关键词的平均频率达到和英语相近的水平 在 天网 的检索系统中 使用北大计算语言学研究所开发的切词程序 共收录了7 3万词条 切词后对词组建索引 日本的