自制搜索引擎——1-6　使用倒排索引进行检索

前面我们已经了解了由索引管理器管理的倒排索引的结构以及具体的实现方法。下面，就让我们再来了解一下在索引检索器上使用倒排索引进行检索的方法吧。 布尔检索 在1-2 节，我们提到了如何从倒排索引中查找出同时包含多个单词的文档，即先获取与各单词相对应的倒排列表，然后用AND 运算符计算出其中包含的文档编号的交集。 使用由多个单词通过逻辑运算符连接而成的查询进行检索，称为“布尔检索”（Boolean Retrieval）。逻辑运算符（Boolean Operator）有AND、OR、NOT 等，其含义分别如下所示。 AND：两边的单词都要包含（逻辑与） OR：包含任意一边的单词即可（逻辑或） NOT：不包含某个单词（逻辑非） 另外，我们通常将“如何进行检索”这样的机制称为检索模型，因此执行布尔检索的检索模型就叫作布尔模型。 使用倒排索引的检索处理流程 一般来说，使用倒排索引的检索处理流程如下所示。 ① 获取查询中每个单词的倒排列表 ② 根据布尔检索，获取符合检索条件的文档编号 ③ ' 计算符合检索条件的文档和查询的匹配度 ③ " 获取对检索结果进行排序时使用的属性值 ④ 根据匹配度或用于排序的属性值，获取前k 个文档 另外，虽然在第①步中使用了“每个单词”这一表述，但是要说得严谨一些的话， 应该是处理由单词或字符连接而成的每个短语（Phrase）。虽然在此后的讲解中还是使用“单词”这一表述，但是请诸位根据实际情况进行解读。 代码清单1-1 中列出了上述流程的伪代码。 代码清单1-1　使用倒排索引的检索处理 假设在这段伪代码中，我们处理的是由各单词通过AND 连接而成的布尔查询（单词 1 AND 单词 2 AND … 单词 N）。 首先，根据各自倒排列表长度的升序，对查询中的单词进行排序。之所以这样做是为了在对多个倒排列表两两计算交集的时候，尽可能地减少比较的次数。 接下来，从查询中取出最前面的单词，获取与之对应的（最短的）倒排列表（①）。 然后，依次计算该倒排列表与查询中剩余单词的倒排列表的交集，最终生成包含全部单词的倒 排列表（②）。接下来，计算刚生成的倒排列表中的各文档与查询的关联度。此时，若还需要根据日期等属性值而非关联度对检索结果进行排序的话，则还需要从每个文档中获取相应的属性值（③）。 最后，在按照关联度和属性值对检索结果进行排序后，取出检索结果中的前k 个文档（④）①。在取出结果的时候，能将所有结果都提供给用户固然好，然而当结果数量过多时，通常只提供根据某种标准选出的“优质结果”。 另外，若查询是由短语构成的，则还需要在第❶步进行查找短语的处理，具体的方法我们在1-3 节中介绍过。由于篇幅有限，此处仅仅列出了有关AND 查询的伪代码，对于其他的布尔操作符，也可以用与此大致相同的流程进行处理。 －－－——————— A　若无需对整个检索结果排序，而是仅对前k 条结果排序即可的话，可以利用堆结构进行高速排序。 —————————— 关联度的计算方法 在Web 搜索引擎中，一般是按照文档与查询的关联度对检索结果进行排序的。计算关联度的方法有余弦相似度（Cosine Similarity）和Okapi BM25 等。 在计算余弦相似度时，需要把文档和查询映射到以单词（Term）为维度的向量空间上，文档向量和查询向量的夹角（内积）越小，说明文档和查询的关联度越高。 而Okapi BM25 则是基于“文档是否匹配查询是由概率决定的”这一统计原理，根据单词的出现频率等因素计算出查询与文档相关联的概率，这个概率越大，说明文档和查询的关联度越高。 关于这些方法就先简单介绍到这里，有兴趣的读者可以参照书后的参考文献2、3。 信息检索中的检索 在被称为信息检索的全文搜索学术领域中，由于其原本的目的就是找出与信息需求相匹配的文档，因此可以认为匹配的文档中没有必要包含查询。也就是说，在检索处理中，文档是否包含查询无关紧要，重要的是通过计算查询和整个文档的关联度，把关联度高的文档作为检索结果。 代码清单1-2 中列出了将余弦相似度作为关联度的指标来进行检索处理的伪代码。 代码清单1-2　检索时只考量了文档和查询的关联度 在该方法中，因为要计算的是所有文档和查询的关联度，所以作为检索对象的文档越多，检索处理的成本就越高。 与此相对，若是先将检索对象限定为至少包含1 个查询中的单词的文档，再计算关联度的话，就可以降低检索处理的成本了。这种情况下的检索处理伪代码如代码清单1-3 所示。 代码清单1-3　检索时考量了至少包含查询中1 个单词的文档和查询的关联度 由此可见，在搜索引擎中各种各样的方法都可用于检索处理。而搜索引擎的开发者则需要根据作为检索对象的文档的性质和检索应用程序的用途，适当地选择这些方法。