布尔检索

IR：广义上指信息获取。

非结构化数据：没有清晰和明显的语义结构的数据，严格意义上讲，非结构化数据并不存在。

结构化数据：与非结构化数据相对，如关系数据库。

半结构化数据：如网页这种具有格式标记的数据。

按照所处理数据的规模进行区分可分为3个主要级别：

大规模级别，Web 搜索(web search)，搜索存储在数百万台计算机上的数十亿片文档。

中等规模级别，面向企业，机构和特定领域的搜索(domain-specific search)。

小规模级别，如个人信息检索(personal information retrieval)。    `

1.1一个信息检索的例子

以莎士比亚全集为例。

想知道那些剧本包含Brutus和Caesar但是不包含Calpurnia。

解决方案线性扫描：在规模不大的的文档集进行线性扫描很简单，不需要额外处理。

但是对于以下情况：

(1)大规模文档集条件下的快速查找。

(2)有时需要更灵活的匹配方式。

(3)需要对结果进行排序。

一种非线性的扫描方式是事先给文档建立索引(index)。

在该例子中建立词项-文档关联矩阵(incidence matrix)。词项(term)是索引的单位。

为响应查询Brutus AND Caesar AND NOT Calpurnia，分别取出Brutus，Caesar，Calpurnia对应的行向量，并对Calpurnia对应的行向量取反，然后进行基于位的与操作，得到110100 AND 110111 AND 101111 = 100100。结果向量第1位和第4位是1，表明查询的结果是Antony and Cleopatra和Hamlet。

布尔检索模型接受表达式查询，即通过AND、OR 及NOT 等逻辑操作符将词项连接起来的查询。在该模型下，每篇文档只被看成是一系列词的集合。

我们的目标是建立一个ad hoc检索系统，在这个任务中，任一用户的信息需求通过一次性的、由用户提交的查询传递给系统，系统从文档集中返回与之相关的文档。

正确率(precision)：返回的结果中真正和信息需求相关的文档所占的百分比。

召回率（Recall）：所有和信息需求真正相关的文档中被检索系统返回的百分比。

词项-文档关联矩阵实际上具有高度的稀疏性。所以为了节省存储空间，引入倒排记录表(inverted index)。左部称为词项词典(dictionary，简称词典，有时也称为vocabulary或者lexicon。而vocabulary则指词汇表)。每个词项都有一个记录出现该词项的所有文档的列表，该表中的每个元素记录的是词项在某文档中的一次出现信息(在后面的讨论中，该信息中往往还包括词项在文档中出现的位置），这个表中的每个元素通常称为倒排记录(posting)。如图：

倒排索引的两个部分。词典部分往往放在内存中，而指针指向的每个倒排记录表则往往存放在磁盘上

1.2构建倒排索引的初体验

为获得检索速度的提升，就必须要事先建立索引。建立索引的主要步骤如下：

(1) 收集需要建立索引的文档。

(2) 将每篇文档转换成一个个词条(token)的列表，这个过程通常称为词条化(tokenization)。

(3) 进行语言学预处理，产生归一化的词条来作为词项。

(4) 对所有文档按照其中出现的词项来建立倒排索引，索引中包括一部词典和一个全体倒排记录表。

针对(4)，给定一个文档集，我们假定每篇文档都有一个唯一的标识符即编号(docID)。在索引构建过程中，我们可以给每篇新出现的文档赋一个连续的整数编号。在上述的前3 步处理结束后，对每篇文档建立索引时的输入就是一个归一化的词条表，也可以看成二元组(词项，文档ID)的一个列表。建立索引最核心的步骤是将这个列表按照词项的字母顺序进行排序，其中一个词项在同一文档中的多次出现会合并在一起，最后整个结果分成词典和倒排记录表两部分，前者往往放在内存中，而后者由于规模大得多，通常放在磁盘上。由于一个词项通常会在多篇文档中出现，上述组织数据的方法实际上也已经减少了索引的存储空间。词典中同样可以记录一些统计信息，比如出现某词项的文档的数目，即文档频率（document frequency），这里也就是每个倒排记录表的长度，该信息对于一个基本的布尔搜索引擎来说并不是必需的，但是它可以在处理查询时提高搜索的效率，因此它在后面介绍的排序检索模型中被广泛使用。倒排记录表会按照docID进行排序，这为高效的查询处理提供了重要基础。在ad hoc文本检索中，倒排索引是其他结构无法抗衡的高效索引结构。

通过排序和合并建立倒排索引的过程

1.3布尔查询的处理

如何使用倒排索引和基本布尔检索模型来处理一个查询呢？以Brutus AND Calpurnia为例：

(1) 在词典中定位 Brutus；

(2) 返回其倒排记录表；

(3) 在词典中定位Calpurnia；

(4) 返回其倒排记录表；

(5) 对两个倒排记录表求交集，

Brutus AND Calpurnia交集计算的示意图

求交集算法：

两个倒排记录表的合并算法

查询优化(query optimization)指的是如何通过组织查询的处理过程来使处理工作量最小。对布尔查询进行优化要考虑的一个主要因素是倒排记录表的访问顺序(短的在前，长的在后)，还可以采用其他存储方式，如hash表。

在输入多个词项的与查询时对它们的倒排记录表进行合并的算法

1.4对基本布尔操作的拓展及有序检索

和布尔检索模型相对的是排序检索模型或有序检索模型(ranked retrieval model)，后者不是通过具有精确语义的逻辑表达式来构建查询，而往往是采用一个或者多个词来构成自由文本查询(free text query)。有序检索系统要能够确定哪篇文档最能满足用户的需求。

很多用户，特别是专业用户，更喜欢布尔查询模型。布尔查询表达上更精确：文档要么满足查询，要么不满足查询。这可以让用户对返回结果拥有更好的控制力和透明度。但是布尔搜索的一个普遍问题就是采用 AND 操作符产生的结果正确率虽高但是召回率偏低，而采用 OR 操作符召回率高但是正确率低，很难或者说不可能找到一个令人满意的折衷方案。

1.5总结

本章中，我们讲述了基本倒排索引的结构和构建，整个索引包含词典和倒排记录表两部分。我们介绍了布尔检索模型，并考察了如何通过线性时间复杂度的合并方法和简单的查询优化方法来进行高效检索。在第2～7 章中，我们会考虑更丰富的查询模型及各种用于高效查询处理的增强的索引结构。在这里，我们仅仅先提一下它们的要点。

(1) 我们要更好地确定词典中的词项表，提供一个能够容忍拼写错误以及当查询和文档中词语表达不一致时的检索方法。

(2) 对能够表示某概念的复合词或者短语(如“ operating system” )进行搜索是非常有用的有时我们希望能够执行诸如“ Gates NEAR Microsoft” 这类的邻近查询，为处理这类查询，索引结构必须要改进。

(3) 布尔模型只记录词项存在或者不存在，但是我们往往需要累加各种证据来得到文档相关的可信度。比如，如果一个查询项在某文档中多次出现，我们会给该文档赋予一个权重，该权重会比仅仅出现一次查询项的文档要高。为了实现这个目的，我们需要引入词项频率(词项在文档中出现的次数)的概念。

(4) 布尔查询仅仅返回一个无序的文档集，但是我们往往需要对返回的结果排序(或排名)，这就需要提供一个机制在给定查询的情况下对每个文档的好坏进行评分。