1.2.3 对索引进行搜索
上面我们已经可以查找到包含关键词的相关文档了，但它还不能满足实际搜索的要求。如果结果只有几个，当然没有问题，全部显示就是了。但在实际应用中，搜索引擎需要返回几十万，甚至百万、千万级的结果。我们怎样才能将最相关的文档显示在最前面呢？这也是下面需要探讨的问题。
1．用户输入查询语句
目前，搜索引擎均提供自然语言搜索以及布尔表达式高级搜索，所以查询语句也是遵循一定的语法结构。比如我们可以输入查询语句“search AND using NOT image”，它搜索包含search和using但不包含image的文档。
2．对查询语句进行词法分析、语法分析、语言处理
词法分析用来提取查询词以及布尔关键字，上面的查询语句提取出的查询词为search using image，布尔关键字是AND和NOT。语法分析会将词法分析的提取结果生成一棵语法树。上例形成的语法树如图1-5所示。
图1-5 语法树
语言处理与创建索引时的语言处理过程几乎相同。如图1-6所示，上例中的using将转换为use。
图1-6 语言处理后的语法树
3．搜索索引，返回符合上述语法树的结果
首先，在反向索引中分别找出包含search、use和image的文档链表。然后，将包含search和use的文档链表合并，得到既包含search，又包含use的文档链表。接着，在上一步的结果中去除包含image的文档链表，最终的文档链表就是符合上述语法树的结果。
4．对结果进行相关性排序
虽然在上一步中我们得到了想要查找的文档，但这些文档并未按照与查询语句的相关性进行排序，并不是我们最终想要的结果。那怎样才能将查找结果按相关性进行排序呢？首先，把查询语句也视为一个由若干词组成的短小文档，那么查询语句与相应文档的相关性问题就转变成了文档之间的相关性问题。毫无疑问，文档主题近似程度高的，其相关性必然强；文档主题近似程度低的，其相关性必然弱。那进一步思考一下，什么又是决定文档间相关性的主要因素？想必读者都读过或写过论文，是否留意到每篇论文都有“关键词”这一项？“关键词”是能够反映论文主题的词或词组。也就是说，论文中每个词对论文主题思想的表达程度是不相同的。换个说法，文档中的每个词对其主题思想表达的权重是不同的，正是这些不同权重的词构成了文档的主题。
有两个主要因素会影响一个词在文档中的重要性。一是词频率（Term Frequency，tf），表示一个词在此文档中出现的次数，它的值越大，说明这个词越重要。二是文档频率（Document Frequency，df），表示多少文档中包含这个词，它的值越大，说明这个词越不重要。一个词的权重可以使用式（1-1）进行计算：
（1-1）
在上述公式中，Wt,d表示词t在文档d中的权重，tft,d表示词t在文档d中出现的频率，n表示文档的总数，dft表示包含词t的文档数量。
怎样才能度量文档的相似度呢？第一步，把文档中每个词的权重组成一个向量，DocumentVector={weight1, weight2, …, weightN}。把查询语句也看作一个简单的文档，将其中的每个词的权重也组成一个向量，QueryVector={weight1, weight2, …, weightN}。第二步，将所有查询出的文档向量和查询语句向量取并集，用并集元素的个数N统一各向量长度，如果一个文档中不包含某个词，那么该词的权重为0。第三步，把所有统一后的向量放到一个N维空间中，每个词是一维，如图1-7所示。
图1-7 N维向量空间（3维）
如图1-8所示，文件向量间存在一定的夹角。我们可以通过计算夹角余弦值的方法来表示它们之间的相似程度。因为夹角越小，余弦值越大，也就是说文档向量夹角的余弦值越接近，文档也越相近。
图1-8 向量夹角
相关性的计算公式如下：
（1-2）
下面梳理一下上述的索引、搜索过程，如图1-9所示。
图1-9 索引、搜索过程
词法分析和语言处理过程将一系列文本转化为若干个词，然后索引创建过程将这些词生成词典和倒排索引，索引写程序将其写入索引库。当用户输入查询语句进行搜索时，首先进行词法分析和语言处理，将查询语句分解成一系列词，而后将其输入语法分析过程生成查询语法树。索引读程序将反向索引表由索引库读入内存，搜索过程在反向索引表中查找与查询语法树中每个词一致的文档链表，并对其进行相应的布尔运算，得到结果文档集。将结果文档集与查询语句的相关性进行排序，并将生成结果返回给用户。