《大规模元搜索引擎技》——1.2　文本检索概述

本节书摘来自华章出版社《大规模元搜索引擎技》一书中的第1章，第1.2节，作者 ［美］孟卫一(Weiyi Meng)， 纽约州立大学， 宾汉姆顿分校於德（Clement T.Yu），伊利诺伊大学芝加哥分校，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.2　文本检索概述

对于给定的查询，文本（信息）检索解决从文本文档的集合中查找相关（有用）文档的问题。文本检索技术对Web搜索引擎有深刻而直接的影响。事实上，第一代搜索引擎（约1995—1997）几乎是完全基于传统文本检索技术构建的，其中Web页面被视为文本文档。在本节中，我们简要概述经典文本检索中的一些基本概念。此概述主要基于向量空间模型（vector space model），其中文档和用户查询均表示为具有权重的词向量［Salton and McGill，1983］。想更多了解这个主题的读者请参考相关教材，如［Salton and McGill，1983］、［Frakes and Baeza-Yates，1992］、［Manning et al.,2008］和［Croft et al.，2009］。

1.2.1　系统体系结构

一个基本的文本检索系统的体系结构如图1-1所示。文本检索系统的文档集合中的文档经过预处理，以便识别那些表示每个文档的词，收集关于这些词的某些统计数据并且以特定格式组织信息（即图1-1的索引），使其易于快速计算每个文档和任一查询的相似度。
当收到用户查询时，首先文本检索系统识别表示查询的那些词，然后计算这些词的权重，这些权重反映了表达查询内容的词的重要性。于是，系统使用预先构建的索引计算查询和文档的相似度，并按相似度对文档降序排列。关于这些概念和操作的更多细节将在下面的几个小节中介绍。

1.2.2　文档表示

一个文档的内容可以使用该文档中的一些单词（word）表示。有些单词如“a”“of”和“is”不包含主题的内容信息。这些单词称为停用词（stop word），往往不使用。同一个单词（word）的变体可被映射到同一词（term）。例如，单词“compute”“computing”和“computation”能够用词“comput”表示。此操作可以通过词干处理程序（stemming program）来完成。词干处理程序删除词的后缀或用其他字符替换后缀。删除停用词和处理词干之后，每个文档可以在逻辑上表示为一个含有n个词的向量［Baeza-Yates，Ribeiro-Neto，1999］，其中n是文档集合中全部文档所含不同词的总数。应该注意的是，不同的文本检索系统常常使用不同的停用词表和词干处理算法。目前很多搜索引擎并不删除停用词。此外，一个词（term）并不意味着一个单词（word），它可以是一个词组（phrase）。
假设文档d表示为向量(d1，…,di，…,dn)，其中di是一个数值（称为权重，weight），描述第i个词在表示该文档内容时的重要性。若一个词不出现在d中，则其权重为零。当一个词出现在d中时，其权重的计算通常基于两个因素，即词频（term frequency，tf）因素和文档频率（document frequency，df）因素。一个文档中的一个词的tf表示在此文档中这个词的出现次数。直觉上，一个词的tf越高，该词越重要。因此，一个文档中的一个词的词频权重（term frequency weight，tfw）通常是这个词tf的单调增加函数。一个词的df是整个文档集合中包含这个词的文档的个数。通常，一个词的df越高，在区分不同文档时其重要性越低。这样，一个词关于df的权重通常是df的单调减少函数，所以称为逆文档频率权重（inverse document frequency weight，idfw）。一个词在某个文档中的权重是它的词频权重和逆文档频率权重的乘积，即tfw×idfw。文档中词的权重也可能受其他因素影响，如它出现在文档中的位置。例如，如果这个词出现在文档的标题中，权重可能会增加。
文本检索的典型查询也是文本。所以，同样，它可以视为一个文档，也可使用上述方法转换为一个n维向量。

1.2.3　文档查询匹配

当所有文档和一个查询都表示为相同维数的向量之后，就可以使用一个相似度函数来计算这个查询向量和每个文档向量之间的相似度。若文档对应的向量与查询向量有很高的相似度，则那些文档就会被检索。用q=(q1，…,qn)和d=(d1，…，dn)分别表示一个查询向量和一个文档向量。

