一、背景介紹

根據?Detecting Near-Duplicates for Web Crawling?論文中的介紹，在互聯網中有很多網頁的內容是一樣的，但是它們的網頁元素卻不是完全相同的。每個域名下的網頁總會有一些自己的東西，比如廣告、導航欄、網站版權之類的東西，但是對于搜索引擎來講，只有內容部分才是有意義的，雖然網頁元素不同，但是對搜索結果沒有任何影響，所以在判定內容是否重復的時候，應該忽視后面的部分。當新爬取的內容和數據庫中的某個網頁的內容一樣的時候，就稱其為Near-Duplicates（重復文章）。對于重復文章，不應再執行入庫操作，這種操作的優點是(A)節省帶寬、(B)節省磁盤、(C)減輕服務器負荷以及(D)去除相似文章噪點干擾，提升索引的質量。

在現實中，一模一樣的網頁的概率是很小的，大部分的相似網頁都會存在一些細節的變化，而如何進行這種判定就是一個本文要解決的一個問題。除了近似文章判定算法的難題，還有以下待解決的難點（按照80億篇文章來考慮）：

• 數據規模巨大，對于海量數據如何存儲
• 查找速度，如何做到在毫秒級別返回檢索結果

二、simhash介紹

simhash是由 Charikar 在2002年提出來的，它是一種能計算文檔相似度的hash算法，google用它來進行海量文本去重工作。simhash屬于局部敏感型（locality sensitive hash）的一種，其主要思想是降維，將高維的特征向量轉化成一個f位的指紋（fingerprint），通過算出兩個指紋的海明距離（hamming distince）來確定兩篇文章的相似度，海明距離越小，相似度越低（根據?Detecting Near-Duplicates for Web Crawling?論文中所說），一般海明距離為3就代表兩篇文章相同。
simhash也有其局限性，在處理小于500字的短文本時，simhash的表現并不是很好，所以在使用simhash前一定要注意這個細節。

三、simhash與hash算法的區別

傳統Hash算法只負責將原始內容盡量均勻隨機地映射為一個簽名值，原理上僅相當于偽隨機數產生算法。傳統hash算法產生的兩個簽名，如果不相等，除了說明原始內容不相等外，不再提供任何信息，因為即使原始內容只相差一個字節，所產生的簽名也很可能差別很大，所以傳統Hash是無法在簽名的維度上來衡量原內容的相似度。而SimHash本身屬于一種局部敏感哈希算法，它產生的hash簽名在一定程度上可以表征原內容的相似度。

　　我們主要解決的是文本相似度計算，要比較的是兩個文章是否相似，當然我們降維生成了hash簽名也是用于這個目的。看到這里，估計大家就明白了，即使把文章中的字符串變成 01 串，我們使用的simhash算法也還是可以用于計算相似度，而傳統的hash卻不行。我們可以來做個測試，兩個相差只有一個字符的文本串，“你媽媽喊你回家吃飯哦，回家羅回家羅” 和 “你媽媽叫你回家吃飯啦，回家羅回家羅”。

通過simhash計算結果為：

　　1000010010101101111111100000101011010001001111100001001011001011

　　1000010010101101011111100000101011010001001111100001101010001011

通過傳統hash計算為：

　　0001000001100110100111011011110

　　1010010001111111110010110011101
大家可以看得出來，相似的文本只有部分 01 串變化了，而普通的hash卻不能做到，這個就是局部敏感哈希的魅力。

四、simhash的生成

simhash的生成圖解如下圖：

為了更加通俗易懂，采用例子來詳解simhash的生成規則。simhash的生成劃分為五個步驟：分詞->hash->加權->合并->降維

• 1：分詞。首先，判斷文本分詞，形成這個文章的特征單詞。然后，形成去掉噪音詞的單詞序列。最后，為每個分詞加上權重。我們假設權重分為5個級別（1~5），比如：“ 美國“51區”雇員稱內部有9架飛碟，曾看見灰色外星人 ” ==> 分詞后為 “ 美國（4） 51區（5） 雇員（3） 稱（1） 內部（2） 有（1） 9架（3） 飛碟（5） 曾（1） 看見（3） 灰色（4） 外星人（5）”，括號里是代表單詞在整個句子里重要程度，數字越大越重要。

• 2：hash。通過hash算法把每個詞變成hash值，比如“美國”通過hash算法計算為 100101，“51區”通過hash算法計算為 101011。這樣，我們的字符串就變成了一串串數字，還記得文章開頭說過的嗎？要把文章變為數字計算，才能提高相似度計算性能，現在是降維過程進行時。

• 3：加權。在第2步驟hash生成結果后，需要按照單詞的權重形成加權數字串，比如“美國”的hash值為“100101”，通過加權計算為“4 -4 -4 4 -4 4”；“51區”的hash值為“101011”，通過加權計算為 “ 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”。

