simhash 實現原理

前言

衆所周知，目前微信公衆號是最具商業價值的寫作平臺，這與它優秀的原創保護機制密不可分，如果你想將其他公衆號上的文章標爲原創，微信會給出類似如下的信息告訴你未通過原創校驗邏輯。

如果你抓包會發現微信返回瞭如下錯誤

如果你想改幾個字矇混過關，對不起，不行！依然會報上述錯誤，這得益於微信原創檢測機制所採用的 simhash 技術，它是 Google 爲了解決大規模的網頁去重而發明的算法，廣泛用在大規模的文章，評論判重等地方，效率極高，那麼這項技術是如何實現的呢，通過上面的錯誤信息不難發現微信是爲每篇文章生成了一個指紋（fingerprint），最終文章相似性的比較其實是指紋的比較，那麼這個指紋又是如何生成的呢，本文將會爲你由淺入深地揭曉 simhash 的祕密。

本文的目錄結構如下：

• 傳統 Hash 與其侷限性
• 餘弦定理實現及其侷限性
• 基於隨機投影來實現空間向量的降維
• simhash 原理及實現

傳統 Hash 與其侷限性

如何比較兩篇文章是否相同，相信大家不難想到以下步驟

1. 通過一個 Hash 函數（MD5 等）將文章轉成定長字符串，比如 32 位
2. 比較上一步生成的定長字符串是否相等

第一步的主要作用是將大範圍映射到小範圍，這樣使用小範圍的定長字符串「一般我們把它稱爲指紋（fingerprint）」大大縮小了空間，更利於保存，並且更利於比較，但對於計算兩篇文章的相似度傳統 hash 就無能爲力了，因爲對於傳統 hash 來說，它要求隨機性足夠好，也就是說對於兩個輸入字符串，哪怕只有一個字母不同，使用傳統 hash 的輸出結果也是大不相同。

如圖示，以 SHA1 爲例，兩個字符串「我是中國人」與「我是中國人啊」只相差了一個字，但輸出的結果完全不同，根本沒法比較，退一步來說，就算要比較，每個 hash 結果也要一個字符一個字符的比，性能極差！

所以我們需要找到這樣的一個 hash 函數，它需要滿足兩個條件

1. 可以實現局部相似性
2. 生成的 hash 結果利於比較

先來看第二點，要讓 hash 結果利於比較，可以將結果轉化爲僅由 0，1 組成的定長二進制數字，這樣只要將結果進行異或運算，算出結果有幾位 1 即可，simhash 就是這麼做的

如圖示：將結果進行異或運算後只有兩位爲 1，即只有兩位是不一樣的

接下來我們再來看第一個問題，simhash 如何輸出局部相似性的結果， 它的計算過程與利用餘弦定理來計算文本相似度有一定的相似性，可以認爲是餘弦定理的一個演變，所以我們先來看看如何用餘弦定理來計算兩者的相似度

餘弦定理

第一次聽說餘弦定理是在吳軍的 <<數學之美>> 裏看到的，通過餘弦可以判斷兩篇文章是否相似，步驟都是類似的，將文章轉化爲 n 個維度的空間向量，再計算這兩個空間向量的在空間中的夾角，我們以下兩個文本爲例來看看如何利用餘弦定理來計算這兩個文本的相似度（本例子來自阮一峯博客）

1句子A：我喜歡看電視，不喜歡看電影。
2句子B：我不喜歡看電視，也不喜歡看電影。
3複製代碼
4

步驟一：分詞

1句子A：我/喜歡/看/電視，不/喜歡/看/電影。
2句子B：我/不/喜歡/看/電視，也/不/喜歡/看/電影。
3複製代碼
4

第二步，列出所有的關鍵詞。

1我，喜歡，看，電視，電影，不，也。
2複製代碼
3

畫外音：使用 TF-IDF 算法來算出所有的關鍵詞，像 「的」,「地」，「得」這種無意義的頓詞需要去掉

第三步，計算詞頻。

1句子A：我 1，喜歡 2，看 2，電視 1，電影 1，不 1，也 0。
2
3句子B：我 1，喜歡 2，看 2，電視 1，電影 1，不 2，也 1。
4複製代碼
5

第四步，寫出詞頻向量。

1句子A：[1, 2, 2, 1, 1, 1, 0]
2
3句子B：[1, 2, 2, 1, 1, 2, 1]
4複製代碼
5

注：這裏爲了演示方便簡單用出現的次數來作爲詞頻向量，實際上生產上一般不會這麼幹，一般會利用 TF-IDF 算法來生成詞頻向量，本文不作展開，感興趣的讀者可以自行研究