一个简单的相似度函数是如下的点乘（内积）函数：
dot(q,d)=∑ni=1qidi(1-1)
当文档与查询有更多相同的重要词时，这个函数赋予文档更高的相似度。但这个简单的相似度函数存在一个问题——它偏向较长的文档，因为这些文档更有可能包含查询中的词。解决该问题的一种通用方法是用内积函数除以这两个向量（即文档向量和查询向量）长度的乘积。新的相似度函数就是众所熟知的余弦函数（cosine function）［Salton and McGill，1983］：
cos(q,d)=∑ni=1qidi∑ni=1q2i∑ni=1d2i(1-2)

两个向量的余弦函数有一个几何解释——它是两个向量之间夹角的余弦值。换句话说，余弦函数度量了查询向量和文档向量之间的角距离。当两个向量都有非负权重时，余弦函数总是返回一个属于［0,1］区间的值。当查询和文档不共享词（即当这两个向量的夹角是900）时，其值为0；当查询向量和文档向量相同或一个向量是另一个的正值常数倍时（即当角度为00），其值为1。
还有其他的一些相似度函数，其中某些函数还考虑那些查询词在文档中的邻近度。这些查询词在文档中出现的位置越接近，文档越可能具有查询本身的含义，因而查询和文档之间的相似性就应该更高。为支持基于邻近度的匹配，对于任何给定的一个文档和一个词，这个词在该文档的所有位置需要被收集并存储起来成为搜索索引的一部分。
还有其他几个文本检索模型。在基本的布尔检索模型（Boolean retrieval model）中，文档检索基于它们是否包含查询词，而不考虑词的权重。一个布尔查询可以包含一个或多个布尔算符（AND、OR和NOT）。在概率模型（probabilistic model）中［Robertson and Sparck Jones，1976；Yu and Salton，1976］，对文档的排序是按照文档相关于查询的概率降序排列。基于查询词在相关和不相关文档的分布，进行概率估计。基于概率模型最广泛使用的相似度函数是Okapi函数［Robertson and Walker，1999］。近年来，语言模型也成功地应用于信息检索［Ponte and Croft，1998；Zhai and Lafferty，2004］。在这种方法中，对于一个给定的查询，根据估计的每个文档生成该查询的概率，将文档按概率降序排序。也存在一些其他语言模型［Croft et al.，2009］。

1.2.4　查询处理

直接计算一个查询和每个文档之间的相似度是低效的，因为大多数文档与给定查询之间没有任何共同词，计算这些文档的相似度是资源浪费。为提高计算效率，我们预先创建一个倒排文件索引（inverted file index）。对于每个词ti，生成并存储一个有表头的倒排表（inverted index），形式为I(ti)=［(Di1,wi1i)，…，(Dik,wiki)］，其中Dij是包含ti的文档标识符，wiji是Dij中ti的权重(1≤j≤k)，k是包含ti的文档个数。此外，散列表(一个类似于表的数据结构)可以用来把每个查询词映射到该词倒排表的表头。利用倒排文件和散列表，对于与任何查询有非零相似度的所有文档可以实现高效的相似度计算。具体来说，考虑一个有m个词的查询。对于每个查询词，可用散列表查找这个词的倒排表的地址。这m个倒排表包含了计算该查询与含有至少一个查询词的所有文档之间的相似度所需的全部必要信息。
一种广泛使用的查询处理策略是每次一文档策略（document-at-a-time strategy）［Turtle and Flood，1995］，也就是说，每次计算一个文档的相似度，而只有那些包含至少一个查询词的文档才予以考虑。这种策略的基本思想如下。在许多文本检索系统中，倒排文件太大不能存储在内存中，因而存储在磁盘上。如果倒排文件存储在磁盘上，那么当开始处理一个查询时，需要首先把此查询的所有词的倒排表调入内存。然后计算至少包含一个查询词的那些文档的相似度，一次一个文档。假设一个查询有m个词。每个词对应一个倒排表，包含这个词的文档的标识符在倒排表中按升序排列。如下面的例1.1所示，可使用倒排表进行m路合并方法计算相似度。由于同步扫描m个倒排表，所以对于查询处理，扫描每个查询词的倒排表一次即可。

