算法簡介

simHash是用來網頁去重最常用的hash方法，速度很快

simhash算法的輸入是一個向量，輸出是一個f位的簽名值。為了陳述方便，假設輸入的是一個文檔的特徵集合，每個特徵有一定的權重。比如特徵可以是文檔中的詞，其權重可以是這個詞出現的次數。

算法步驟

simhash算法分為5個步驟：分詞、hash、加權、合併、降維，具體過程如下所述：

• 分詞

給定一段語句，進行分詞，得到有效的特徵向量，然後為每一個特徵向量設置1-5等5個級別的權重。

• hash

通過hash函數計算各個特徵向量的hash值，hash值為二進制數01組成的n-bit簽名。

• 加權

在hash值的基礎上，給所有特徵向量進行加權，即W = Hash * weight，且遇到1則hash值和權值正相乘，遇到0則hash值和權值負相乘。

• 合併

將上述各個特徵向量的加權結果累加，變成只有一個序列串。

• 降維

對於n-bit簽名的累加結果，如果大於0則置1，否則置0，從而得到該語句的simhash值，最後我們便可以根據不同語句simhash的海 明距離來判斷它們的相似度。

算法應用

例如：

需要計算“CSDN博客”的simhash簽名值為“1 0 1 0 1 1”，假定我們計算出另外一個短語的簽名值為“1 0 1 0 0 0”，那麼根據異或規則，我們可以計算出這兩個簽名的海明距離為2，從而判定這兩個短語的相似度是比較高的。

簡單來說，現在問題轉換為：對於64位的SimHash值，我們只要找到海明距離在3以內的所有簽名，即可找出所有相似的短語。現在關鍵是，如何將其擴展到海量數據呢？譬如如何在海量的樣本庫中查詢與其海明距離在3以內的記錄呢？

• 一種方案是查找待查詢文本的64位simhash code的所有3位以內變化的組合
• 大約需要四萬多次的查詢
• 另一種方案是預生成庫中所有樣本simhash code的3位變化以內的組合
• 大約需要佔據4萬多倍的原始空間

這兩種方案，要麼時間複雜度高，要麼空間複雜度複雜，能否有一種方案可以達到時空複雜度的絕佳平衡呢？答案是肯定的：

• 我們可以把 64 位的二進制simhash簽名均分成4塊，每塊16位。根據鴿巢原理（也稱抽屜原理），如果兩個簽名的海明距離在 3 以內，它們必有一塊完全相同。
• 然後把分成的4 塊中的每一個塊分別作為前16位來進行查找，建倒排索引。

這樣看來，如果樣本庫中存有2^34的simhash簽名，則每個table返回2^(34-16)=262144個候選結果，大大減少了海明距離的計算成本。

• 假設數據是均勻分佈，16位的數據，產生的像限為2^16個，則平均每個像限分佈的文檔數則為2^34/2^16 = 2^(34-16)) ，四個塊返回的總結果數為 4* 262144。
• 原本需要比較10億次，經過索引後，大概只需要處理100萬次。