simhash是google用來處理海量文本去重的算法。 google出品，你懂的。 simhash最牛逼的一點就是將一個文檔，最后轉換成一個64位的字節，暫且稱之為特征字，然后判斷重復只需要判斷他們的特征字的距離是不是<n（根據經驗這個n一般取值為3），就可以判斷兩個文檔是否相似。

原理

simhash值的生成圖解如下：

大概花三分鐘看懂這個圖就差不多怎么實現這個simhash算法了。特別簡單。谷歌出品嘛，簡單實用。

算法過程大概如下：

將Doc進行關鍵詞抽取(其中包括分詞和計算權重)，抽取出n個(關鍵詞，權重)對， 即圖中的(feature, weight)們。 記為feature_weight_pairs = [fw1, fw2 ... fwn]，其中fwn = (feature_n, weight_n)。
hash_weight_pairs = [ (hash(feature), weight) for feature, weight in feature_weight_pairs ]生成圖中的(hash,weight)們, 此時假設hash生成的位數bits_count = 6（如圖）;
然后對hash_weight_pairs進行位的縱向累加，如果該位是1，則+weight,如果是0，則-weight，最后生成bits_count個數字，如圖所示是[13, 108, -22, -5, -32, 55], 這里產生的值和hash函數所用的算法相關。
[13,108,-22,-5,-32,55] -> 110001這個就很簡單啦，正1負0。

到此，如何從一個doc到一個simhash值的過程已經講明白了。 但是還有一個重要的部分沒講，

simhash值的海明距離計算

二進制串A 和 二進制串B 的海明距離 就是A xor B后二進制中1的個數。

舉例如下：

A = 100111;
B = 101010;
hamming_distance(A, B) = count_1(A xor B) = count_1(001101) = 3;

當我們算出所有doc的simhash值之后，需要計算doc A和doc B之間是否相似的條件是：

A和B的海明距離是否小于等于n，這個n值根據經驗一般取值為3,

simhash本質上是局部敏感性的hash，和md5之類的不一樣。 正因為它的局部敏感性，所以我們可以使用海明距離來衡量simhash值的相似度。

高效計算二進制序列中1的個數

/* src/Simhasher.hpp */
bool isEqual(uint64_t lhs, uint64_t rhs, unsigned short n = 3)
{
    unsigned short cnt = 0;
    lhs ^= rhs;
    while(lhs && cnt <= n)
    {
        lhs &= lhs - 1;
        cnt++;
    }
    if(cnt <= n)
    {
        return true;
    }
    return false;
}

由上式這個函數來計算的話，時間復雜度是 O(n); 這里的n默認取值為3。由此可見還是蠻高效的。

simhash實現的工程項目

我自己寫的simhash

主要是針對中文文檔，也就是此項目進行simhash之前同時還進行了分詞和關鍵詞的抽取。

對比其他算法

百度的去重算法

百度的去重算法最簡單，就是直接找出此文章的最長的n句話，做一遍hash簽名。n一般取3。 工程實現巨簡單，據說準確率和召回率都能到達80%以上。

shingle算法

shingle原理略復雜，不細說。 shingle算法我認為過于學院派，對于工程實現不夠友好，速度太慢，基本上無法處理海量數據。

其他算法

具體看微博上的討論

參考

Similarity estimation techniques from rounding algorithms
simhash與Google的網頁去重
海量數據相似度計算之simhash和海明距離

總結

以上是生活随笔為你收集整理的（转）simhash算法原理及实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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