於是問題表現爲瞭如何在空間中計算這兩個向量的相似度了，我們可以把這兩個向量認爲是兩條線段，從原點 [0, 0, xxx]，指向這兩點的線段，這兩個線段形成了一個夾角，夾角越小，說明這兩個向量越相似，如何知道這兩個夾角的大小呢，計算它們的餘弦值（cosθ）即可，如果值越接近 1， 說明 θ 越小，兩個向量就越接近，文本也就越相似

於是問題轉化爲了如何計算 cosθ 的值，回憶下大學的數據公式, 其值計算如下

於是我們可以根據以上公式計算出句子 A 和句子 B 的 cosθ 值爲:

高達 93.8% 的相似度！這與實際情況吻合，既然使用餘弦定理就可以計算文章的相似性，那爲啥還要搞出 simhash 這樣的算法呢，細心的朋友不難發現它的缺點，計算餘弦的過程涉及到很多的乘法開方等計算，n 個分詞最終轉化後就是 n 維向量，一篇文章的分詞是非常多的，也就意味着這個 n 是非常大的，所以計算餘弦是非常耗時的，肯定無法應用於 Google 這樣需要海量網頁判重的場景。

由此分析可知餘弘定理計算主要性能瓶頸在於文章轉化後的高維度向量，高維度所需的計算量較複雜，那能否考慮降維呢，即把 n 維降低到 k 維（k 遠小於 n）甚至是一維，維度越小，計算量就越小，接下來我們就來看看如何利用隨機投影實現數據降維。

基於隨機投影來實現空間向量的降維

向量點積含義

隨機投影的基礎方法，是向量點積運算。所以理解隨機投影的基礎，是理解向量點積運算的含義。

設二維空間內有兩個向量，則其點積（也叫內積）定義爲以下實數：

點積運算

$OA→⋅OB→\overrightarrow{OA} \cdot \overrightarrow{OB}$OA⋅OB

表示的是兩個投影積，一個是 $OA→\overrightarrow{OA}$OA 在 $OB→\overrightarrow{OB}$OB 上的投影長度: $∣OA→∣cosθ|\overrightarrow{OA}|cos\theta$∣OA∣cosθ

一個是 OB 在其本身的投影長則爲 |OB|，

如果我們把 $OB→\overrightarrow{OB}$OB 看作是新空間的座標軸，那麼點 A 在新空間的座標是

假設有如下兩個向量

那麼點 A 以向量 $∣OB→∣|\overrightarrow{OB}|$∣OB∣ 所在直線爲座標軸的空間中，座標爲 a.b=7_1+3_(-1)=4，發現了嗎，此時點 A 在新空間中的座標由 2 維降到了 1 維，實際上向量點積不光可以實現二維降一維，也可以實現從 M 維降到 K 維。只要基於高斯分佈（即正態分佈），在原向量空間中找到一個 k 維向量

就可以讓原來任意一個在 M 維空間的向量 M 通過點積 M ⋅ R 將其降維到 K 維，Johnson–Lindenstrauss 引理指出：在歐式空間中的若干點，經過相同的映射後進入新的空間，它們仍然會保持原來的相對位置，也就是說原來向量之間的夾角在向量降維映射到新空間後依然可以認爲基本不變，這也就意味着降維後不會對文本的相似度計算產生影響。

隨機投影降維離散化 ---- 基於隨機投影的局部敏感哈希

通過隨機投影法，確實實現了高維度降到低維度的目標，但降維後生成的向量座標很可能是 float 型的，不利於存儲，而且在計算比如餘弦時，需要 float * float 的計算，我們知道浮點型計算是比較耗性能的，所以有人就提出能否對這些 float 的連續型座標離散化，這樣就解決了存儲，計算的難點。

在將數據映射到降維後的新空間後，我們將落在座標軸負軸的維度 (該維度取值爲負數)，統一賦值爲 0（或者 -1，使用 -1 的話 是將映射後的詞語放置在整個空間中，而不是某一個象限，這樣可以讓數據點分佈得更均勻一點），表示數據與對應隨機向量夾角大於 90 度。類似的，我們將落在座標軸非負軸的維度，統一賦值爲 1。這樣原始數據就被映射到了一個離散的新空間裏。

這種離散化的數據映射方法，就是我們常說的基於隨機投影的局部敏感哈希，經過離散化後，原來在空間中接近的數據點依然是相似或相同的，更重要的是經過離散化後轉化爲了 0，1 二進制數字，計算速度大大提高！

基於隨機投影的局部敏感哈希，也是隨機投影 hash 的一種，通過上述映射規則，將原空間向量進行了離散化降維

隨機超平面 hash

知道了什麼是基於隨機投影的局部敏感哈希, 也就不難理解隨機超平面 hash 了，它也是隨機投影 hash 離散化的變種，對於一個 n 維向量 v，如果要得到一個由 0，1 組成的 f 位簽名（f 遠小於 n），它的算法如下：

