文档高频词汇统计

到目前为止，我们已经抽象地定义了一个IR系统是如何工作的，但是我们还没有解释如何使它们更有效，以便一个Web（万维网）搜索引擎能够在十分之一秒内就从数十亿网页的集合中返回靠前的结果。对于任何一种IR系统来说，两个关键的数据结构是列出文档集合中所有词语的词典，和列出每个词语在文档集合中出现位置的倒排索引。

词典是支持下述操作的一种数据结构：给定一个词语，它能够返回该词语在倒排索引中的位置，倒排索引表存储了词语在文档中的出现次数信息。在一些系统的实现中，它也可以返回包含该词语的文档总数。词典应该是通过哈希表或者类似的允许快速查找的数据结构实现的。有时信息内容很少的一个常用词语集合会被从词典中省略。这些停用词（stop word，比如“the”、“of”、“to”、“be”、“a”等）占据了索引中的空间却不能改进结果的评分。将它们保留在词典中的唯一合理原因在于对于支持短语查询的系统而言，停用词的索引对于有效地检索类似于“to be or not to be（莎士比亚悲剧《哈姆雷特》里的名言——译者注）”这样的查询是必要的。

倒排索引[17]，类似于本书最后的索引，是由一组命中表组成的：存储每个词语出现的位置。对于布尔型关键词模型，命中表就是一个文档列表。对于一元模型，命中表则是(文档，计数)二元组的列表（计数值为该词语在对应文档中出现的次数——译者注）。为了支持短语搜索，命中表还必须包含在每篇文档中词语出现的位置。

当查询是一个单词时（根据Silverstein等人(1998)的著述，大约有26％的时间），处理过程是非常快的。我们在词典中查找一个单词并得到其在命中表中的地址，然后我们创建一个空的优先级队列。之后，我们每次搜索命中表中的一篇文档，并检查该文档对应的计数。如果优先级队列中的元素个数少于R个（R是结果集合的期望规模），我们把(文档, 计数)二元组添加到队列中。否则，如果计数比优先级队列中最低条目要高，那么我们就删除最低条目，并添加新的(文档，计数)对。因此，应答查询的时间复杂度是O(H+R logR)，其中H是命中表中的文档个数。当查询中包含n个词语时，我们不得不合并n个命中表，需要的时间为O(nH+R logR)。

我们之所以采用概率模型来表示我们有关IR的理论的总体观点，是因为该模型利用了我们在其它的主题中已经谈论过的思想。但是，实际的IR系统使用另一种不同方法的可能性更大，即向量空间模型。这种模型采用与概率模型同样的词包方法。每篇文档被表示为一元词频的向量。查询也用同样的方法表示。查询 [Bayes information retrieval model]（[贝叶斯 信息 检索 模型]）被表示为如下向量

[0, … , 1, 0, … , 1, 0, … , 1, 0, … , 1, 0, … ]

这样表示的思想是，用每一维表示文档集合中的一个词语，除了那4个出现在查询中的词语之外，其余维得到的评分都是 0。相关文档是通过寻找在向量空间中与查询向量距离最近的文档向量而进行选择的。一种对相似度的度量是查询向量和文档向量之间的点积；点积结果越大，说明两个向量越接近。从代数角度看，这样会赋予在文档和查询中都频繁出现的词较高的评分。从几何角度看，两个向量之间的点积等于这两个向量夹角的余弦值；最大化两个这样的向量之间夹角的余弦值（在同一个象限中）意味着它们之间的夹角接近于0度。

关于向量空间模型还有更多的内容。在实际中，该模型渐渐已经能够适应范围很宽的各种不同的额外特征、改进、纠错以及添加。根据向量空间中的相似度对文档进行排序的基本思想，使得在数值化的排序系统中揉入新思想成为可能。有些人认为一个统计模型会允许同样的操作按照更有原则的方式进行，但是IR研究人员不会轻易改变，除非他们能够看到其它模型有明显的性能优势。

为了对一个典型 IR 任务的索引问题的量级有一个认识，我们考虑来自 TREC（Text REtrieval Conference，文本检索会议）的一个标准文档集合，包含大约750 000篇文档共计2GB（1GB约为十亿字节）大小的文本。词典大约包含500 000个经过取词干和大小写同一处理的词语；这些词语占7到10 MB的存储空间。存储(文档, 计数)对的倒排索引占324 MB，尽管采用压缩技术可使其降到83 MB。压缩技术可以节省空间，不过以处理开销的轻微增长为代价。然而，如果压缩技术允许你把整个索引保留在内存里而不是硬盘上，那么它会带来实质的性能净增长。对短语查询的支持将索引所占空间扩大到未经压缩的1 200 MB或经过压缩的600 MB。而Web搜索引擎则在比这个规模还要大3000倍的索引上运转。虽然很多此类操作是相同的，但是由于在单台计算机上处理数以万亿字节计的数据是不可操作的，因此将索引分为k段，每段分别存储在不同的计算机上。一个查询被并行地送往所有计算机，然后k个结果集合被合并成单一结果集合显示给用户。Web搜索引擎还必须每秒钟处理上千个查询，所以它们需要这k个计算机的n个备份。而k和n的值是随时间不断增长的。