信息检索复习（1）——布尔查询

信息检索概述

信息检索（Information Retrieval，简称IR）：是从大规模非结构化数据（通常是文本）的集合（通常保存在计算机上）中找出满足用户信息需求的资料（通常是文档）的过程。

信息检索分类（依据所处理数据的规模）

1. Web搜索
2. 个人信息检索
3. 面向企业、机构和特定领域的搜索

---

建立索引

• 词项-文档矩阵（incident matrix）
  行：得到每个词项对应的文档向量，表示词项在哪些文档中出现或不出现
  列：得到每个文档对应的词项向量，表示文档中哪些词项出现或不出现
  问题：该矩阵具有高度的稀疏性，仅仅保存非零的位置明显更好
  ps：词项按照字符表排序

词项-文档关联矩阵.png

• 布尔查询模型
  接受布尔表达式查询：AND、OR、NOT等逻辑操作符
  例：brutus AND caesar AND NOT calpurnia

  1. 取出brutus、caesar、calpurnia对应的行向量，并对calpurnia向量取反，然后进行基于位的与操作
  2. 110100 AND 110111 AND 101111 = 100100
  3. 结果向量中的第1、4个元素值为1，返回Antony And Cleopatrahe 和 Hamlet

• 倒排索引
  过程：收集文档 - 词条化 - 词项 - 建立倒排索引
  文档频率：出现某词项的文档的数目

  1. 对每个词项t, 记录所有包含t的文档，建立词条序列<词条，docID>二元组
  2. 对词项、文档排序。按词项排序，然后每个词项按docID排序

  3. 合并词项，并常记录文档频率df（对每个词项t, 记录所有包含t的文档数目）

     
     倒排索引表.png

• 查询优化策略
  按照词项的文档频率，从小到大依次进行处理，如果我们先合并两个最短的倒排记录表，那么所有中间结果的大小都不会超过最短的倒排记录表