信息检索与 Web 搜索 第 2 讲 布尔检索 Boolean Retrieval 授课人：高曙明 * 改编自 “ 现代信息检索 ” 网上公开课件（ ）

布尔检索  针对布尔查询的检索，布尔查询是指利用 AND, OR 或者 NOT 操作符将词项连接起 来的查询 信息 AND 检索 信息 OR 检索 信息 AND 检索 AND NOT 教材  Google 支持布尔检索 2

布尔检索模型  检索模型： 查询与文档之间的相关性定义，文档及 查询的表示  布尔检索模型 文档采用词项集合表示 查询用词项的布尔表达式表示 相关性：整个查询的相关性通过对词项相关性进行布 尔运算得到，对于查询中的每个词项，包含则相关 相关性只有相关和不相关两种 3

基于扫描的布尔检索  信息需求： 确定莎士比亚的哪些剧本包含 Brutus 及 Caesar 但是不包含 Calpurnia  布尔查询表示： Brutus AND Caesar AND NOT Calpurnia  简单直接的方法： 从头到尾扫描所有剧本，对每部剧本 判断它是否包含 Brutus AND Caesar ， 同时又不包含 Calpurnia  存在的问题 速度超慢 ( 特别是对超大型文档集 ) 难以支持更复杂的查询 (e.g., find the word Romans near countrymen) 不支持检索结果的排序 ( 即只返回较好的结果 ) 4

词项 - 文档关联矩阵 若某剧本包含某单词，则 该位置上为 1 ，否则为 0 Brutus AND Caesar BUT NOT Calpurnia  词项 - 文档关联矩阵： 给定一个词项集和一个文档集，指由 其中的 词项和文档之间的关联关系形成的矩阵

基于关联向量的布尔检索  关联向量： 指关联矩阵的每一行、每一列对应的向量  给定查询 Brutus AND Caesar AND NOT Calpurnia  具体步骤： 取出三个相应的行向量 ，并对 Calpurnia 的行向量求补，最后按位进行与操作 AND AND =  检索结果： Antony and Cleopatra 和 Hamlet 6

一个更真实的场景  假定 N = 1 百万篇文档 (1M), 每篇有 1000 个词 (1K)  假定每个词平均有 6 个字节 ( 包括空格和标点符 号 ) 那么所有文档将约占 6GB 空间.  假定词汇表的大小 ( 即词项个数 ) M = 500K 7

超大的词项 - 文档矩阵  矩阵大小为 500K x 1M=500G  但是该矩阵中最多有 10 亿 (1G) 个 1 词项 - 文档矩阵高度稀疏 (sparse). 稀疏矩阵  不应简单地建立和存储词项文档关联矩阵  应该有更好的表示方式 比如我们仅仅记录所有 1 的位置 8 Why?

倒排索引 (Inverted index) 9 Dictionary Postings 按 docID 排序 Posting Brutus Calpurnia Caesar 词典 倒排 ( 记录 ) 表 倒排记录  倒排索引示意图

倒排索引  核心思想： 对每个词项 t, 记录所有包含 t 的文档列 表，其中每篇文档用 docID 表示  文档列表的数据结构： 能否采用定长数组的方式 来存储 docID 列表 ？  通常采用变长表方式存储倒排表 磁盘上，顺序存储方式比较好，便于快速读取 内存中，采用链表或者可变长数组方式 存储空间 / 易插入之间需要平衡 10

Tokenizer 词条流 Friends RomansCountrymen 倒排索引构建 Linguistic modules 与词项对应的词条 friend romancountryman Indexer 倒排索引 friend roman countryman 待索引文档 Friends, Romans, countrymen. 词条化工具 语言分析工具

索引构建过程 : 词条表生成  将每篇文档转化为 二元组列表 I did enact Julius Caesar I was killed i' the Capitol; Brutus killed me. Doc 1 So let it be with Caesar. The noble Brutus hath told you Caesar was ambitious Doc 2

索引构建过程 : 排序  首先按词项排序  然后对每个相同词项按 docID 排序 索引构建的核心步骤

