simHash是google提出的用于計(jì)算海量文本相似度的算法：
(1) 分詞 => word
(2) 單詞權(quán)重 tfidf word => (word, weight)
(3) 每個(gè)詞hash為指定長度的二進(jìn)制串， 如 10010 => (hash, weight)
(4) 所有詞加權(quán)合并 sum(hash * weight), 加權(quán)乘的時(shí)候把0當(dāng)做-1對待
(5) 降維： (4)得到文檔的向量， > 0映射 為 1 ， <=0 映射為0， 得到文檔的 二進(jìn)制向量，即文檔的simHash簽名
(6) 計(jì)算文檔間的漢明距離
漢明距離計(jì)算方式：
p1 = 100101
p2 = 101100
p3 = p1 XOR p2
i = 0
while(p3){
p3 &= p3 -1
i ++
}
simhash用于比較大的長文本, 可以取漢明距離為3， 對于短文本的效果比較差， 漢明距離可以取大一些進(jìn)行相似過濾
———————————————————————————-
算法過程很簡單，我們來理解一下原理，主要是參考自 http://www.cnblogs.com/hxsyl/p/4518506.html 。
假設(shè)詞匯總量是5， 那么我們用于標(biāo)記文檔唯一性的詞向量就是5維，文檔d=(1, 2, 0, 3, 0), 權(quán)值標(biāo)識該詞對d的重要程度，0表示沒有。詞的hash函數(shù)生成3byte二進(jìn)制串：
h(w1) = 101
h(w2) = 011
h(w3) = 100
h(w4) = 001
h(w5) = 110
特征矩陣(0 視為 -1)
| 1 | -1 | 1 |
|---|---|---|
| -1 | 1 | 1 |
| 1 | -1 | -1 |
| -1 | -1 | 1 |
| 1 | 1 | -1 |
因?yàn)槲臋n向量d(1, 2, 0, 3, 0) 是5維向量， 我們?nèi)√卣骶仃嚨牧邢蛄浚?/p>
v1 = 1 -1 1 -1 1
v2 = -1 1 -1 -1 -1
v3 = 1 1 -1 1 1
v1, v2, v3 看做5維空間的三個(gè)超平面，文檔d也是這個(gè)空間的一個(gè)平面， 現(xiàn)在我們想以v1, v2, v3為分割平面， 定位d的位置， 分別計(jì)算d與v1~v3超平面的夾角， 也就是算向量的點(diǎn)積， 點(diǎn)積大于0 標(biāo)記為1 ，點(diǎn)積小于等于0 標(biāo)記為0， 這樣：
d T v1 = -4 < 0 鈍角
d T v2 = -2 < 0 鈍角
d T v3 = 6 > 0 銳角
得到d的簽名=001，simHash的有效性這樣就比較清楚了， 就是利用這3個(gè)超平面來定位出文檔平面所在的位置，類似決策樹中的樹樁， 2^3 種分法，100萬的文檔， 理論上 20 byte簽名就可以區(qū)分， 10億的文檔需要30byte（30個(gè)超平面）
———————————————————————————-
假設(shè)我們庫中有5000萬(2^26)的文本， 每來一個(gè)新文本我們都需要做5000萬次的漢明距離計(jì)算， 這個(gè)計(jì)算量還是比較大的，假設(shè)簽名為64位。
考慮目標(biāo)文檔3位以內(nèi)變化的簽名有 C(64, 3) 4萬多可能， 然后 4萬 * 5000萬的hash查詢， 時(shí)間復(fù)雜度太大了
我們可以將庫中已有的5000萬文章的簽名表切成4個(gè)表， 分別存儲將64byte切開的ABCD四段中一段， 每進(jìn)來一篇新文章，同樣的分割為ABCD字段， 去與對應(yīng)的表精確匹配(這個(gè)過程可以設(shè)置4個(gè)并發(fā)比較)， 取每個(gè)表join后剩下的文檔ID， 大概每個(gè)表產(chǎn)出備選文檔ID 有5000萬/2^16 = 1000左右的量級，要找到5000萬文檔中和目標(biāo)文檔漢明距離小于3的文檔集， 那么庫中的文檔至少ABCD有一段和目標(biāo)文檔完全匹配，這樣我們最多會有 4 * 2 ^(26 -16) 篇備選文檔， 大概4000多次漢明距離的計(jì)算就可以了
參考：
http://grunt1223.iteye.com/blog/964564
http://www.cnblogs.com/hxsyl/p/4518506.html
http://blog.chinaunix.net/uid-25304914-id-4857313.htmlew