1. 隨機產生 f 個 n 維的向量 r1,…rf；
2. 對每一個向量 ri，如果 v 與 ri 的點積大於 0（說明在此向量劃分的空間是相似的），則最終簽名的第 i 位爲 1，否則爲 0。

這個算法相當於隨機產生了 f 個 n 維超平面，每個超平面將向量 v 所在的空間一分爲二，v 在這個超平面上方則得到一個 1，否則得到一個 0，然後將得到的 f 個 0 或 1 組合起來成爲一個 f 維的簽名

如圖所示，隨機在空間裏劃幾個超平面，就可以把數據分到不同空間裏，比如中間這個小三角的區域就可以賦值爲 110

每個降維後的 f 維簽名，就是文章的最終簽名！通過這樣的解釋相信大家不難理解通過異或比較位數的不同來判斷文章的相似度的幾何意義：​有幾位不同，代表其在幾面超平面上不相似

simhash 原理及實現

爲啥前面花這麼大力氣介紹引出隨機超平面 hash 呢，因爲 simhash 就是基於超平面 hash 演變而來的，可以說理解了超平面 hash 也就理解了 simhash，接下來我們看看 simhash 的生成流程:

simhash 的生成劃分爲五個步驟：分詞 ->hash-> 加權 -> 合併 -> 降維

1. 分詞: 這一步可以餘弦定理的 1~4 步類似，首先，判斷文本分詞，形成這個文章的特徵單詞。然後，形成去掉噪音詞的單詞序列。最後，爲每個分詞加上權重。我們假設權重分爲 5 個級別（1~5），比如：“美國 “51 區” 僱員稱內部有 9 架飛碟，曾看見灰色外星人 ” ==> 分詞後爲 “ 美國（4） 51 區（5） 僱員（3） 稱（1） 內部（2） 有（1） 9 架（3） 飛碟（5） 曾（1） 看見（3） 灰色（4） 外星人（5）”，括號裏是代表單詞在整個句子裏重要程度，數字越大越重要，爲了方便解釋，以下我們假設文檔只有「美國」和「51 區」這兩個分詞。

2. hash: 通過 hash 算法把每個詞變成 hash 值，比如 “美國” 通過 hash 算法計算爲 100101，“51 區”通過 hash 算法計算爲 101011。這樣，我們的字符串就變成了一串串數字，此 hash 值我們稱爲這些詞對應的獨熱編碼，然後再將 0 轉爲 -1，這樣美國的「100101」編碼爲了「1-1-11-11」，51 區的編碼爲「1-11-111」，將 0 轉爲 -1 的目的是將映射後的詞語放置在整個空間中，而不是某一個象限，這樣可以讓數據點分佈得更均勻一點，與隨機超平面 hash 相比，這裏使用了一個 “不隨機” 的超平面，將空間進行了分割。

3. 加權: 通過 2 步驟的 hash 生成結果，需要按照單詞的權重形成加權數字串，比如「美國」的 hash 值爲「1-1-11-11」，通過加權（權重參見步驟一得出的各個詞語的權重值）計算（相乘）爲「4 -4 -4 4 -4 4」；「51 區」的 hash 值爲「1-11-111」，通過加權計算爲 「5 -5 5 -5 5 5」，得到的各向量即表徵了這個文檔

4. 合併: 把上面各個單詞算出來的序列值累加，變成只有一個序列串。比如 “美國” 的 “4 -4 -4 4 -4 4”，“51 區” 的 “ 5 -5 5 -5 5 5”， 把每一位進行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。

5. 降維: 把第 4 步算出來的 「9 -9 1 -1 1 9」變成 0 1 串，形成我們最終的 simhash 簽名。 如果每一位大於 0 記爲 1，小於 0 記爲 0。最後算出結果爲：「1 0 1 0 1 1」，這裏採用了隨機超平面 hash 的離散化方法，得到文本的最終表示

相信細心的你不難發現在第二步和第五步可以看到隨機超平面的身影，也就是說並沒有產生直接的隨機超平面向量來映射，是間接產生的，如果想找到直接的超平面向量 R 來生成最後的簽名也不難，我們就假設文檔只有「美國」,「51 區」這兩個特徵詞，由第一，二步可知其文檔向量爲 d = (4, 5)，hash 後的編碼爲 100101，101011，我們注意到第三步還要再做一層轉換， 1 不變， 0 轉爲 -1

1 100101  ----> 1-1-11-11
2 101011  ----> 1-11-111
3複製代碼
4

再用逗號隔開，使其成爲了特徵詞對應的向量

1「美國」對應的向量：(1, -1, -1, 1, -1, 1)
2「51區」對應的向量：(1, -1, 1, -1, 1, 1)
3複製代碼
4

再把上述每個特徵詞對應向量的第 i 位取出來組成 ri 向量，如下

