信息检索——倒排索引和布尔查询
- 线性扫描
- 词项-文档关联
- 倒排索引
- 查询处理AND
- 布尔查询
- 自由文本查询
- 查询优化
举例：查找《莎士比亚》中的人名
1 AND 2 but NOT 3
线性扫描grepping:
从头到尾阅读该全集，对每部剧本都留心是否包含1和2不包含3
缺点：
太慢
不灵活
无法排序
词项-文档关联
缺点：
太大了
而且99.8%的元素都为0
更好的方法是只记录原始矩阵中1的位置
行：文档向量
列：词项向量
1或0：1表示存在；0表示不存在
倒排索引
词项（排序）——文档频率（一个词在几个文档中出现）——倒排记录表（文档编号）
概念：
词项：通常表示词term
文档：可以是一条记录，或者是一本书的某章doc
文档集/语料库：所有文档‘corpus
信息需求：用户想查找的信息主题
正确率：返回结果中和信息需求真正相关的文档所占的百分比
召回率：所有和信息需求真正相关的文档被检索系统返回的百分比
查询处理AND
对两个倒排记录表求交集
倒排记录表以文档ID排序
伪代码：为了让人看懂的代码，论文中常见
代码解释
算法名称：INTERSECT，两个参数，倒排表1和倒排表2
- answer准备放结果，初始化为0
- p1 p2都没结束时继续循环
- 如果p1指向的文档编号与p2指向的文档编号相同
- 相同是我们要的交集结果，把结果添加到answer
- P1往后移
- P2往后移
- 如果p1指向的文档编号与P2不相同，且p1指向的文档编号小于p2指向的文档编号
- P1往后
- 反之p2往后
- 返回结果
- NIL:NULL
布尔查询
使用AND BUT OR来连接查询词项
布尔模型是构建信息检索最简单的模型
30年来最主流的检索模型
自由文本查询
不是通过具有精确语义的逻辑表达式来构建查询，而往往是采用一个或者多个词来构成
区别：
- 很多专业用户更喜欢布尔查询模型（布尔查询表达上更精确）
- 这并不意味着对于专业搜索人员来说布尔查询更加有效
- 采用自由文本查询比布尔查询能取得更好的结果。
- 布尔搜索的AND操作符结果正确率高但召回率偏低，而OR操作符结果的召回率偏高但正确率低
什么时候适合使用布尔查询？
取决于 信息需求，文档集，搜索者
Note9.9√
查询优化
通过组织查询的处理过程来使处理工作量最小
从最小的倒排记录表进行合并，所以我们需要记录文档频率
本例先将1 2合并 再与3合并
倒排表posting p
词项term t
- 查询优化 SortByIncreasingFrequency，按文档频率递增排序，把排序好的放在terms
- First(terms)取出terms中的第一个词，posting（first(terms)）,取出terms中的第一个词的倒排表，放在result
- 剩下的词放在terms，相当于把第一个词从terms中去掉。
- 当terms中还有词时继续循环，result（中间结果和最终结果）不为空时继续。
- .这里的Intersect有2个参数，是两个倒排表求交集的算法
result（中间结果）与terms中的第一个词的倒排表求交集，把结果再放回到result
- 词的倒排表求完交集后，再从terms中去掉
- 返回最终结果
PPT1√