深入拆解'搜索引擎'实现原理三：搜索索引

通过上一篇文章我们了解了‘‘搜索引擎’’是如何创建索引的。

于是通过索引便可以实现快速匹配搜索的内容。

拿百度为例，我们试着搜索'微信公众平台'：

可以看到匹配结果数高达1000000000个，虽然匹配数量惊人，但百度很智能的将相关度最高的微信公众平台官网排到了首位。

那么这种按照相关度排序是如何实现的呢？

带着这个问题我们来拆解‘搜索引擎’的最后一环：搜索索引

01

关系判断

既然需要排序，那势必要分析这些匹配结果的关系，经过互相比较之后给出相关度的打分，然后得到排序结果。

但如何分析文档之间的关系呢？

我们先看两个简单的例子：

分析人与人之间的关系

首先 看一个人，往往有很多要素 ，如性格，信仰，爱好，衣着，高矮，胖瘦等等。

其次 对于人与人之间的关系，不同的要素重要性不同 ，性格，信仰，爱好可能重要些，衣着，高矮，胖瘦可能就不那么重要了，所以具有相同或相似性格，信仰，爱好的人比较容易成为好的朋友，然而衣着，高矮，胖瘦不同的人，也可以成为好的朋友。

因而判断人与人之间的关系，首先要找出哪些要素对人与人之间的关系最重要 ，比如性格，信仰，爱好。

其次要判断两个人的这些要素之间的关系 ，比如一个人性格开朗，另一个人性格外向，一个人信仰佛教，另一个信仰上帝，一个人爱好打篮球，另一个爱好踢足球。

我们发现，两个人在性格方面都很积极，信仰方面都很善良，爱好方面都爱运动，因而两个人关系应该会很好。

我们再来看看公司之间的关系吧

首先 看一个公司，有很多人组成，如总经理，经理，首席技术官，普通员工，保安，门卫等。

其次对于公司与公司之间的关系，不同的人重要性不同 ，总经理，经理，首席技术官可能更重要一些，普通员工，保安，门卫可能较不重要一点。

所以如果两个公司总经理，经理，首席技术官之间关系比较好，两个公司容易有比较好的关系。

然而一位普通员工就算与另一家公司的一位普通员工有血海深仇，怕也难影响两个公司之间的关系。

因而判断公司与公司之间的关系，首先要找出哪些人对公司与公司之间的关系最重要 ，比如总经理，经理，首席技术官。

其次要判断这些人之间的关系 ，比如两家公司的总经理曾经是同学，经理是老乡，首席技术官曾是创业伙伴。

我们发现，两家公司无论总经理，经理，首席技术官，关系都很好，因而两家公司关系应该会很好。

通过这两个例子我们可以提取出判断'关系'的两个要点：

1. 提取影响关系的关键属性
2. 判断关键属性的相关度

这两个要点就构成了我们判断文档关系的思路：

1. 计算权重（提取影响关系的关键属性）

• 找出词(Term) 对文档的重要性的过程称为计算词的权重(Term weight) 的过程。
• 词的权重(Term weight)表示此词(Term)在此文档中的重要程度，越重要的词(Term)有越大的权重(Term weight)，因而在计算文档之间的相关性中将发挥更大的作用。

2. 向量空间模型算法（判断关键属性的相关度）

02

计算权重

权重需要从两个维度判断：

• 该词汇在文档中出现的频次，频次越高，说明越重要。
• 有多少文档包含该词汇，文档数越多，说明越不重要。

我们打个比方，像'搜索'这个词汇，在本文中出现的频率很高，满足上面的第一个维度。

反观另一个词汇‘‘我们’’在本文出现的频率依然很高，一样满足第一个维度，但它同样重要吗？

这就要看第二个维度，‘我们’这个词汇有太多文档包含，所以权重并不高，不构成影响文档关系的重要词汇。

道理明白了，我们来看看公式：

这仅仅只term weight计算公式的简单典型实现。实现全文检索系统的人会有自己的实现，Lucene就与此稍有不同。

03

向量空间模型算法

在得到了文档中不同词汇的权重之后，我们需要将得到的数据生成向量空间模型，用来做相关度比较。

把所有此文档中词(term)的权重(term weight) 看作一个向量：

Document = {term1, term2, …… ,term N}

Document Vector = {weight1, weight2, …… ,weight N}

同样我们把搜索语句看作一个简单的文档，也用向量来表示：

Query = {term1, term 2, …… , term N}

Query Vector = {weight1, weight2, …… , weight N}

我们把所有搜索出的文档向量及搜索向量放到一个N维空间中，每个词(term)是一维。

两个向量之间的夹角越小，相关性越大。

所以我们计算夹角的余弦值作为相关性的打分，夹角越小，余弦值越大，打分越高，相关性越大。

有人可能会问，搜索语句一般是很短的，包含的词(Term)是很少的，因而查询向量的维数很小，而文档很长，包含词(Term)很多，文档向量维数很大。

你的图中两者维数怎么都是N呢？

在这里，既然要放到相同的向量空间，自然维数是相同的，不同时，取二者的并集，如果不含某个词(Term)时，则权重(Term Weight)为0。