例1.1　图1-2显示了一个文档-词矩阵（document-term matrix）的示例，文档集合包含5个文档和5个不同的词。为简单起见，权重用了原始词频，内积函数将用于计算相似度。

从图1-2中的矩阵，可以得到如下倒排文件表：
I(t1)=［(D1，2)，(D3，1)，(D4，2)］

I(t2)=［(D1，1)，(D2，2)，(D4，1)，(D5，2)］

I(t3)=［(D1，1)，(D2，1)，(D3，1)，(D4，2)］

I(t4)=［(D2，1)，(D3，1)，(D4，2)，(D5，1)］

I(t5)=［(D5，2)］

设q为一个查询，包含两个词t1和t3且权重都是1（即它们每个恰好出现一次）。
现在应用每次一文档策略计算文档对于q的相似度。首先把两个查询词的倒排表取到内存。当取到
I(t1)=［(D1，2)，(D3，1)，(D4，2)］和I(t3)=［(D1，1)，(D2，1)，(D3，1)，(D4，2)］之后，以同步方式考虑出现在倒排表中的每个文档。第一个同时出现在两个表中的文档是D1（即D1同时包含t1和t3）。文档D1关于查询的相似度可以用内积计算，权重是2（对于t1）和1（对于t3），内积dot(q，D1)=1×2+1×1=3。两个表的下一个词分别是(D3，1)和(D2，1)。因为D2■

另一个著名的查询处理策略是每次一词策略（term-at-a-time strategy）［Turtle and Flood，1995］。这种策略一个接一个地处理查询词的倒排表。当一个查询词的倒排表处理完后，这个词对文档的总体相似度（即查询与每个包含这个词的文档之间的相似度）的贡献就都被计算出来了，然后把该贡献加到已经处理过的那些查询词的贡献中。当所有查询词的倒排表全部处理之后，若一个文档包含至少一个查询词，则查询与该文档的最终相似度就被计算出来了。

例1.2　
我们用例1.1的文档和查询示例来说明每次一词策略。假设首先考虑查询词t1。我们首先得到I(t1)。因为I(t1)包含D1、D3及D4，所以当t1处理完后，得到下面的中间相似度：dot(q，D1)=1×2=2，dot(q，D3)=1×1=1，dot(q，D4)=1×2=2。对于t3，我们得到I(t3)。通过把t3的贡献加到前面得到的部分相似度，得到最终相似度：dot(q，D1)=2+1×1=3，dot(q，D2)=0+1×1=1，dot(q，D3)=1+1×1=2及dot(q，D4)=2+1×2=4。■

有许多剪枝策略可以用来减少上述两种基本策略的计算开销［Turtle and Flood，1995］。

1.2.5　检索有效性度量

用户提交一个查询，文本检索的目标是找到那些相关（relevant）于或有用（useful）于用户的文档并将其排在前面。文本检索系统的检索有效性经常使用召回率（recall）和查准率（precision）这一对数值来度量。对于一个给定的用户查询，假设文档集的相关文档集合已知,那么，召回率是检索到的相关文档比率，查准率是检索出的文档中相关文档的比率。例如，对一个查询，假设有10篇相关文档，在20个检索出的文档中有6篇相关，那么，对此查询，召回率是6/10=0.6，查准率是6/20=0.3。
为评价一个文本检索系统的有效性，经常使用一组测试查询。对于每个查询，提前确定相关文档的集合。对每个测试查询，对每个不同的召回率得到一个查准率。通常只考虑11个召回率值：0.0，0.1，…，1.0。对所有测试查询，每个召回率值对应的查准率的平均值计算出来之后，就可以得到平均的召回率-查准率曲线。
针对文本检索系统，还有许多其他检索有效性的度量。在搜索引擎的背景下，通常不可能知道测试查询的全部相关文档。在这种情况下，基于一定的靠前排序（top ranked）结果，可以使用一些面向查准率的度量。例如，对于某个给定的n，可以用n查准率来计算前n排序（top n ranked）结果的查准率。读者可以参阅书籍［Voorhees and Harman，2005］获得关于评估方法学和评估度量的更多信息。