r1 = (1, 1), r2 = (-1, -1), r3 = (-1, 1), r4 = (1, -1), r5 = (-1, 1), r6 = (1, 1)

再回顧下隨機 hash 超平面算法的第二步:

1 對每一個向量 ri，如果 v 與 ri 的點積大於 0，則最終簽名的第 i 位爲 1，否則爲 0。
2複製代碼
3

將文檔向量 d = (4, 5) 與上述 r1...r5 每一個向量相乘，可得結果爲

1（9, -9, 1, -1, 1, 9）  ---->   (1 , 0, 1, 0, 1, 1)
2複製代碼
3

與 simhash 生成的完全一致！所以我們說 simhash 是從超平面 hash 算法演變更來的。

一般 simhash 生成的簽名爲 64 位，只要兩個簽名不同的位數少於等於 3 位我們就認爲兩個文章相似，這種使用不同進制位個數來計算兩者差異的方式我們也叫漢明距離。

simhash 查詢優化

生成了 64 位的簽名，然後就通過計算簽名的異或來查詢文章的相似度嗎？too young too naive! 對於 Google 網頁去重來說，可能會有幾十億的網頁內容，那每次判重都需要使用簽名進行幾十億的異或比較，這誰頂得住啊，那該如何優化呢？答案是利用抽屜原理進行優化存儲。

什麼是抽屜原理？把三個蘋果放進四個抽屜裏，必然有一個是空的

我們注意到判斷文章相似的條件 ，對於簽名爲 64 位的 simhash 簽名，只要位數少於等於 3 位即可判斷爲相似，這樣的話我們可以把 64 位的簽名分成四份，每份 16 位，如果相似，那必然有一份是完全相同的。

我們可以把簽名用 K-V 的形式進行存儲， K 爲其中的一部分，V 爲剩餘的 3 部分，先比較 K 是否精確匹配相同，如果匹配，再比較 V 部分的相似度，那麼這四部分哪一部分應該爲 K 呢，由於我們不知道哪一部分是精確匹配的，所以每一部分都應該爲 K，剩餘的部分爲 V，以文本 1 爲例，它應該設計成如下方式進行存儲，這樣保證不會有遺漏

以下是查詢庫

那麼用這樣的方式來存儲到底提升了多少速度，我們一起來算筆帳。

假設數據庫中有 2^30 條數據，也就是差不多 10 億條數據：

• 如果不用抽屜原理，則需要進行 10 億次的比較
• 如果使用抽屜原理
  • 首先先進行 K 的比較，由於是 K-V 也就是 hash 存儲，所以 K 比較時間複雜度是 0(1)，可以忽略不計，
  • K 如果精確匹配, 把所有對應的 V 取出來即可，那麼 V 可能有多少數據？因爲 K 最多可能有 2^16 位，所以 V 最多有 2^(30-16) = 2^14 位，
  • 由於最多進行 4 次 K 的比較，所以最多會進行 4 * 2^14 = 65536，約 6 萬次比較

可以看到利用抽屜原理比較次數從 10 億次降到了 6 萬次！查詢性能大大提升，當然了天下沒有免費的午餐，由於數據複製了四份，存儲空間也增大了 4 倍，這就是典型的以空間換時間。

simhash 缺點

simhash 比較適合海量長文上，短文本準確度上不高，因爲用來度量長文本相似的漢明距離閾值爲 3，但是短文本中，相似文本之間的漢明距離通常是大於 3 的。

所以你會發現在公衆號後臺如果你要標原創，字數必須大於 300，也是這個原因

總結

理解 simhash 的關鍵在於理解超平面隨機 hash，使用它可以實現向量從高維度到低維度的降維。網上有很多講 simhash 的的文章，但大多把降維這個具體過程給跳過了，看得是讓人一頭霧頭，所以筆者查閱了大量資料希望能幫助大家理解這一流程，希望大家能有收穫，如果想對 simhash 有更深入的理解，可以查閱文末一堆的參考鏈接，都非常棒！

巨人的肩膀

• www.cnblogs.com/shaosks/p/9…

• 局部敏感哈希算法及其思想的討論：my.oschina.net/u/4367429/b…

• www.ruanyifeng.com/blog/2013/0…

• zhuanlan.zhihu.com/p/81026564

• www.hanting.tech/2017/05/23/…

• zhuanlan.zhihu.com/p/92155250

• blog.csdn.net/sunny_ss12/…

• cloud.tencent.com/developer/a…

• www.cnblogs.com/sddai/p/100…

• 徹底弄懂 LSH 之 simHash 算法: www.cnblogs.com/hxsyl/p/451…

• 海量短文本場景下的去重算法：www.iyunying.org/seo/dataana…

• 海量數據相似度計算之 simhash 和海明距離: cloud.tencent.com/developer/a…

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://juejin.cn/post/6939461751251402789?utm_source=gold_browser_extension