索引构建过程 : 词典 & 倒排表  某个词项在单篇文档中 的多次出现会被合并  拆分成词典和倒排记录 表两部分  每个词项出现的文档数 目 ( doc. frequency, DF ) 会被加入

存储开销计算 15 指针 词项及文 档频率 后续章节 : 如何快速构建索引 ? 如何减少存储开销 ? 倒排索引 docID 表 第一讲：布尔检索

布尔查询的处理 : AND  给定一个布尔查询 : Brutus AND Caesar  首先在词典中定位 Brutus 返回其倒排记录表  再在词典中定位 Caesar 返回其倒排记录表  合并 ( Merge ) 两个倒排记录表，即求交集 Brutus Caesar

倒排表的合并  每个倒排记录表都有一个定位指针，两个指针同时从前 往后扫描, 每次比较当前指针对应的倒排记录，然后移 动某个或两个指针。  假定表长分别为 x 和 y, 那么上述合并算法的复杂度为 O(x+y)  关键原因 : 倒排记录表按照 docID 排序 Brutus Caesar 2 8

合并算法的伪代码 18

布尔查询的处理 : OR/NOT  OR 表达式： Brutus OR Caesar 两个倒排记录表的并集  NOT 表达式： Brutus AND NOT Caesar 两个倒排记录表的差集  一般的布尔表达式 (Brutus OR Caesar) AND NOT (Antony OR Cleopatra)  查询处理依序而行？ 19

查询处理的效率问题  考虑 n 个词项的 AND 查询  对每个词项，取出其倒排记录表，然后两两合并 Brutus Caesar Calpurnia 查询 : Brutus AND Caesar AND Calpurnia 20

查询处理顺序的优化  优化策略：按照表从小到大的顺序进行处理 21 这是为什么保存 df 的原因之一 相当于处理查询 (Calpurnia AND Brutus) AND Caesar Brutus Caesar Calpurnia

一般化的优化处理  针对一般的布尔表达式，首先进行形式转化， e.g., (madding OR crowd) AND (ignoble OR strife) 每个布尔表达式都能转换成上述形式 ( 合取范式 )  然后获取每个词项的 df ，并通过将词项的 df 相加估 计每个 OR 表达式对应的倒排记录表的大小  最后从小到大依次处理每个 OR 表达式 22

布尔检索的优点  构建简单，是构建 IR 系统的一种最简单方式  查询表达方式直观清晰，易于理解  在 30 多年中是最主要的检索工具  当前许多搜索系统仍然使用布尔检索模型 电子邮件、文献检索系统、 Mac OS X Spotlight 工具 23

布尔检索系统 : WestLaw  最大的商业化法律搜索服务引擎 (1975 年开始提 供服务 ; 1992 年加入排序功能 )  几十 T 数据， 700,000 付费用户  大部分用户仍然使用布尔查询  查询的例子 : 有关对政府侵权行为进行索赔的诉讼时效 (What is the statute of limitations in cases involving the federal tort claims act? ） LIMIT! /3 STATUTE ACTION /S FEDERAL /2 TORT /3 CLAIM 24

布尔检索的不足  难以表达复杂的用户信息需求 想查关于 2011 年快女 6 进 5 比赛的新闻，用布尔表 达式怎么构造查询？ (2011 OR 二零壹壹 ) AND ( 快乐女声 OR 快女 OR 快乐女生 ) AND (6 进 5 OR 六进五 OR 六 AND 进 AND 五 ) 表达式相当复杂，构造困难！ 不严格的话结果过多，而且很多不相关；非常严格 的话结果会很少，漏掉很多结果 25

布尔检索的不足  没有充分利用词项的频率信息  不能对检索结果进行排序  检索输出量无法合理控制  难以支持相关反馈 26

参考资料  《信息检索导论》，第一章  莎士比亚全集 :  Managing Gigabytes( 深入搜索引擎 ), 3.2 节  《现代信息检索》, 8.2 节 27

课后作业  见课程网页 : 28