simhash（局部敏感哈希）的原理
simhash的背景
simhash廣泛的用于搜尋領域中，也許在面試時你會經常遇到這樣的問題，如果對抓取的網頁進行排重，如何對搜尋結果進行排重等等。随着資訊膨脹時代的來臨，算法也在不斷的精進，相似算法同樣在不斷的發展，接觸過lucene的同學想必都會了解相似夾角的概念，那就是一種相似算法，通過計算兩個向量的餘弦值來判斷兩個向量的相似性，但這種方式需要兩兩進行計算向量的餘弦夾角，計算量比較大，不能用于實時計算或是大資料量的運算，比如在做搜尋結果的相似性排重時，需要對上千條結果進行相似性排重，如果兩兩比對的話，最少也需要進行上千次的向量餘弦值計算，其中涉及到分詞，特征提取，餘弦值計算等，很難滿足性能的需要。
jaccard相似度也是一種相似算法，它的計算方式比較直覺，就是sim（x,y）= (x∩y) / （x∪y）,例如：
若
S={a, d}
，
T={a, c, d}
則
Jaccard_Sim(S, T) = |{a, d}|/|{a, c, d}| = 2/3
也是一種需要實時生成特征向量并且進行計算的算法。
那麼
什麼是simhash呢？
Simhash 是一種用單個哈希函數得到文檔最小哈希簽名的方法，過程為：
- 将一個 f 維的向量 V 初始化為0；f 位的二進制數 S 初始化為0；
- 對每一個特征：用傳統的 hash 算法對該特征産生一個 f 位的簽名 b。對 i=1 到 f：
- 如果 b 的第 i 位為1，則 V 的第 i 個元素加上該特征的權重；
- 否則，V 的第 i 個元素減去該特征的權重。
- 如果 V 的第 i 個元素大于0，則 S 的第 i 位為1，否則為0；
- 輸出 S 作為簽名。
對兩篇文檔，它們的 Simhash 值之間不同位的個數越少（即海明距離越小），它們之間的 Jaccard 相似度越高。
什麼是局部敏感性哈希呢？
局部敏感哈希（LSH）是指這樣的哈希方法：對兩篇文檔，如果它們相似，則它們的哈希值有較高的機率是相同的。有了文檔的最小哈希簽名，我們就能實作這種哈希方法。直覺的做法是，将包含 b×r 個值最小哈希簽名分為 b 等份，每份 r 個，對兩個文檔，定義 P 為兩個文檔至少含有1個相同份的機率，顯然，文檔間的Jaccard 相似度越高，哈希簽名具有相同值的位數就越多，機率 P 就越大。
如何計算simhash呢？
simhash從内部看就是特征向量hash疊加的效果，并且具有局部敏感性，普通的hash算法針對差别不大的字元串會産生截然不同的hash值，但是simhash計算出來的hash值的海明距離會很相近。
具體的算法是将doc分解為特征向量，具體可以通過分詞，也可以通過bigram實作，并且可以賦予一定的權重，針對每個向量使用統一的hash函數進行hash，針對每個特征的hash值的每一位，如果是1就對simhash值的對應位加1，當然也可以使用權重，如果對應位是0，則simhash的對應位減1，對最後的simhash值如果該位大于0則該位置1，如果該位小于0，則該位置0，最後就可以得到一個真正的simhash值。
過程可以參考下面：
漢明距離的計算（不是simhash算法）代碼如下：
其中對二進制數統計含有幾個1，最快速的方法是:
每次讓二進制數H做 H=H&(H-1) 計算，在循環比較H是否大于0,統計循環次數，因為這樣每次都會把最後一個1和該1後面的全部取反，&之後全部為零，例如 11011010，減一之後為11011001，&之後為11011000，這樣就把11011010最後一個1去掉了，然後繼續按11011000，減一之後為11010111，&之後為1101000，依次類推，每次去掉一個1.
輸出為：
//漢明距離計算
#include<stdio.h>
#include<stdint.h>
int hamdistance(uint64_t sim1, uint64_t sim2){
uint64_t xor_val = sim1 ^ sim2;
int distance = 0;
//用這種方法可以快速計算出有幾個1，有幾個1就會循環幾次，不要一個一個比較，循環n次
while(xor_val > 0){
xor_val = xor_val & (xor_val - 1);
distance++;
}
return distance;
}
int main(int argc, char *argv[]){
uint64_t sim1 = 851459198;
uint64_t sim2 = 847263864;
int dis = hamdistance(sim1, sim2);
printf("hamdistance of %lu and %lu is %d", sim1, sim2, dis);
}
hamdistance of 851459198 and 847263864 is 4
simhash的好處？
simhash離線計算指紋，友善了大規模資料比較時的消耗，不需要在計算時提取特征進行計算，hash值的可比性很強，隻需要比較漢明距離，
友善了從海量資料中發掘相似項的實作，試想一個新文檔同百萬級甚至千萬級資料做相似夾角的情況。simhash大大減少了相似項排重的複雜度。
如何應用simhash呢，具體的應用場景？
simhash有兩個比較典型的應用，一個是網頁抓取的排重，一個是檢索時相似doc的排重
前者是在大集合中尋找是否具有相似項，後者是對檢索的集合進行濾重。
檢索集中發現相似項比較簡單，就是針對要排重的field離線提取特征，并計算simhash值，然後将檢索集中德記錄進行兩兩比較，就是計算漢明距離，兩個simhash值異或後求二進制中1的個數就是漢明距離了，這是真對較少的記錄。
針對較多的記錄，例如抓取時做排重，針對上千萬，或數億的資料，就需要對算法進行改進，因為求simhash的相似性，其實就是計算simhash間的漢明距離。
提到查找算法就不得不提到O（1）的hash表，但是如何讓simhash和hash表聯系在一起呢？
假如我們認為海明距離在3以内的具有很高的相似性，那樣我們就可以用到鴿巢原理，如果将simhash分成4段的話，那麼至少有一段完全相等的情況下才能滿足海明距離在3以内。同理将simhash分為6段，那麼至少要滿足三段完全相等，以此類推。
這樣我們就可以使用相等的部分做為hash的key，然後将具體的simhash值依次連結到value中，友善計算具體漢明距離。
1、将64位的二進制串等分成四塊
2、調整上述64位二進制，将任意一塊作為前16位，總共有四種組合，生成四份table
3、采用精确比對的方式查找前16位
4、如果樣本庫中存有2^34（差不多10億）的哈希指紋，則每個table傳回2^(34-16)=262144個候選結果，大大減少了海明距離的計算成本
我們可以将這種方法拓展成多種配置，不過，請記住，table的數量與每個table傳回的結果呈此消彼長的關系，也就是說，時間效率與空間效率不可兼得，參看下圖：
現在的以圖找圖功能也是simhash的一種展現，同樣适用指紋值分桶查找的原理實作。
參考引用
http://tech.uc.cn/?p=1086
http://grunt1223.iteye.com/blog/964564
http://www.lanceyan.com/tag/simhash
http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf
來源：http://blog.csdn.net/wdxin1322/article/details/16826331
我的數學之美系列二 —— simhash與重複資訊識别
在工作學習中，我往往感歎數學奇迹般的解決一些貌似不可能完成的任務，并且十分希望将這種喜悅分享給大家，就好比說：“老婆，出來看上帝”……
随着資訊爆炸時代的來臨，網際網路上充斥着着大量的近重複資訊，有效地識别它們是一個很有意義的課題。例如，對于搜尋引擎的爬蟲系統來說，收錄重複的網頁是毫無意義的，隻會造成存儲和計算資源的浪費；同時，展示重複的資訊對于使用者來說也并不是最好的體驗。造成網頁近重複的可能原因主要包括：
- 鏡像網站
- 内容複制
- 嵌入廣告
- 計數改變
- 少量修改
一個簡化的爬蟲系統架構如下圖所示：
事實上，傳統比較兩個文本相似性的方法，大多是将文本分詞之後，轉化為特征向量距離的度量，比如常見的歐氏距離、海明距離或者餘弦角度等等。兩兩比較固然能很好地适應，但這種方法的一個最大的缺點就是，無法将其擴充到海量資料。例如，試想像Google那種收錄了數以幾十億網際網路資訊的大型搜尋引擎，每天都會通過爬蟲的方式為自己的索引庫新增的數百萬網頁，如果待收錄每一條資料都去和網頁庫裡面的每條記錄算一下餘弦角度，其計算量是相當恐怖的。
我們考慮采用為每一個web文檔通過hash的方式生成一個指紋（fingerprint）。傳統的加密式hash，比如md5，其設計的目的是為了讓整個分布盡可能地均勻，輸入内容哪怕隻有輕微變化，hash就會發生很大地變化。我們理想當中的哈希函數，需要對幾乎相同的輸入内容，産生相同或者相近的hashcode，換句話說，hashcode的相似程度要能直接反映輸入内容的相似程度。很明顯，前面所說的md5等傳統hash無法滿足我們的需求。
simhash是locality sensitive hash（局部敏感哈希）的一種，最早由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出。Google就是基于此算法實作網頁檔案查重的。我們假設有以下三段文本：
the cat sat on the matthe cat sat on a matwe all scream for ice cream
使用傳統hash可能會産生如下的結果：
引用
irb(main):006:0> p1 = 'the cat sat on the mat'
irb(main):005:0> p2 = 'the cat sat on a mat'
irb(main):007:0> p3 = 'we all scream for ice cream'
irb(main):007:0> p1.hash
=> 415542861
irb(main):007:0> p2.hash
=> 668720516
irb(main):007:0> p3.hash
=> 767429688
使用simhash會應該産生類似如下的結果：
引用
irb(main):003:0> p1.simhash
=> 851459198
00110010110000000011110001111110
irb(main):004:0> p2.simhash
=> 847263864
00110010100000000011100001111000
irb(main):002:0> p3.simhash
=> 984968088
00111010101101010110101110011000
海明距離的定義，為兩個二進制串中不同位的數量。上述三個文本的simhash結果，其兩兩之間的海明距離為(p1,p2)=4，(p1,p3)=16以及(p2,p3)=12。事實上，這正好符合文本之間的相似度，p1和p2間的相似度要遠大于與p3的。
如何實作這種hash算法呢？以上述三個文本為例，整個過程可以分為以下六步：
1、選擇simhash的位數，請綜合考慮存儲成本以及資料集的大小，比如說32位
2、将simhash的各位初始化為0
3、提取原始文本中的特征，一般采用各種分詞的方式。比如對于"the cat sat on the mat"，采用兩兩分詞的方式得到如下結果：{"th", "he", "e ", " c", "ca", "at", "t ", " s", "sa", " o", "on", "n ", " t", " m", "ma"}
4、使用傳統的32位hash函數計算各個word的hashcode，比如："th".hash = -502157718
，"he".hash = -369049682，……
5、對各word的hashcode的每一位，如果該位為1，則simhash相應位的值加1；否則減1
6、對最後得到的32位的simhash，如果該位大于1，則設為1；否則設為0
整個過程可以參考下圖：
按照Charikar在論文中闡述的，64位simhash，海明距離在3以内的文本都可以認為是近重複文本。當然，具體數值需要結合具體業務以及經驗值來确定。
使用上述方法産生的simhash可以用來比較兩個文本之間的相似度。問題是，如何将其擴充到海量資料的近重複檢測中去呢？譬如說對于64位的待查詢文本的simhash code來說，如何在海量的樣本庫（>1M）中查詢與其海明距離在3以内的記錄呢？下面在引入simhash的索引結構之前，先提供兩種正常的思路。第一種是方案是查找待查詢文本的64位simhash code的所有3位以内變化的組合，大約需要四萬多次的查詢，參考下圖：
另一種方案是預生成庫中所有樣本simhash code的3位變化以内的組合，大約需要占據4萬多倍的原始空間，參考下圖：
顯然，上述兩種方法，或者時間複雜度，或者空間複雜度，其一無法滿足實際的需求。我們需要一種方法，其時間複雜度優于前者，空間複雜度優于後者。
假設我們要尋找海明距離3以内的數值，根據抽屜原理，隻要我們将整個64位的二進制串劃分為4塊，無論如何，比對的兩個simhash code之間至少有一塊區域是完全相同的，如下圖所示：
由于我們無法事先得知完全相同的是哪一塊區域，是以我們必須采用存儲多份table的方式。在本例的情況下，我們需要存儲4份table，并将64位的simhash code等分成4份；對于每一個輸入的code，我們通過精确比對的方式，查找前16位相同的記錄作為候選記錄，如下圖所示：
讓我們來總結一下上述算法的實質：
1、将64位的二進制串等分成四塊
2、調整上述64位二進制，将任意一塊作為前16位，總共有四種組合，生成四份table
3、采用精确比對的方式查找前16位
4、如果樣本庫中存有2^34（差不多10億）的哈希指紋，則每個table傳回2^(34-16)=262144個候選結果，大大減少了海明距離的計算成本
我們可以将這種方法拓展成多種配置，不過，請記住，table的數量與每個table傳回的結果呈此消彼長的關系，也就是說，時間效率與空間效率不可兼得，參看下圖：
事實上，這就是Google每天所做的，用來識别擷取的網頁是否與它龐大的、數以十億計的網頁庫是否重複。另外，simhash還可以用于資訊聚類、檔案壓縮等。
也許，讀到這裡，你已經感受到數學的魅力了。
來源：http://grunt1223.iteye.com/blog/964564
海量資料相似度計算之simhash和海明距離
通過 采集系統 我們采集了大量文本資料，但是文本中有很多重複資料影響我們對于結果的分析。分析前我們需要對這些資料去除重複，如何選擇和設計文本的去重算法？常見的有餘弦夾角算法、歐式距離、Jaccard相似度、最長公共子串、編輯距離等。這些算法對于待比較的文本資料不多時還比較好用，如果我們的爬蟲每天采集的資料以千萬計算，我們如何對于這些海量千萬級的資料進行高效的合并去重。最簡單的做法是拿着待比較的文本和資料庫中所有的文本比較一遍如果是重複的資料就标示為重複。看起來很簡單，我們來做個測試，就拿最簡單的兩個資料使用Apache提供的 Levenshtein for 循環100w次計算這兩個資料的相似度。代碼結果如下：
String s1 = "你媽媽喊你回家吃飯哦，回家羅回家羅" ;
String s2 = "你媽媽叫你回家吃飯啦，回家羅回家羅" ;
long t1 = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
int dis = StringUtils .getLevenshteinDistance(s1, s2);
}
long t2 = System.currentTimeMillis();
System. out .println(" 耗費時間： " + (t2 - t1) + " ms ");
耗費時間： 4266 ms
大跌眼鏡，居然計算耗費4秒。假設我們一天需要比較100w次，光是比較100w次的資料是否重複就需要4s，就算4s一個文檔，單線程一分鐘才處理15個文檔，一個小時才900個，一天也才21600個文檔，這個數字和一天100w相差甚遠，需要多少機器和資源才能解決。
為此我們需要一種應對于海量資料場景的去重方案，經過研究發現有種叫 local sensitive hash 局部敏感哈希 的東西，據說這玩意可以把文檔降維到hash數字，數字兩兩計算運算量要小很多。查找很多文檔後看到google對于重複網頁刪除偵測使用的是simhash，他們每天需要處理的文檔在億級别，大大超過了我們現在文檔的水準。既然老大哥也有類似的應用，我們也趕緊嘗試下。simhash是由 Charikar 在2002年提出來的，參考 《Similarity estimation techniques from rounding algorithms》 。 介紹下這個算法主要原理，為了便于了解盡量不使用數學公式，分為這幾步：
- 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”。
整個過程圖為：
大家可能會有疑問，經過這麼多步驟搞這麼麻煩，不就是為了得到個 0 1 字元串嗎？我直接把這個文本作為字元串輸入，用hash函數生成 0 1 值更簡單。其實不是這樣的，傳統hash函數解決的是生成唯一值，比如 md5、hashmap等。md5是用于生成唯一簽名串，隻要稍微多加一個字元md5的兩個數字看起來相差甚遠；hashmap也是用于鍵值對查找，便于快速插入和查找的資料結構。不過我們主要解決的是文本相似度計算，要比較的是兩個文章是否相識，當然我們降維生成了hashcode也是用于這個目的。看到這裡估計大家就明白了，我們使用的simhash就算把文章中的字元串變成 01 串也還是可以用于計算相似度的，而傳統的hashcode卻不行。我們可以來做個測試，兩個相差隻有一個字元的文本串，“你媽媽喊你回家吃飯哦，回家羅回家羅” 和 “你媽媽叫你回家吃飯啦，回家羅回家羅”。
通過simhash計算結果為：
1000010010101101111111100000101011010001001111100001001011001011
1000010010101101011111100000101011010001001111100001101010001011
通過 hashcode計算為：
1111111111111111111111111111111110001000001100110100111011011110
1010010001111111110010110011101
大家可以看得出來，相似的文本隻有部分 01 串變化了，而普通的hashcode卻不能做到，這個就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法應該算是業界公認比較好的算法。在simhash的發明人Charikar的論文中并沒有給出具體的simhash算法和證明，“量子圖靈”得出的證明simhash是由随機超平面hash算法演變而來的。
現在通過這樣的轉換，我們把庫裡的文本都轉換為simhash 代碼，并轉換為long類型存儲，空間大大減少。現在我們雖然解決了空間，但是如何計算兩個simhash的相似度呢？難道是比較兩個simhash的01有多少個不同嗎？對的，其實也就是這樣，我們通過海明距離（Hamming distance）就可以計算出兩個simhash到底相似不相似。兩個simhash對應二進制（01串）取值不同的數量稱為這兩個simhash的海明距離。舉例如下： 10101 和 00110 從第一位開始依次有第一位、第四、第五位不同，則海明距離為3。對于二進制字元串的a和b，海明距離為等于在a XOR b運算結果中1的個數（普遍算法）。
為了高效比較，我們預先加載了庫裡存在文本并轉換為simhash code 存儲在記憶體空間。來一條文本先轉換為 simhash code，然後和記憶體裡的simhash code 進行比較，測試100w次計算在100ms。速度大大提升。
未完待續：
1、目前速度提升了但是資料是不斷增量的，如果未來資料發展到一個小時100w，按現在一次100ms，一個線程處理一秒鐘 10次，一分鐘 60 * 10 次，一個小時 60*10 *60 次 = 36000次，一天 60*10*60*24 = 864000次。 我們目标是一天100w次，通過增加兩個線程就可以完成。但是如果要一個小時100w次呢？則需要增加30個線程和相應的硬體資源保證速度能夠達到，這樣成本也上去了。能否有更好的辦法，提高我們比較的效率？
2、通過大量測試，simhash用于比較大文本，比如500字以上效果都還蠻好，距離小于3的基本都是相似，誤判率也比較低。但是如果我們處理的是微網誌資訊，最多也就140個字，使用simhash的效果并不那麼理想。看如下圖，在距離為3時是一個比較折中的點，在距離為10時效果已經很差了，不過我們測試短文本很多看起來相似的距離确實為10。如果使用距離為3，短文本大量重複資訊不會被過濾，如果使用距離為10，長文本的錯誤率也非常高，如何解決？
參考：
Detecting near-duplicates for web crawling.
Similarity estimation techniques from rounding algorithms.
http://en.wikipedia.org/wiki/Locality_sensitive_hashing
http://en.wikipedia.org/wiki/Hamming_distance
simHash 簡介以及 java 實作
simhash原理推導
文章來源：http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity.html
海量資料相似度計算之simhash短文本查找
在前一篇文章 《海量資料相似度計算之simhash和海明距離》 介紹了simhash的原理，大家應該感覺到了算法的魅力。但是随着業務的增長 simhash的資料也會暴增，如果一天100w，10天就1000w了。我們如果插入一條資料就要去比較1000w次的simhash，計算量還是蠻大，普通PC 比較1000w次海明距離需要 300ms ，和5000w資料比較需要1.8 s。看起來相似度計算不是很慢，還在秒級别。給大家算一筆賬就知道了：
随着業務增長需要一個小時處理100w次，一個小時為3600 *1000 = 360w毫秒，計算一下一次相似度比較最多隻能消耗 360w / 100w = 3.6毫秒。300ms慢嗎，慢！1.8S慢嗎，太慢了！很多情況大家想的就是更新、增加機器，但有些時候光是增加機器已經解決不了問題了，就算增加機器也不是短時間能夠解決的，需要考慮分布式、客戶預算、問題解決的容忍時間？頭大時候要相信人類的智慧是無窮的，泡杯茶，聽下輕音樂：）暢想下宇宙有多大，宇宙外面還有什麼東西，程式員有什麼問題能夠難倒呢？
加上客戶還提出的幾個，彙總一下技術問題：
- 1、一個小時需要比較100w次，也就是每條資料和simhash庫裡的資料比較需要做到3.6毫秒。
- 2、兩條同一時刻發出的文本如果重複也隻能保留一條。
- 3、希望保留2天的資料進行比較去重，按照目前的量級和未來的增長，2天大概在2000w — 5000w 中間。
- 4、短文本和長文本都要去重，經過測試長文本使用simhash效果很好，短文本使用simhash 準備度不高。
目前我們估算一下存儲空間的大小，就以JAVA 來說，存儲一個simhash 需要一個原生态 lang 類型是64位 = 8 byte，如果是 Object 對象還需要額外的 8 byte，是以我們盡量節約空間使用原生态的lang類型。假設增長到最大的5000w資料， 5000w * 8byte = 400000000byte = 400000000/( 1024 * 1024) = 382 Mb，是以按照這個大小普通PC伺服器就可以支援，這樣第三個問題就解決了。
比較5000w次怎麼減少時間呢？其實這也是一個查找的過程，我們想想以前學過的查找算法： 順序查找、二分查找、二叉排序樹查找、索引查找、哈希查找。不過我們這個不是比較數字是否相同，而是比較海明距離，以前的算法并不怎麼通用，不過解決問題的過程都是通用的。還是和以前一樣，不使用數學公式，使用程式猿大家都了解的方式。還記得JAVA裡有個HashMap嗎？我們要查找一個key值時，通過傳入一個key就可以很快的傳回一個value，這個号稱查找速度最快的資料結構是如何實作的呢？看下hashmap的内部結構：
如果我們需要得到key對應的value，需要經過這些計算，傳入key，計算key的hashcode，得到7的位置；發現7位置對應的value還有好幾個，就通過連結清單查找，直到找到v72。其實通過這麼分析，如果我們的hashcode設定的不夠好，hashmap的效率也不見得高。借鑒這個算法，來設計我們的simhash查找。通過順序查找肯定是不行的，能否像hashmap一樣先通過鍵值對的方式減少順序比較的次數。看下圖：
存儲：
1、将一個64位的simhash code拆分成4個16位的二進制碼。（圖上紅色的16位）
2、分别拿着4個16位二進制碼查找目前對應位置上是否有元素。（放大後的16位）
3、對應位置沒有元素，直接追加到連結清單上；對應位置有則直接追加到連結清單尾端。（圖上的 S1 — SN）
查找：
1、将需要比較的simhash code拆分成4個16位的二進制碼。
2、分别拿着4個16位二進制碼每一個去查找simhash集合對應位置上是否有元素。
2、如果有元素，則把連結清單拿出來順序查找比較，直到simhash小于一定大小的值，整個過程完成。
原理：
借鑒hashmap算法找出可以hash的key值，因為我們使用的simhash是局部敏感哈希，這個算法的特點是隻要相似的字元串隻有個别的位數是有差别變化。那這樣我們可以推斷兩個相似的文本，至少有16位的simhash是一樣的。具體選擇16位、8位、4位，大家根據自己的資料測試選擇，雖然比較的位數越小越精準，但是空間會變大。分為4個16位段的存儲空間是單獨simhash存儲空間的4倍。之前算出5000w資料是 382 Mb，擴大4倍1.5G左右，還可以接受：）
通過這樣計算，我們的simhash查找過程全部降到了1毫秒以下。就加了一個hash效果這麼厲害？我們可以算一下，原來是5000w次順序比較，現在是少了2的16次方比較，前面16位變成了hash查找。後面的順序比較的個數是多少？ 2^16 = 65536， 5000w/65536 = 763 次。。。。實際最後連結清單比較的資料也才 763次！是以效率大大提高！
到目前第一點降到3.6毫秒、支援5000w資料相似度比較做完了。還有第二點同一時刻發出的文本如果重複也隻能保留一條和短文本相識度比較怎麼解決。其實上面的問題解決了，這兩個就不是什麼問題了。
- 之前的評估一直都是按照線性計算來估計的，就算有多線程送出相似度計算比較，我們提供相似度計算伺服器也需要線性計算。比如同時用戶端發送過來兩條需要比較相似度的請求，在伺服器這邊都進行了一個排隊處理，一個接着一個，第一個處理完了在處理第二個，等到第一個處理完了也就加入了simhash庫。是以隻要服務端加了隊列，就不存在同時請求不能判斷的情況。
- simhash如何處理短文本？換一種思路，simhash可以作為局部敏感哈希第一次計算縮小整個比較的範圍，等到我們隻有比較700多次比較時，就算使用我們之前精準度高計算很慢的編輯距離也可以搞定。當然如果覺得慢了，也可以使用餘弦夾角等效率稍微高點的相似度算法。
參考：
我的數學之美系列二 —— simhash與重複資訊識别
package pro;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class test {
private String tokens;
private BigInteger intSimHash;
private String strSimHash;
private int hashbits = 64;
public test(String tokens) {
this.tokens = tokens;
this.intSimHash = this.simHash();
}
public test(String tokens, int hashbits) {
this.tokens = tokens;
this.hashbits = hashbits;
this.intSimHash = this.simHash();
}
public BigInteger simHash() {
int[] v = new int[this.hashbits];
StringTokenizer stringTokens = new StringTokenizer(this.tokens);
while (stringTokens.hasMoreTokens()) {//算出字元串的64位權重值
String temp = stringTokens.nextToken();
BigInteger t = this.hash(temp);
for (int i = 0; i < this.hashbits; i++) {//周遊64次後将temp的hash值轉化為1或-1，順便計算權重
BigInteger bitmask = new BigInteger("1").shiftLeft(i);
if (t.and(bitmask).signum() != 0) {
v[i] += 1;
} else {
v[i] -= 1;
}
}
}
BigInteger fingerprint = new BigInteger("0");//計算出的64位值
StringBuffer simHashBuffer = new StringBuffer();
for (int i = 0; i < this.hashbits; i++) {
if (v[i] >= 0) {
fingerprint = fingerprint.add(new BigInteger("1").shiftLeft(i));
simHashBuffer.append("1");
}else{
simHashBuffer.append("0");
}
}
this.strSimHash = simHashBuffer.toString();
System.out.println(this.strSimHash + " length " + this.strSimHash.length());
return fingerprint;
}
private BigInteger hash(String source) {
if (source == null || source.length() == 0) {
return new BigInteger("0");
} else {
char[] sourceArray = source.toCharArray();
BigInteger x = BigInteger.valueOf(((long) sourceArray[0]) << 7);
BigInteger m = new BigInteger("1000003");
BigInteger mask = new BigInteger("2").pow(this.hashbits).subtract(
new BigInteger("1"));//2的64次方-1
for (char item : sourceArray) {//周遊每一個字元變為long型
BigInteger temp = BigInteger.valueOf((long) item);
x = x.multiply(m).xor(temp).and(mask);
}
x = x.xor(new BigInteger(String.valueOf(source.length())));
if (x.equals(new BigInteger("-1"))) {
x = new BigInteger("-2");
}
return x;
}
}
//海明距離
public int hammingDistance(test other) {
BigInteger x = this.intSimHash.xor(other.intSimHash);
int tot = 0;
//統計x中二進制位數為1的個數
//我們想想，一個二進制數減去1，那麼，從最後那個1（包括那個1）後面的數字全都反了，對吧，然後，n&(n-1)就相當于把後面的數字清0，
//我們看n能做多少次這樣的操作就OK了。
while (x.signum() != 0) {
tot += 1;
x = x.and(x.subtract(new BigInteger("1")));
}
return tot;
}
public int getDistance(String str1, String str2) {
int distance;
if (str1.length() != str2.length()) {
distance = -1;
} else {
distance = 0;
for (int i = 0; i < str1.length(); i++) {
if (str1.charAt(i) != str2.charAt(i)) {
distance++;
}
}
}
return distance;
}
//劃分，劃分為distance+1份
public List subByDistance(test simHash, int distance){
int numEach = this.hashbits/(distance+1);//numeach為16
List characters = new ArrayList();
StringBuffer buffer = new StringBuffer();
int k = 0;
for( int i = 0; i < this.intSimHash.bitLength(); i++){
boolean sr = simHash.intSimHash.testBit(i);//判斷目前位是否為1
if(sr){
buffer.append("1");
}
else{
buffer.append("0");
}
if( (i+1)%numEach == 0 ){//每一塊
BigInteger eachValue = new BigInteger(buffer.toString(),2);
System.out.println("----" +eachValue );
buffer.delete(0, buffer.length());
characters.add(eachValue);
}
}
return characters;
}
public static void main(String[] args) {
String s = "This is a test string for testing";
test hash1 = new test(s, 64);
System.out.println(hash1.intSimHash + " " + hash1.intSimHash.bitLength());
hash1.subByDistance(hash1, 3);
System.out.println("\n");
s = "This is a test string for testing, This is a test string for testing abcdef";
test hash2 = new test(s, 64);
System.out.println(hash2.intSimHash+ " " + hash2.intSimHash.bitCount());
hash1.subByDistance(hash2, 3);
s = "This is a test string for testing als";
test hash3 = new test(s, 64);
System.out.println(hash3.intSimHash+ " " + hash3.intSimHash.bitCount());
hash1.subByDistance(hash3, 3);
System.out.println("============================");
int dis = hash1.getDistance(hash1.strSimHash,hash2.strSimHash);
System.out.println(hash1.hammingDistance(hash2) + " "+ dis);
int dis2 = hash1.getDistance(hash1.strSimHash,hash3.strSimHash);
System.out.println(hash1.hammingDistance(hash3) + " " + dis2);
}
}
文章來源：http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity2-html.html