你好，我是黄申。

上一节，我们充分利用了哈希表时间复杂度低的特点，设计了一个简单的缓存系统。在实际项目中，哈希表或者类似的哈希数据结构，有着更为广泛的运用。比如，搜索引擎中的倒排索引，也是基于哈希表结构来设计的。这种倒排索引可以大大提升数据对象的检索效率。

除了搜索的效率，搜索引擎另一个需要考虑的问题是相关性，也就是说，我们需要保证检索出来的信息是满足用户需求的。最简单的基于倒排索引的实现，属于一种布尔排序模型，它只考虑了单词是不是出现在文档之中，如果出现了就返回相应的文档，否则就不返回，对应于布尔模型中的真假值。在这种实现中，只要出现了相关搜索词的文档都会被检索出来，因此相关性比较差。对于这点，我们可以利用向量空间模型，来衡量文档和用户查询之间的相似程度，确保两者是相关的。不过，向量空间模型需要涉及两两之间的比较，时间复杂度比较高。

考虑到上述两点，今天，我们就以文档检索为例，参照倒排索引加向量空间模型的设计思路，设计一个简单的搜索引擎。

搜索引擎的设计框架

之前在讲解向量空间模型的时候，我们介绍了信息检索的基础知识，而我们平时经常使用的搜索引擎，就是一种典型的信息检索系统。在讲解如何结合倒排索引和向量空间模型之前，我们先来看，常见的文本搜索引擎都由哪些模块组成。

文本搜索系统的框架通常包括 2 个重要模块：离线的预处理和在线的查询。离线预处理也就是我们通常所说的“索引”阶段，包括数据获取、文本预处理、词典和倒排索引的构建、相关性模型的数据统计等。数据的获取和相关性模型的数据统计这两步，根据不同的应用场景，必要性和处理方式有所不同。可是，文本预处理和倒排索引构建这两个步骤，无论在何种应用场景之中都是必不可少的，所以它们是离线阶段的核心。之前我们讲过，常规的文本预处理是指针对文本进行分词、移除停用词、取词干、归一化、扩充同义词和近义词等操作。

在第 17 讲里，我讲解了如何使用倒排索引，把文档集转换为从关键词到文档的这种查找关系。有了这种“倒排”的关系，我们可以很高效地根据给定的单词，找到出现过这个单词的文档集合。

倒排索引是典型的牺牲空间来换取时间的方法。我们假设文章总数是 k，每篇文章的单词数量是 m，查询中平均的关键词数量是 l，那么倒排索引可以把时间复杂度从 O(k×logm) 降到 O(l)。但是，如果使用倒排索引，就意味着除了原始数据，我们还需要额外的存储空间来放置倒排索引。因此，如果我们的字典里，不同的词条总数为 n1n1