信息检索导论(译)：第一章 布尔检索(1)

信息检索这个词的含义非常广。仅从钱包中取出信用卡，然后输入信用卡号也属于信息检索的范畴。然而，从学术角度来讲，信息检索定义如下：

信息检索即从大量非结构化文档集中找到满足需要的文档的过程。

按照如上定义，信息检索曾经是仅少数人如图书管理员，律师，专业搜索者参与的活动。而今非昔比，当今成千上万的人每天都会用搜索引擎搜索网页和邮件。信息检索正迅速取代传统的数据库搜索的方式，成为信息获取的主要方式。除此之外，信息检索技术还可以解决其他有关数据和信息的问题。所谓非结构化数据，指的是没有清晰的可被计算机理解的语义结构的数据。与之相对的是结构化数据，例如传统的关系型数据库，被很多公司用来保存产品库存及员工信息。现实世界中，几乎没有数据是完全没有结构的，尤其把人类语言的潜在语义结构考虑在内的情况下。即便认为只有刻意标注的结构才属于结构化的，大多数文档都有标题，正文，下标等结构，且在文档中被显式标注的。信息检索技术还可以进行半结构化搜索，如寻找标题含有Java，正文中含有threading的文档。

信息检索领域还包括帮助用户浏览，过滤文档集，以及对检索结果进行再处理。

聚类，即给定一文档集，根据它们的内容将文档分组的过程。类似根据主题将书籍分放到不同的书架上。

分类，即给定一些类别及一组文档，判断每篇文档属于哪个类别的过程。通常此过程首先人工将一部分文档进行分类，以期新的文档可以自动判断所属的类别。

信息检索系统可以根据规模分成以下三大类：

互联网搜索(Web Search)：系统的搜索对象是存储在数百万计算机上的数十亿的文档。互联网搜索系统所面临的主要问题是如何获取要索引的文档，如何高效处理大容量的数据，以及如何应对互联网特有的问题，例如跟踪挖掘超链接，防止站点欺骗(鉴于互联网的商业价值，有的站点会修改网页内容从而获得更高排名)。

个人信息检索(personal information retrieval)：近年来，个人电脑操作系统开始集成信息检索系统。邮件系统通常不仅仅提供搜索功能，而且提供文本分类功能，即其至少提供垃圾邮件过滤器，也一般会提供自动或者手动的分类器，使得不同的邮件被放入不同的文件夹中。此类系统所面临的主要问题包括如何处理个人计算机上多种多样的文档类型，系统可免费维护，在启动，处理及磁盘使用方面足够的轻量级，不妨碍用户正常使用。

企业级搜索(enterprise search)：主要是针对公司内部文档，专利数据库及研究论文进行检索。此种情况下，文档往往是集中存储在统一的文件系统上，一台或多台专用电脑复杂对它们进行检索。

本书讲述的技术涵盖了以上所有的范畴。然而对于互联网搜索系统中的并行及分布式检索的等方面相对涉及较少，因为有关此方面的论文也相对较少。然而除了几家互联网搜索的公司外，大多数程序员更多可能接触的是个人信息检索系统和企业级搜索系统。

本章，我们从一个简单的信息检索问题入手，介绍词条(term)-文档(document)矩阵的概念，以及最重要的倒排表数据结构。然后我们介绍布尔检索模型及如何处理布尔查询。

一个简单的信息检索问题

相信很多朋友都有莎士比亚全集这本砖头书。假设你想找出莎士比亚的那部歌剧包含Brutus和Caesar，但不包含Calpurnia。一种方式是，从头至尾阅读整本书，依次找出那些包含Brutus和Caesar，但不包含Calpurnia的歌剧。这是文档检索最简单的方式，称为顺序扫描法。这个过程常被称为grep，正如Unix命令所作的一样。顺序扫描法可以十分有效，尤其在现代计算机高处理速度的情况下，而且还常常允许使用通配符。对于如莎士比亚全集这种小于百万字的文本集时，现代计算机的速度已经足够慢速此类简单的查询，我们别无所求。

