倒排索引是搜索引擎的基石--VSM检索模型

　　

倒排索引是搜索引擎的基石--VSM检索模型

　　

　　简介：

　　在信息爆炸的今天，在搜索引擎的帮助下，我们可以快速方便地找到我们要找的东西。说到搜索引擎就不得不说VSM模型，说到VSM就不得不说倒排索引。可以毫不夸张地说，倒排索引是搜索引擎的基石。

　　VSM 检索模型

　　VSM的全称是Vector Space Model，是IR（Information Retrieval Information Retrieval）模型之一。由于其简单、直观、高效，被广泛应用于搜索引擎的架构中。 1998年，谷歌凭借这样的模式，开始了疯狂的扩张之路。废话不多说，我们来看看VSM是什么。

　　在开始之前，我假设大家对线性代数中的Vector有一定的了解。矢量是具有大小和方向的量。它通常用有向线段表示。向量包括：加法、减法、倍数、内积、距离、模数和角度运算。

　　文档：一个完整​​的信息单元，指的是相应搜索引擎系统中的单个网页。

　　Term：文档的基本单位。比如在英文中可以看成一个词，在中文中可以看成一个词。

　　查询：用户的输入通常由多个术语组成。

　　然后用一句话总结搜索引擎做了什么：对于用户输入的Query，找到最相似的Document，返回给用户。而这正是IR模型解决的问题：

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

　　一个简单的例子：

　　现在有两篇文章(Document)文章，分别是《春风来了，春天的脚步在逼近》和《春风未过玉门关》。然后输入查询是“春风”。从直觉上讲，前者与输入查询更相关，因为它收录两个弹簧，但这只是我们的直观感受。怎么量化，要知道电脑是严谨的学科^_^。这时候，我们前面提到的 Term 和 VSM 模型就派上用场了。

　　首先，我们需要确定向量的维度。这时候，我们需要一个字典库。字典库的大小就是向量的维度。本例中，字典为{春风，来，春，的，脚步声，近，不度，玉门关}，文档向量和查询向量如下：

　　

　　VSM 模型示例

　　PS：为了简单起见，这里的分词粒度非常大。

　　将 Query 和 Document 都量化为向量后，可以计算出用户的查询与哪个文档更相似。简单的计算结果是D1和D2与Query的内积为1，囧。当然，如果分词粒度越细，查询的结果就会不同，所以分词粒度也会影响查询结果（主要是recall和accuracy）。

　　上面的例子用一个非常简单的例子来说明VSM模型。在计算文档相似度时，也采用了最原创的内积法，只考虑词频（TF）影响因素，不考虑反向。词频（IDF），现在比较常用的是cos角法，影响因子很多，据说谷歌的影响因子多达100+。

　　著名的 Lucene 项目就是使用 VSM 模型构建的。 VSM的核心公式如下（由cos角法演化而来，这里省略推导过程）

　　

　　VSM 模型公式

　　从上面的例子不难看出，如果向量的维度（对于中文来说，这个值一般是30w-45w）变大，文档数量（通常是海量）变大，那么计算相关性一次，开销很大，这个问题怎么解决？别忘了，我们这一节的主题是倒排索引，主角终于登场了！ ！ ！

　　倒排索引

　　倒排索引与我们之前提到的Hash结构非常相似。以下内容来自维基百科：

　　倒排索引（英文：Inverted index），也常称为倒排索引、置入文件或倒排文件，是一种索引方法，用于在全文搜索下存储文档中的某个词或存储位置的映射。一组文件。它是文档检索系统中最常用的数据结构。

　　反向索引有两种不同的形式：

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

　　从上面的定义可以知道，倒排索引收录一个字典索引和一个所有单词的列表。字典索引收录了所有的Term（通常理解为文档中的单词），索引后面的列表保存了单词的信息（出现的文档编号，甚至每个文档中收录的位置信息）。下面我们也用上面的方法举一个简单的例子来说明倒排索引。

　　比如现在我们要索引三个文档（在实际应用中，文档的数量是海量的）：

　　文件1（D1)：中国移动互联网发展迅猛

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

　　文件3（D3)：中华民族是勤劳的民族

　　文档中设置的字典为：{China, mobile, internet, development, Rapid, future, of, potential,巨大, 中国, 民族, 是, 个人, 勤奋}

　　构建的索引如下图：

　　

　　倒排索引

<p>在上面的索引中，存储了两条信息，文档编号和出现次数。建立索引后，我们就可以开始查询了。例如，有一个名为“中国移动”的查询。首先分词获取Term集{China, Mobile}，检查倒排索引，分别计算query与d1、d2、d3的距离。有没有发现，倒排列表创建后，不需要搜索整个文档库，直接从字典集合中找到“中国”和“手机”，然后遍历下面的列表，直接计算。