在深度学习蓬勃发展的今天，一切物体皆可变成向量。图片可以变成一个向量，一个人的兴趣也可以表示成一个向量，一段语音也可以编码成一个向量。既然一切皆可成为向量，那么，通过一个东西找到相似的东西这个问题，都可以转化为通过一个向量找到相似的向量的问题了。
所以，向量近似最近邻(ANN)算法需要解决如下的问题：
- 给定N个维度是f的向量(vector)组成集合S
- 给定一个距离函数d，其中 d(a, b) 是向量a和b的距离，距离越小表示a，b越相似
- 输入一个维度是f的向量q，如何找到S中和q距离最近的K个向量
对于这个问题，最傻瓜的算法当然是，对集合S中的N个向量，每个计算一下和q的距离，并将结果放入一个堆中（堆里维护着距离最小的K个向量）。这样，整个算法的复杂度是 O(Nlog(K))。当N很大时（比如1亿），显然查询是非常慢的。
因此，为了解决快速查找的问题，如何对集合S建立合适的索引，就是一个重要的问题了。而HNSW就是这方面的一个重要算法。关于HNSW的开源实现可以参考Github上的hnswlib。不过，因为这个库做了很多性能优化，导致它的代码可读性不是很好，不太容易看懂。因此这篇文章着重用浅显易懂的语言来介绍一下hnsw的算法。
上面这张图先看一眼。但看不懂也没关系。下面有详细解释。
HNSW的索引是由一层层图构成。level0的图包含了集合S中所有的向量（每个向量对应图里面的一个顶点），level1的顶点是level0的子集，是从level0的节点里随机采样的，level2是level1的子集，以此类推，level越高，节点越少。同时，随着level升高，每个level的节点个数指数下降。
那么，对于一个给定的level，假设我们已经知道了这个level的顶点集合（其实就是包含的向量集合）。那么，如何建立索引呢？
索引其实是一个图(Graph)。图的数据结构一般由顶点和边构成。那么HNSW的每一层的图的组成如下：
- 顶点就是这一层的所有向量
- 每个向量和与它距离最近的P个向量对应的顶点连接成边
所以，构建某一层的图，需要解决的问题就是，假设现在已经基于已有的N个向量构建了图G，来了一个新的向量，如何把这个向量对应的顶点加入到图中。而加入的过程很简单，也是2步：
- 找到图里和待加入顶点距离最近（当然这里可以是近似的）的P个顶点
- 把这个顶点加入图中，并和P个顶点连上边。
因此，问题转化为，如何从图里找到和待加入顶点v最近的P个顶点。这里采用了A*算法。可以简单描述一下它的思路如下，这里我们首先用一种直观的语言描述一下：
- 从图里随机找一个点u，算一下和v的距离。
- 看一下u的邻居里有没有比u离v还近的点，如果有，比如d(u',v) < d(u, v)，那么就看看u' 的邻居里有没有离v更近的。
- 然后就不断的看邻居，直到找不到更近的点。
然后我们再用偏程序员才能看懂的语言再描述一下
- 构建一个优先级队列Q存储顶点u以及u和v的距离d(u,v)，距离越小的排在越前面 。
- 从图里面随机找一个点u, 将 {u, d(u,v)}放入Q中
- while Q不空
- 找到Q中的头节点{u, d(u, v)}，如果已经访问过，continue
- 将{u, d(u, v)}放入返回结果L中
- 遍历u的所有邻居u'，计算它们和v的距离，并将{u', d(u', v)}放入Q
- 将L里面离v距离最近的P个点返回
这样就搞定了。细节可以看看hnswlib的代码。不过主要流程就是这个，很简单。
下面说说，为啥HNSW需要有多层的图。只有一层，不行吗？只有一层，有2个问题
- 从上面描述里可以看到，我们是从图里面一个随机的节点开始的。那么，可能要搜索很久，才能找到离我最近的P个节点。
- 如果只有level0的图，很有可能这个图是不联通的。如果一开始的随机节点在一个特殊的联通分支上，这个联通分支上所有点都离我很远，那就SB了。
因此，HNSW解决这个问题的办法很简单。
- 我们从 level 最高的层开始搜索。比如从level = T开始搜索。因为这一层节点很少，因此，从一个随机的点开始，很快能找到一个离查询节点q最近的节点，假设是v
- 那么，在level = T - 1层搜索时，就不需要从随机节点开始搜索了，而是可以从节点v开始搜索。（需要注意的是，我们前面提到了，如果i > j，那么level = i 的层的节点是 level = j 的层的节点的子集，因此v如果在第T层存在，那么在T-1层也存在）
- 以此类推，直到 level = 0 就可以快速找到最终结果了。
最后，不忘贴一下HNSW的论文原文，可以去Google自行搜索
Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
在向量最近邻的领域，除了hnsw，还有很多其他算法。后面有空也会写写。