然而某些情况下，并非如此：

1. 迅速处理大量文档集。互联网上的数据量的增长速度已经超过计算机的处理速度，而我们期望能够搜索包含数十亿甚至数万亿字的文档集。

2. 支持更加灵活的查询方法。例如，用grep查找Romans NEAR countrymen是不可能的，此处NEAR表示在五个字内或者在一句话内。

3. 允许对检索结果进行排名。多数情况下，你想要的是包含特定词的文档中最好的，最能满足搜索需要的那一篇。

代替顺序扫描的一种方法是事先对文档建索引。让我们仍以莎士比亚全集为例，来介绍布尔检索模型的基本概念。假如我们记录下每篇文档(此处为莎士比亚的一部歌剧)是否包含每个莎士比亚用过的词(莎士比亚总共用了32000个词)。结果是我们得到了一个二进制的词条(term)-文档(document)的索引矩阵。词条(term)是索引的基本单位，其多数情况下是单词，至少现在你可以这样认为，然而有的词却不仅仅是单词，如I-9或者Hong Kong，所以在信息检索领域，我们称之为词条(term)。当我们按行来看这个矩阵的时候，我们会得到一个向量，表示每个词条在那些文档中出现过。当我们按列来看这个矩阵的时候，我们会得到一个向量，表示都有哪些词在此文档中出现过。

为得到Brutus AND Caesar AND NOT Calpurnia的查询结果，我们首先得到Brutus，Caesar和Calpurnia的向量，对最后一个向量取反，然后对三个向量进行二进制与运算(AND)：

110100 AND 110111 AND 101111 = 100100

最后我们得到满足条件的两个歌剧，“Antony and Cleopatra”及“Hamlet”。

布尔检索模式即将词按照布尔表达式的方式用and, or not连接起来组成查询语句，并将每篇文档看成一系列词的集合。

现在，让我们考虑一个更加实际的情形，并同时利用此机会介绍一些名词和符号。假设我们有N=1M的文档，此处所谓文档(Document)即任何我们构建信息检索系统的一个单位，可以使一篇备忘录，也可以是一本书中的一章或几章。所谓的文档集(collection)即我们要进行检索的一组文档，有时又被称为语料库(corpus)。假设每篇文档包含1000个词(一本书的两三页)。假设每个词(包含空格和标点符号在内)平均占用6个byte，则此文档集大约有6GB。通常，在这些文档中共有大约M=500000个不同的词。我们没有刻意选择这些数字，其也可能随着文档量的不同而不同，但却给我们提出了此类必须解决的问题，即数据量的问题。我们会在5.1节讨论这些有关数据量的假设，并对其建模。

我们的目的是开发一个可以完成此类特定检索任务的系统。这个标准的信息检索任务即：通过它，系统可以根据任意用户一次性发起的查询语句，提供文档集中同用户的信息检索需求相关的文档。所谓信息检索需求即用户期望得知的话题，它和查询(query)不同，所谓查询是用户将自己的信息检索需求表达为计算机可理解的方式。所谓一篇文档是相关的即用户认为此文档包含其信息检索需求相关的信息。上面的例子中，信息检索需求被表达为一系列特定词的组合，是为了表述问题而人为设定的，在现实生活中，比如用户关心的是”管道泄露”相关的话题(信息检索需求)，但是他们想找的文档可能并不一定精确的包含这些词，也可能他们会用其他的词来表达自己的需求，如”管道爆裂”(查询)。为了衡量信息检索系统的效果，用户可能会期望知道查询结果的两个重要统计指标：

精确度(Precision)：返回的结果中有多大比例和信息检索需求相关。

召回率(recall)：文档集中的相关文档有多大比例被返回了。

我们将在第八章详细讨论相关性的评估，包括精确度和召回率。

