信息检索问题的一个实例

许多人可能拥有莎士比亚的作品集，假设你想要在其中找到某一个作品，这个作品含有单词 Brutus 和 Caesar 并且不能含有 Calpurnia。很容易想到的一个方法是从头到尾把所有的作品集都读一遍，然后去查找符合这样条件的文档。计算机最简单的一种文档检索的形式就是对文档进行类似的线性扫描。这样的一个过程通常被称为 grepping through text,类似 Unix 的 grep 命令。对于现代计算机的处理速度而言，这样的一种方式有时候是非常高效的，通配符的使用也成为了可能。对于现代计算机，以及那些简单的查询而言，这样的方法可能就已经足够了。(莎士比亚的作品集大概总共一百万字左右)

但是为了其他的一些目的，你需要更多：

1. 为了更快速的处理大型的文档集。当前网络的数据量的增长丝毫不亚于计算机的发展速度，现在我们更关心是否能够对十亿甚至万亿的单词的检索。

2. 为了更加灵活的匹配操作。例如，想要使用 grep 执行以下的查询就会变得不那么现实，Romans NEAR countrymen ，这里的 NEAR 可以被定义为 within 5 words 或者是 within the same sentence。

3. 为了能够进行对检索的排序：很多情况下你想要的只是那个最佳的匹配结果。

避免这样的线性扫描的方法是事先对这些文档排序。就拿莎士比亚的文集来说，大概里面有 32,000 个不同的单词。对每个文档而言，我们纪录下来是否某个单词在这个文档内出现，这样我们就得到了一个二元的 term-document incidence matrix。Terms 就是被标记的单元，通常就是单词，但有时候也可能是词组，比如 Hong Kong ，因为单纯的 Hong 和 Kong 并没有意义。现在，我们有了一个矩阵，从行或者列来看的话，我们也可以把某一行理解为一个向量。

如果说要处理查询 Brutus AND Caesar AND NOT Calpurnia ，我们先取出 Brutus,Caesar,Calpurnia 所对应的向量，再对最后那个向量进行取反操作，最后在每一位上进行与运算：

对应的答案就是 Antony and Cleopatra and Hamlet 。

对于布尔检索模型而言，我们可以以布尔表达式的形式来进行查询，包括了基本的 and,or,not 这些操作。该模型把每一个文档看作是很多单词的集合。

现在让我们考虑一个更加现实的场景，并且引入一些新的术语和概念。假设我们有 $N = 1\mbox{ million}$ 文档，我们基于这些文档来构建检索系统。它们可以是单独的纪录或者书的某些章节。有时候也称它们为语料库(一系列文本的合集)。假设每个文档大约有 1000 字长(2-3 页)。如果我们假设平均每个字大约占 6 bytes，包括空格和标点符号。那么我们的整个文档大约占了 6 GB 。典型来说，大概有 $M = 500{,}000$ 不同的 terms 在这些文档里。这里我们假设的这些数字并没有什么特殊的地方，它们当然也可以是其他的值，这里只是要对我们面临的数据量进行一个大致的估算。

我们的目标是要构建一个系统来这门完成某种信息检索的任务。(原文提到的是 ad hoc retrieval，大意是指数据库基本维持不变，变化的是用户的检索请求)这也可以算是最为标准的一种 IR 任务了。系统在现有文档的基础上，为用户的任意查询提供相关的文档，这样的交互一般是用户发起，并且是 one-off 的。什么是 information need 呢？这涉及到用户想要了解的某一个主题，并且是从用户的查询里区分出来，传达给计算机的对这个主题的需求。一个文档可以说是相关的，如果用户能够发现该文档对于他/她的 information need 是有价值的。我们之前的例子可能没有那么的符合实际，比较偏向于某些特定的单词。然而现实中人们可能更倾向于对某个主题，例如 pipeline leaks 相关的信息，用户可能并不会非常精确地输入他/她的需求。为了评估一个 IR 系统的有效性(比如搜索结果的质量)，用户通常会想要知道两个关键的统计数据：

1. Precision : 返回的结果中，有多少是需求相关的呢？
2. Recall : 相对于整个文档，有多少需求相关的结果被返回了？

在第八章会有对相关性评估更为详细的阐述，包括精确率以及重现率这两个指标。

我们现在还不能比较轻松的构建一个 term-document matrix。一个 $500\mathrm{K} \times 1\mathrm{M}$ 的矩阵有万亿个0和1，对于现在的计算机内存来说，这太大了。但是如果你仔细观察，你会发现这个矩阵非常的稀疏，就是说我们存了太多不必要的数据。(太多的0了)由于每个文档大约有 1000 字，我们的矩阵不会有超过十亿的1，也就是说大概 99.8% 的值都是0。显然只存储那些1是一个更好的做法。

我们以 inverted index 的概念为中心，有时也被称作 inverted file,现在这已经是 IR 领域里的一个术语了。主要概念可以参考下图。 我们把一系列图左边的单词统称为 dictionary，对于每一个单词，我们都有一个列表，纪录了这个单词在哪个文档种出现过。(有时候也会纪录在文档中出现的位置)，把这样的纪录称为 posting。这样的一个列表就称为是 postings list，所有的这些 postings list 就称为是 postings。你会发现图上的单词已经按字母序排序好了，并且文档的 ID 也按照数字大小排好序了，之后我们会解释为什么要这样做。