信息检索实验室.pptVIP

索引和查找 胡晓光 信息检索实验室 提纲 顺序查找 索引查找 签名文件 倒排文件 PAT树（Patricia tree） 关于压缩 说明 索引和查找的关系 索引和查找其实是密不可分的 建索引时必须不断的执行查找操作 查找和查询的区别 查找（search） 如何在索引中定位关键词信息 查询（query） Query处理：如何根据用户输入确定关键词 检索模型：如何利用查找返回的信息计算相似度等 文本压缩和索引压缩的区别 注意文本压缩不能有效地减少索引文件的大小 顺序查找 精确匹配算法 Brute Force Knuth-Morris-Pratt Boyer-Moore Shift-Or Suffix Automaton 容错匹配算法 Dynamic Programming Non-deterministic Finite Automaton Bit-Parallelism 正则表达式和扩展模式 索引 索引文件 为方便查找，描述原文件信息组织的文件 签名文件，倒排文档，后缀树都是索引文件 签名文件 Karp-Rabin匹配思想 假设我们现在要判断字符串A和字符串B是否匹配 把A和B分别散列成数字hash (A)和hash (B) 如果hash (A) != hash (B) 则A != B 然而hash (A) = hash (B) 不能说明 A ＝B 签名文件 文档的签名 把文档中的关键词散列成F位的位串Signature 顺序访问原文档的关键词，把散列所得的位串依次存入文件 重叠编码(superimposed coding) 我们不需要为每个关键词都保存一个Signature 多个关键词共用一个Signature可以减少文件的长度 错误匹配（False drop） 由于重叠编码和哈希冲突的原因，关键词和Signature不是一一对应的关系 Signature匹配并不能保证关键词一定出现，还需要检查 签名文件 签名文件 优点 文件组织简单，基本和原文档顺序一致 维护容易，生成，插入，删除都很方便 所需空间小，特别是采用重叠编码之后 缺点 检索速度慢，需要顺序扫描 并且，当False Drop发生的时候需要比较原文档 总之 签名文件是倒排文档和全文扫描之间的折中 倒排文件 倒排索引思想 每个文档都可以用一系列关键词来表示 如果按关键词建立到文档的索引便可以根据关键词快速地检索到相关文档 倒排文件组成 词汇表（Vocabulary） 根据Heap’s定律，通常比较小O (n?), ?: 0.4~0.6 通常我们称存放词汇表的文件为索引文件（index file） 出现位置（Occurrence） 较大，O（n），通常在原文本的30％～40％ 通常我们称存放出现位置的文件为置入文件（posting file） 倒排文件 倒排文件 块地址索引 有时候为了节省索引空间，可按块地址建索引 把原文划分为多个块，只记录关键词的块地址 倒排文件 倒排文件的性能 时间代价主要取决于词汇表的组织方式 词表文件通常较小且比较固定 对于未登录词和数词可以按字建索引 空间代价主要取决于对置入文件的压缩能力 置入文件的压缩能减少IO操作，也能提高部分时间性能 词汇表文件的组织方式 采用Hash散列表 按字母表顺序有序排列 采用Trie树，B树等查找树 置入文件的压缩 通常采用差值压缩（delta compression） 倒排文件 词汇表的哈希存储 根据给定的关键字，散列成一个整数 用该整数作为词汇的访问地址 例如：如果我们按字索引，那么可以直接用字的编码 作为访问地址，对于2字节编码只需64K地址 优点 实现简单 速度极快 缺点 关键在于找到一个好的散列函数 随着现在散列空间的增大，问题相对简单 当冲突过多时效率会下降 倒排文件 词汇表的顺序排列 把词汇按照字典顺序排列 词汇的查找采用二分查找 优点 实现简单 词汇表体积小（通常只有几兆） 缺点 索引构建的效率一般 对于插入的文档需要反复地调用排序和查找算法 排序的时间复杂度为N*log N （分配排序例外） 索引合并时还需要堆排序等方法合并多个有序的词汇表 如果合并最主要的时间开销在于IO操作的话，这点还是次要的 检索的效率一般 二分查找logN的复杂度已经具有较好的效率 能不能变成和词汇数量无关的常数复杂度 倒排文件 Lucene的词汇表即采用这种方式 假设现在词表中有16，000个词 indexInterval=16 则在词表中需要查找次数为16＋log(1000) = 26次 倒排文件 词汇表的查找树 把词汇表中的关键词以树的形式组织 二叉树，B树，Trie 等 二叉查找树 考虑到平衡性，性能低于二分查找 B树 是多路查找树，效率高于二叉树，实现更麻烦 Trie