大家好，我是Jack Bytes，一个专注于将人工智能应用于日常生活的程序猿，平时主要分享AI、NAS、开源项目等。

把你关在一个空无一人的房间里，只有一台电脑，你该如何了解世界上发生的事情？

可以直接躺在地上睡觉，或者，在电脑上使用搜索引擎来获取信息。

当你欢快的通过搜索引擎进行信息获取的同时，你有没有想过搜索引擎的工作原理是什么？它是如何能够在秒级、甚至毫秒级内给你返回最相关的结果？

互联网上的数据是海量的，多达上百亿。当用户输入一个查询词之后，如果把查询词一个一个和互联网上的网页进行计算，那得计算上百亿次，如果每次计算1毫秒，一共100亿个网页，那么得10000000秒，也就是115.74天才能计算完成。

不过目前主流的搜索引擎显然不是这样的，他们基本上能够在我们眨眼的功夫就返回结果，那么它是怎么做的呢？

一、爬虫技术

所谓爬虫，并不是真的虫子，而是一个不停在互联网获取网页内容的应用程序。

简单的爬虫维护两个结构，已访问结果和待访问队列。

爬虫递归的获取网页中的链接，判断这个链接先前是否访问过，如果访问过则跳过，否则将其加入待访问队列。

爬虫不停的从待访问队列中取出URL链接，获取其网页内容，加入到网页库中，同时把该链接放入到已访问集合中。

当你在互联网发布了一篇文章，不就之后，爬虫就能够检测到这个网页，并将网页放入到它的网页库种，方便后续构建索引。

当累计了必定的数据量之后，就会触发索引构建，目前常见的索引有两种：1. 倒排索引，2. 向量索引，下面来分别介绍一下这两种方式。

二、倒排索引

假设目前网页库种有4个网页，在不构建索引的情况下，当用户的查询词来了之后，最直接的方式就是计算查询词和这4个网页相关性，列如统计查询词在网页中的词频、位置等等。

不过，如果网页数量变得许多，这种方式就超级低效了。于是，机智的人类提出了倒排索引这样的结构。

假设这四个网页的ID分别是0、1、2、3，每个页面都有如下表格中所示的关键词：

网页ID	关键词
0	夏天、西瓜
1	西瓜、雪糕
2	夏天、游泳
3	游泳、书包

为了能够快速根据关键词找到和关键词相关的网页，我们需要把上面的结构做个变换，如下所示：

关键词	网页ID
夏天	0、2
西瓜	0、1
雪糕	1
游泳	2、3
书包	3

如果用户的查询词包含了「夏天」，我们可以很快的找到网页0和网页2。

同样的，如果用户的查询词同时包含了「夏天」、「西瓜」，我们可以快速找到网页0。

这样的结构就是倒排索引。

三、向量检索

倒排索引可以精准的命中关键词，不过却不具备语义相关的信息。举个例子：

如果用户的查询词是「冰激淋」，那么对于上面的倒排索引，将会返回空结果，由于其中只有夏天、西瓜、雪糕、游泳、书包这几个关键词，没有「冰激淋」这个关键词。

那么我们应该怎么做才能让用户即使输入了索引中不存在关键词，也能有相关的结果返回呢？

小学二年级的时候我们学过，特征向量能够在高维空间描述一个物体。

到了小学三年级，我们就知道了，能够通过模型将文本转换为向量，这样的话就能够在高维空间描述两个文本的类似性。

还是举个简单的例子：

「雪糕」的特征有：冰、遇热会融化、放在冰箱中、有根棍

「冰激淋」的特征有：冰、遇热会融化、放在冰箱中、有尖尖的脆皮筒

可以看到，雪糕和冰激淋虽然字面上不一样，但是包含了许多类似的特征，应该被归为同一类。

模型通过大量数据的训练，可以学习到海量词之间的特征。

简单的，我们可以把使用模型把上面的网页0、1、2、3转化为向量，如下所示（图中向量值仅供参考，无实际含义）：

网页ID	关键词	向量
0	夏天、西瓜	[1,1,0,0,0]
1	西瓜、雪糕	[0,1,2,3,4]
2	夏天、游泳	[1,2,2,2,3]
3	游泳、书包	[2,3,1,4,5]

然后我们把向量构建成向量索引，最简单的就是暴力索引，也就是用户查询请求来了之后，和所有的向量都计算一遍类似度，然后返回最类似的向量。

在向量规模比较小的时候，可以这么做，并且召回率也是100%。但是，让向量规模很大，如几千万，暴力检索的效率会超级低。

小学四年级，我们学过了可以通过哈希、图等方式对向量进行划分，从而降低计算的向量数量。比较有名、效果比较好的是HNSW图索引，结构如下：

具体的HNSW原理由于篇幅太多，这里不再赘述，大家可以在网上查阅相关资料或者看我往期的文章。

简单来说就是把向量集合分层，其中最下层包含所有的向量，层数越往上，向量数越少，上层可以作为下层的导航层。

当用户输入了一个查询词之后，模型第一把查询词转换为向量，然后从上图的最顶层开始，每次在当前层计算和用户查询向量最类似的向量，作为下一层的入口，以此类推，直到到达最底层，这样在最底层只需要计算有限次的向量，就可以找到类似的结果了。

我们把最类似的向量关联的网页ID返回给用户即可。

四、在线查询

搜索引擎是一个极其复杂的系统，为了方便大家理解，我对其做了简化，利用我们上面讲的内容，绘制了下图：

抛开构建索引的过程，对于在线查询来说，当用户在搜索引擎入口输入查询词之后，会依次经历如下阶段：1.召回，2.粗排，3.精排，4.渲染，并返回给用户。

其中：

召回阶段会从海量网页中通过倒排索引和向量索引获取到相关的几千条结果。

粗排阶段会根据特征对这几千条结果进行初步的排序，并返回几百条或者几十条结果。

精排阶段会使用更加复杂的模型对粗排阶段返回的结果重新计算特征，重新排序。

最终，将这些精排的结果进行渲染并返回给用户。

当然，在返回给用户之前，会做一些其他的处理，如插入广告等等。

好了，大家学废了嘛～

我是Jack Bytes

一个专注于将人工智能应用于日常生活的半吊子程序猿！

平时主要分享AI、NAS、Docker、搞机技巧、开源项目等技术，喜爱的话请关注吧！