1. 首先SimHash的算法生成圖如下圖所示：
生成步驟如下：
- 對(duì)于每篇文章，選擇分詞作為該篇文章的特征，獲取去掉噪音的詞做為文檔特征，為每個(gè)詞賦予一個(gè)權(quán)重，該權(quán)重可以使用TFIDF來(lái)對(duì)應(yīng)
- 根據(jù)機(jī)器的存儲(chǔ)以及性能，可以選擇使用哪種hash算法，計(jì)算出每個(gè)詞的hash值，可以是32位的也可以是64位的
- 對(duì)于上述hash值的每一位乘以相應(yīng)的權(quán)重，得到新的hash序列，最后將每個(gè)詞的每一位hash序列相加求和
- 對(duì)于求和后的hash序列，如果該位>0，最終的simhash的該位=1,否則simhash=0
simhash可以用來(lái)衡量?jī)善臋n的相似程度，如果兩篇文檔比較相似，那么他們的simhash值也相似，這種hash算法與MD5算法不同：
對(duì)于MD5算法，稍微對(duì)某個(gè)字符串修改一點(diǎn)，那么得出的MD5戳就會(huì)發(fā)生很大的變化。
2.如何通過(guò)兩篇文檔的simHash來(lái)檢查兩篇文檔是否相似呢？使用海明距離。
海明距離：兩個(gè)hash串異或之后1的個(gè)數(shù)，也就是兩個(gè)simhash串不同的位數(shù)。根據(jù)經(jīng)驗(yàn)，一般海明距離<=3或者4的時(shí)候，兩篇文檔相似。
如何高效計(jì)算某個(gè)二進(jìn)制串中為1的個(gè)數(shù)呢？
int getHammingDistance(BigInteger hash1, BigInteger hash2){
BigInteger data = hash1.xor(hash2);
int tot = 0;
while (data != 0) {
tot += 1;
data = data&(data-1);
}
return tot;
}
時(shí)間復(fù)雜度為o(n), 我們知道一個(gè)二進(jìn)制數(shù)減掉1之后和該二進(jìn)制數(shù)去&操作,相當(dāng)于把最右邊的一位1變成了0,因此能執(zhí)行多少次這樣的操作就有多少個(gè)1存在.
3. 工程實(shí)現(xiàn)的問(wèn)題：
在工程實(shí)現(xiàn)中，往往數(shù)據(jù)量較大, 如每篇文章要和500萬(wàn)的文章進(jìn)行比較，假如hash值位數(shù)是64位，比較一次的時(shí)間復(fù)雜度是o(64)
對(duì)于每篇文章都要比較500萬(wàn)次，時(shí)間消耗也就較大。
因此第一步需要縮小比較范圍，以空間換時(shí)間的方式，可以借鑒HashMap的存儲(chǔ)和查找方式,key代表1/4的hash值,value使用鏈表的方式存儲(chǔ)多個(gè)文章的simhash:
1.將simhash值拆分成4個(gè)16位的hash
2.分別拿著4個(gè)hash去map中是否有該值,如果有的話,追加到key對(duì)應(yīng)的鏈表中,沒(méi)有的話新建key對(duì)應(yīng)的鏈表
在查找的時(shí)候,可以分別拿著4個(gè)16為的hash值,去查找map,然后依次和value鏈表中的多個(gè)simhash序列比較即可.具體可參照下面的參考鏈接.
優(yōu)缺點(diǎn)：
simhash用于比較大文本，比如500字以上效果比較好，距離小于3的基本都是相似，誤判率也比較低。
但是如果處理的是微博信息，最多也就140個(gè)字，使用simhash的效果并不那么理想。
參考：
https://yanyiwu.com/work/2014/01/30/simhash-shi-xian-xiang-jie.html
http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity2-html.html