现在，我们不能再如此简单的构造一个词条-文档矩阵。一个500K x 1M的矩阵有半兆个0和1，这太多了，不能够保存在内存中。然而一个重要的发现是，矩阵是稀疏的，非零项只占很少的一部分。因为每篇文档仅包含1000个词，此矩阵有不超过十亿个1，也即至少99.8%项是0。所以一个更好的表示方法是仅仅记录值为1的项。

通过此理念，我们很容易得到信息检索一个重要的概念：反向索引(inverted index)。反向索引这个名字实际上是冗余的，因为一个索引总是从词条映射到包含它的文档。尽管如此，反向索引，或者说反向文件，成为信息检索领域的一个标准术语。图1.3展示了反向索引的基本概念，我们维护了一个词条组成的词典，对于每一个词条，都有一个列表保存着包含这个词条的文档。列表中的每一项称为一个posting，此列表称为Posting list(倒排表)。图1.3中的词典按照字母顺序排序，每个倒排表中的文档按照文档号排序，1.3节中，我们会看到，这种排序是很有用处的，在7.1.5节中，我们还考虑了其他方案。

尝试构建反向索引

为了在检索阶段获取索引的速度优势，我们必须事先创建索引。主要的步骤如下：

1.收集要索引的文档

2. 对这些文本进行分词，将文档变成一个个的词的序列

3. 进行语言处理，将此一序列的词标准化，形成词条

4. 将词条和文档创建成反向索引，包括词典和倒排表。

我们将在第2.2节定义并讨论1至3步，在此之前，你可以简单的认为词或者标准化后词等同于单词。在此，我们假设前三步都已经完成，我们重点来看如何通过排序来构建一个基本的反向索引。

在一个文档集中，我们假设每一篇文档都有一个唯一的序列号，称为文档号。在索引创建过程中，我们可以简单的给每一个新来的文档附一个连续的整型作为文档号。对于每一篇文档，索引的输入是一系列标准化的词，我们也可以认为是一系列词条和文档号的二元组合，如图1.4所示。索引阶段一个核心的步骤是对这些词条按照字典顺序排序，如图1.4中中间一列所示。出现在同一篇文档的同一个词条的多次出现合并，相同的词条合并，并将结果分成词典和倒排表两部分，如图1.4中右面一列所示。由于一个词条一般出现在不多的文档中，这种数据组织方式已经减少了索引所占用的存储空间。词典还保存了一些统计信息，比如有多少篇文档包含此词条(称为document frequency，文档频率)。这些信息对于布尔搜索引擎不十分重要，然而却可以使我们在搜索阶段提高效率，并在需要排序的信息检索模型中发挥作用。倒排表按照文档号排序，这为高效的处理搜索奠定了基础。反向索引对于此类特定的信息检索来接无疑是最有效率的结构。

在最后形成的索引中，我们存储了词典和倒排表。其中后者占用的空间更大，词典多保存在内存中，倒排表多保存在硬盘中，所以两者占用的空间大小事很重要的，在第五章，我们会讨论如何优化二者的存储从而提高访问效率。

在倒排表中应该使用什么样的数据结构呢？定长的数组可能会比较浪费，因为有些词在很多的文档中出现，而有的词却在很少的文档中出现。对于内存中的倒排表，有两种较好的选择，一是单链表，一是变长数组。单链表使得文档插入倒排表比较廉价，而且可以很自然的扩展到如跳表这种更高级的索引方式，然而他需要额外的空间存储指针。变长数组在空间需求方面避免了指针带来了额外空间，在时间需求方面也因使用连续内存可以加快速度。实践中，额外的指针可以编码为偏移量放在链表中。如果更新相对不频繁，变长数组会更加紧凑和易于遍历。我们还可以用一个折中的方式，对每一个词条保存一个链接在一起的定长数组。当倒排表被存储在硬盘上的时候，其能够被存储为没有显式指针的连续空间，这样就可以减少倒排表的大小及把倒排表读入内存而读取硬盘的次数。