信息检索导论读书笔记(二):布尔检索、倒排索引、倒排索引表合并算法、短语查询

时间:2024-03-31 22:30:18

布尔检索:

       布尔检索模型接受布尔表示查询,即通过AND、OR及NOT等逻辑操作符将词项连接起来进行查询,在该模型下,每篇文档只被看成是一系列词的集合。布尔搜索的一个普遍问题就是AND操作产生的结果正确率高但是召回率偏低,而采用OR操作符召回率高但是正确率低,因此很难或者说不可能找到一个令人满意的这种方案。

倒排索引:

       倒排索引是信息检索内第一个核心概念。倒排索引中左侧为词项词典,右侧为全体倒排记录表,每个词项对应的表成为倒排记录表,每个倒排记录表中包含多个存在词项的文档编号,每个编号是一个倒排记录。

信息检索导论读书笔记(二):布尔检索、倒排索引、倒排索引表合并算法、短语查询

     实现倒排索引遵循一定的步骤:

  1. 词条化,定义好文档单位之后将给定的字符序列拆分为一系列词条(token)。
  2. 去除停用词,停用词有被抛弃的趋势,Web搜索引擎通常都不用停用词。
  3. 词条归一化,将看起来不完全一致的多个词条(如大小写,重音变音符号,连接符)归纳成一个等价类,以便在它们之间进行匹配的过程,建立的过程是隐式的,可以对规则进行定义。
  4. 词干还原与词形归并,前者往往是粗略地去除单词两端词缀,后者是利用词汇表和词形分析去除屈折词缀从而返回词的原形。示例:saw,词干还原返回s,词形归并返回see或saw。两者对检索效率提高跟语言有关系,对英文提升不大。

经过上面几个步骤可以得到倒排索引表,当查询两个词项的交集时只要求词项对应的倒排记录表交集即可。

倒排记录表快速合并算法:

       普通合并算法及数据结构与算法中的双指针法,两个指针分别指向两个倒排记录表,然后寻找文档编号相同的值,时间复杂度显然就是记录总数即O(m+n),多个词项求交集的实际操作过程中可以先从出现频率最低的记录表开始求交,这样可以减小中间结果的长度,最大可能减小时间消耗。

       为了进一步提升记录表合并的效率,使用了跳表,其实所谓跳表就是增加几个额外的指针指向后面较大的值,这样使用双指针法合并时可以加快指针移动速度。实践中,通常选取跨度为信息检索导论读书笔记(二):布尔检索、倒排索引、倒排索引表合并算法、短语查询

信息检索导论读书笔记(二):布尔检索、倒排索引、倒排索引表合并算法、短语查询

短语查询:

       短语是指一些连接在一起使用的复合词,如Stanford University,大部分搜索引擎都支持通过双引号标记短语以便于进行短语查询,有研究表明短语查询占到了Web总查询数量的10%。

       要实现短语查询,主要实现方式主要有:二元词索引、位置信息索引以及混合索引。

       二元词索引,是指短语中两两相邻的单词作为一个词项,比如Stanford university palo alto会被分为三个词项:Stanford university、university palo、palo alto。而对于被虚词间隔的短语,比如the abolition of slavery,则可以首先对短语中的单词进行词性标注(名词N、虚词X),然后将短语看成XNXN的序列看成扩展的二元词,也叫短语索引。这种实现方式会大大增大倒排记录表的大小。

       位置信息索引是在记录表中记录词项在文档中出现的位置,进行短语搜索时使用 k 词近邻搜索,即要求短语中的单词出现位置间隔不超过 k 的文档内容才会出现在搜索结果中。大文档下,索引消耗的存储空间也增大很多。

       混合索引则是将前述两者结合起来,对某些短语使用二元词索引和短语索引,而对于其他短语采用位置索引。短语索引应该收录哪些查询开销最大的短语,这种短语往往是其中的每个单词都很常见但组合成的短语却很少见,比如将the who加入短语索引可以提高1000倍搜索效率。