在信息大爆炸的今天，有了搜索引擎的帮助，使得我们能够快速、便捷地找到所寻求的数据。提到搜索引擎，就不得不说VSM模型（Vector Space Model，向量空间模型），说到VSM，就不得不提倒排索引。可以毫不夸张地讲，倒排索引是文本索引的基石。

1.VSM模型

VSM是IR(Information Retrieval，信息检索)模型中的一种，由于其具有简单、直观、高效的特点，所以广泛应用在搜索引擎的架构中。1998年Google就是凭借这样的一个模型开始了它的疯狂扩张之路。

首先我们了解几个基本的概念：

线性代数里面的向量（Vector）是既有大小又有方向的量，通常用有向线段表示，向量有加、减、倍数、内积、距离、模、夹角等运算。

文档（Document）：一个完整的信息单元，在搜索引擎系统里对应的就是一个个网页。

标引项（Term）：文档的基本构成单位，例如在英文中可以看作一个单词，在中文中可以看作一个词语。

查询（Query）：一个用户的输入，一般由多个Term构成。

用一句话概况搜索引擎所做的事情就是：对于用户输入的Query，找到最相似的Document返回给用户。而这正是IR模型所解决的问题。

信息检索模型是指如何对查询和文档进行表示，然后对它们进行相似度计算的框架和方法。

下面举个简单的例子：现在有两篇文章分别是“春风来了，春天的脚步近了”和“春风不度玉门关”，然后查询的是“春风”。从直观上感觉，前者和输入的查询更相关一些，因为它包含两个春，但如何把我们的直观感觉用程序来表达呢？这个时候，我们前面讲的VSM模型就派上用场了。

首先我们要确定向量的维数，这时候就需要一个字典库，涉及字典库的大小，即向量的维数。在该例中，字典为{春风,来了,春天,的,脚步,近了,不度,玉门关}，查询向量如图3-2所示。

2.VSM模型示例

将Query和Document都量化为向量以后，就可以计算用户的查询和哪个文档相似性更大了。简单的计算结果是D1和D2同Query的内积都是1。

如果分词粒度再细一些，比如用每个字来作为一个粒度，则D1中“春”的粒度是2，在检索中很容易胜出。因此分词的粒度也是会对查询结果（主要是召回率和准确率）造成影响的。

上述的例子是用一个很简单的例子来说明VSM模型的，计算文档相似度的时候也是采用最原始的内积的方法，并且只考虑了词频(TF)影响因子，而没有考虑反词频(IDF)，而现在工业界比较常用的是cos夹角法，影响因子也非常多，据传Google的影响因子超过100个。

大名鼎鼎的Lucene项目就是采用VSM模型构建的，VSM的核心公式如图3-3所示（由cos夹角法演变而来）。

3.VSM模型原理

从上面的例子不难看出，如果向量的维度(对中文来讲，这个值一般在30万到45万)变大，而且文档数量(通常都是海量的)变多，那么在文档库中计算一次相关性，开销是非常大的。倒排索引就是为了避免搜索整个历史文档库，而是直接只搜索字典就可以完成计算的方法。

倒排索引非常类似于我们前面提到的Hash结构。以下内容来自维基百科：倒排索引（英语：inverted index），也常称为反向索引、置入档案或反向档案，是一种索引方法，用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。有两种不同的倒排索引形式：

一条记录的水平倒排索引（或者倒排档案索引）包含每个引用单词的文档的列表。

一个单词的水平倒排索引（或者完全倒排索引）又包含每个单词在一个文档中的位置。

后者的形式提供了更多的兼容性（比如短语搜索），但是需要更多的时间和空间来创建。

由上面的定义可以知道，一个倒排索引包含一个字典的索引和所有词的列表。其中字典索引中包含了所有的Term词，索引后面跟的列表则保存该词的信息（出现的文档号，甚至包含在每个文档中的位置信息）。下面我们采用上面的方法举一个简单的例子来说明倒排索引。

例如，现在我们要对三篇文档建立索引(在实际应用中，文档的数量是海量的)：

文档1(D1)：中国移动互联网发展迅速

文档2(D2)：移动互联网未来的潜力巨大

文档3(D3)：中华民族是个勤劳的民族

那么文档中的词典集合为：{中国，移动，互联网，发展，迅速，未来，的，潜力，巨大，中华，民族，是，个，勤劳}。

建好的索引如图3-4所示。

在上面的索引中存储了两个信息：文档号和出现的次数。建立好索引以后，我们就可以开始查询了。例如现在有一个Query是“中国移动”。首先分词得到Term集合{中国，移动}，查倒排索引，分别计算query与D1、D2、D3的距离。有没有发现，倒排表建立好以后，就不需要再检索整个文档库，而是直接从字典集合中找到“中国”和“移动”，然后遍历后面的列表直接计算。

1）左侧的索引表如何建立?怎么做才能最高效？

遇到这个问题的第一反应是：左侧的索引当然要采取hash结构，这样可以快速地定位到字典项。但是这样问题又来了，hash函数如何选取呢？而且hash是有碰撞的，但是倒排表似乎又不允许存在碰撞。事实上，在这里我们可以采用Bitmap的思想，每个词对应一个位置(当然，这里不是一个比特位)，而且是一一对应的。如何能够做到呢？一般在文字处理中有很多编码，汉字中的GBK编码基本上就可以包含所有用到的汉字，每个汉字的GBK编码是确定的，因此一个词的“ID”也就确定了，从而可以做到快速定位。注意：得到一个汉字的GBK号是非常快的过程，可以理解为O(1)的时间复杂度。

2）如何快速添加、删除或更新索引？

有经验的程序员都知道，一般在系统的“做加法”的代价比“做减法”的代价要低很多，这是因为做减法往往牵扯到原数据结构的重新组织，在搜索引擎中也不例外。因此，在倒排表中，遇到要删除一个文档，其实不是真正的删除，而是将其标记删除。这样一个减法操作的代价就比较小了。

3）如何存储海量文档呢？有没有什么备份策略呢？

当然，一台机器是存储不下的，采取分布式存储的方式。一般的备份保存3份就足够了。