《信息检索》翻译版

首页 -> 1.1 信息检索问题的一个例子

许多人都拥有一本厚书《莎士比亚作品集》。假设你想知道莎士比亚的哪一个剧作包含了词Brutus和Caesar，但是没有Calpurnia。一种做法是从头开始通读整本书，注意每一个剧作是否包含了Brutus和Caesar并把那些包含了Calpurnia的剧作排除在外。文档检索的最简单形式就是让计算机对这些文档进行线性扫描。用来执行这种操作的Unix命令grep产生后，这种操作通常指的就是对文本进行grep操作。考虑到现代计算机的速度，Grep操作可以算一个非常高效的操作，而且一般可以支持对用户正则表达式的匹配查找。对于现代计算机，对适当尺寸文档集合（《莎士比亚作品集》的总尺寸按文本计算大概是100万单词以上。）进行简单查询，确实不需要做什么其他的。

但是对于更广泛的需求，你需要做得更多：

1. 为了更快地处理大文档集。在线数据总量的增长和计算机处理速度的增长一样块，我们现在需要能搜索十亿文档到万亿文档集的能力。
2. 为了更灵活的匹配模式。例如，用grep来查询单词countrymen附近的单词Romans是无法实现的，这里说的附近的意思是“5个单词以内”或者“在同一个句子里”。
3. 为了带有排名的检索。在很多情况下，你想得到包含特定单词的许多文档中，符合信息需求的最佳答案。

避免每个查询都对文本进行现行扫描的方法是预先对文档集进行索引。让我们继续关注《莎士比亚作品集》，用它来介绍布尔检索模型的基础知识。假设我们按照下面的格式记录下每个文档 - 莎士比亚的剧作 - 是否包含莎士比亚用过的所有单词中的每个单词（莎士比亚用了大约3200个不同的单词）。结果就是一个二进制的词-文档矩阵，如表1.1。词是被索引的单元（2.2节更详细的讨论）；它们通常是单词，但是信息检索的书籍通常把它们叫做词，因为它们中的一些，比如I-9或者Hong Kong通常不算作单词。现在依据我们查看矩阵行还是列，我们拥有了每个词的一个向量，展现它们出现在哪些文档，或者每个文档的一个向量，展现它里面出现了什么词。


表1.1 词-文档关联矩阵。矩阵元素（t,d）当位于列D的剧作包含位于行t的时候值为1，反之为0。
────────

要回答查询“包含Brutus和Caesar，且不包含Calpurnia”，我们取得Brutus, Caesar和Calpurnia的向量，用0补足空位，然后做一个位与操作：


那么查询的答案就是《Anthony and Cleopatra》和《Hamlet》（表1.2）。

布尔检索模型就是可以把任何布尔表达式形式的查询，表示为词以及操作符AND，OR和NOT的组合的一种信息检索模型。这样的查询高效地把每个文档看成一组单词。

现在让我们考虑一个更真实的场景，同时利用这个机会来介绍一些术语和表示方法。假设我们有N=100万个文档。文档的意思就是用来我们构建检索系统的单位。它们可能是独立的备忘录或者一本书的一个章节（2.1.2节有更进一步的讨论）。我们把进行检索的一组文档叫做一个（文档）集。或者有时叫做一个语料库。假设每个文档大概有1000个单词（2-3页）。如果我们假定包括空格和标点在内，每个单词平均占6个字节，那么文档集大概是6GB。通常，这些文档中可能有大概M=50万个不同的词。我们选择的数目没有任何特殊性，它们的大小是可以变化的，但是它们给了我们需要处理的问题规模的一些概念。我们将在5.1节对这些尺寸的设想进行讨论和建模。

我们的目标是开发一个系统讨论专门的检索任务。这是最常见的标准IR任务。其中，系统的目标是提供数据集中与用户信息需求相关的文档，跟系统通讯的方式是一次性的用户触发的查询。信息需求是用户想了解的主题，不同于查询，查询是用户传递给计算机的要求满足信息需求的意图。如果从用户的角度来看，一个文档包含了针对他们信息需求有价值的信息，那么这个文档就是相关的。前面我们的例子中，信息需求定义为具体的单词构成的词多少有点太理想化，反之通常用户感兴趣的主题例如“pipeline leaks”（管道泄露），希望找到相关的文档，无论它们是精确地使用了这些单词，还是用其他单词来表达这个概念，例如“pipelinerupture”（管道爆裂）。要了解IR系统的效率（搜索结果的质量等），用户通常希望知道系统返回的查询结果的两个关键的统计数值：

准确率：返回结果与信息需求的相关性有多大？
查全率（重现率）：数据集中相关的文档有多少被系统返回了？

相关的细节讨论以及准确率和查全率的统计方法可以在第8章找到。

现在我们不能直接构建一个词-文档矩阵了。一个500K×1M的矩阵就是半T（5000亿）的0或者1，这对计算机的内存来说太大了。但是很重要的观察结果是这个矩阵非常的稀疏，其中只有很少的非0项。因为每个文档有1000个单词，矩阵最多有10亿左右的1，也就是将近99.8%的项是0。更好的表现方式是只记录发生的事儿，也就是值为1的位置。

这是信息检索第一个主要概念的核心，反向索引。这个名字实际有点多余：索引总是从词映射回它们在文档出现的位置。不过，反向索引，或者有时候叫做反向文件，还是成了信息检索的标准术语。表1.3展示了反向索引的基本概念。我们保存了一个词的字典（或者叫词汇，或者辞典；本书中，我们用字典表示这种数据结构，用词汇表示词的结合）。然后对于每个词，我们有一个记录它在哪个文档出现过的列表。列表中的每一个项目──记录了词在文档中出现了（而且，后面通常包含了词出现在文档中的位置）── 通常叫做记录。表1.3中的字典已经按照字母顺序排序过，而且每个记录列表也按照文档ID排序过。1.3节中，我们将看到这种做法的好处，后面（7.15节）我们将讨论这种做法面临的取舍。