在深度學習蓬勃發展的今天，一切物體皆可變成向量。圖片可以變成一個向量，一個人的興趣也可以表示成一個向量，一段語音也可以編碼成一個向量。既然一切皆可成為向量，那麼，透過一個東西找到相似的東西這個問題，都可以轉化為透過一個向量找到相似的向量的問題了。
書的二維向量化表示（因為是二維，所以可以展示到一張圖上）
所以，向量近似最近鄰（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原理圖（先看一下，不用懂）
上面這張圖先看一眼。但看不懂也沒關係。下面有詳細解釋。
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，還有很多其他演算法。後面有空也會寫寫。