整個過程的流程圖為：

五、simhash分表存儲策略

在線上查詢算法中，首先建立多個指紋表:T1，T2，√…，Tt。每個指紋表 Ti 關聯兩個未知數：一個整型pi和一個在f bit-positions上的排列πi，Ti就是對已經存在的所有指紋進行排列πi得到的有序集合。對于一個指紋f和一個整數k，算法分兩個步驟：

• 1 找到Ti中所有的前pi個bit-positions和πi（F）的前pi個bit-positions相同的指紋，假設為指紋集合F。
• 2 在F中的每一個指紋，比較其是否和πi（F）有的差異不超過k個。

分表存儲原理

借鑒“hashmap算法找出可以hash的key值”。因為我們使用的simhash是局部敏感哈希，這個算法的特點是：只要相似的字符串，只有個別的位數是有差別變化的。這樣，我們可以推斷兩個相似的文本，至少有16位的simhash是一樣的。

分表存儲設計

假設f = 64 ，k=3，并且我們有80億 = 2^34個數的網頁指紋，d=34，可以有下面四種設計方法 （f：指紋位數，k：海明距離，d：將文章數量轉化成2的冪次方，d就是冪值）

1.20個表：將64bit分為11,11,11,11,10,10六個bit塊。根據排列組合，如果想從這6個塊中找3個作為leading bits的話（這樣才能滿足|pi-d|是個小整數），一共有C(6,3)=20種找法，所以需要20個表，每個表的前三塊來自不同的三個塊，那么pi就有11+11+11、11+ 11+10和11+10+10三種可能了。一次嗅探平均需要檢索2^(34-31)=8個指紋。
2.16個表：先將64bit均分成4份，然后針對每份，將剩余的48bit再均分成四份，也就是16,12,12,12,12,12五部分，很明顯這種組合的可能是4*4，而pi = 28。一次嗅探平均需要檢索2^(34-28)=64個指紋。
3.10個表：將64bit分成 13，13，13，13，12 五個bit快。根據排列組合，需要從5塊中找到2個作為leading bits，共有C(5,2)=10種找法，需要10張表，而pi=25或26。一次嗅探平均需要檢索2^(34-25)=512個指紋。
4.4個表：同理 64 等分為4份，每份16bit，從四份中找出1個leading bits，共有C(4,1)=4種找法，pi=16,一次嗅探平均需要檢索2^(34-16)=256K個指紋。

分表存儲實現

存儲：
　　1、將一個64位的simhash簽名拆分成4個16位的二進制碼。（圖上紅色的16位）
　　2、分別拿這4個16位二進制碼查找當前對應位置上是否有元素。（放大后的16位）
　　3、對應位置沒有元素，直接追加到鏈表上；對應位置有則直接追加到鏈表尾端。（圖上的 S1 — SN）

　　查找：
　　1、將需要比較的simhash簽名拆分成4個16位的二進制碼。
　　2、分別拿著4個16位二進制碼每一個去查找simhash集合對應位置上是否有元素。
　　3、如果有元素，則把鏈表拿出來順序查找比較，直到simhash小于一定大小的值，整個過程完成。

　　原理：
　　借鑒“hashmap算法找出可以hash的key值”。因為我們使用的simhash是局部敏感哈希，這個算法的特點是：只要相似的字符串，只有個別的位數是有差別變化的。那這樣我們可以推斷兩個相似的文本，至少有16位的simhash是一樣的。具體選擇16位、8位、4位，大家根據自己的數據測試選擇，雖然比較的位數越小越精準，但是空間會變大。分為4個16位段的存儲空間是單獨simhash存儲空間的4倍。之前算出5000w數據是 382 Mb，擴大4倍1.5G左右，還可以接受

最佳分表策略

根據 4.2節分表存儲設計，給定 f,k 我們可以有很多種分表的方式，增加表的個數會減少檢索時間，但是會增加內存的消耗，相反的，減少表的個數，會減少內存的壓力，但是會增加檢索時間。
根據google大量的實驗，存在一個分表策略滿足時間和空間的平衡點

τ=d-pi （pi計算看4.2章節，取最小pi）

simhash存儲實現(Go)

國外有一大神用go實現了d=3和6的實現，在他的基礎上我實現了d到8的擴展，源碼請看https://github.com/kricen/shstorage

參考文章

論文 Detecting Near-Duplicates for Web Crawling
http://www.cnblogs.com/maybe2030/p/5203186.html

尊重別人勞動成果，原文鏈接：https://kricen.github.io/2018/03/06/perday/simhash/

總結

以上是生活随笔為你收集整理的Simhash的生成及存储的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。