????????傳統(tǒng)的hash?算法只負(fù)責(zé)將原始內(nèi)容盡量均勻隨機(jī)地映射為一個簽名值，原理上相當(dāng)于偽隨機(jī)數(shù)產(chǎn)生算法。產(chǎn)生的兩個簽名，如果相等，說明原始內(nèi)容在一定概 率下是相等的；如果不相等，除了說明原始內(nèi)容不相等外，不再提供任何信息，因?yàn)榧词乖純?nèi)容只相差一個字節(jié)，所產(chǎn)生的簽名也很可能差別極大。從這個意義 上來說，要設(shè)計一個?hash?算法，對相似的內(nèi)容產(chǎn)生的簽名也相近，是更為艱難的任務(wù)，因?yàn)樗暮灻党颂峁┰純?nèi)容是否相等的信息外，還能額外提供不相等的原始內(nèi)容的差異程度的信息。

????????而Google?的?simhash?算法產(chǎn)生的簽名，可以用來比較原始內(nèi)容的相似度時，便很想了解這種神奇的算法的原理。出人意料，這個算法并不深奧，其思想是非常清澈美妙的。

Simhash算法

simhash算法的輸入是一個向量，輸出是一個?f?位的簽名值。為了陳述方便，假設(shè)輸入的是一個文檔的特征集合，每個特征有一定的權(quán)重。比如特征可以是文檔中的詞，其權(quán)重可以是這個詞出現(xiàn)的次數(shù)。?simhash?算法如下：

1，將一個?f?維的向量?V?初始化為?0?；?f?位的二進(jìn)制數(shù)?S?初始化為?0?；

2，對每一個特征：用傳統(tǒng)的?hash?算法對該特征產(chǎn)生一個?f?位的簽名?b?。對?i=1?到?f?：

如果b?的第?i?位為?1?，則?V?的第?i?個元素加上該特征的權(quán)重；

否則，V?的第?i?個元素減去該特征的權(quán)重。

3，如果?V?的第?i?個元素大于?0?，則?S?的第?i?位為?1?，否則為?0?；

4，輸出?S?作為簽名。

算法幾何意義和原理

這個算法的幾何意義非常明了。它首先將每一個特征映射為f?維空間的一個向量，這個映射規(guī)則具體是怎樣并不重要，只要對很多不同的特征來說，它們對所對應(yīng)的向量是均勻隨機(jī)分布的，并且對相同的特征來說對應(yīng)的向量是唯一的就行。比如一個特征的?4?位?hash?簽名的二進(jìn)制表示為?1010?，那么這個特征對應(yīng)的?4?維向量就是?(1,-1,1,-1)?T?，即hash?簽名的某一位為?1?，映射到的向量的對應(yīng)位就為?1?，否則為?-1?。然后，將一個文檔中所包含的各個特征對應(yīng)的向量加權(quán)求和，加權(quán)的系數(shù)等于該特征的權(quán)重。

得到的和向量即表征了這個文檔，我們可以用向量之間的夾角來衡量對應(yīng)文檔之間的相似度。最后，為了得到一個?f?位的簽名，需要進(jìn)一步將其壓縮，如果和向量的某一維大于?0?，則最終簽名的對應(yīng)位為?1?，否則為?0?。這樣的壓縮相當(dāng)于只留下了和向量所在的象限這個信息，而?64?位的簽名可以表示多達(dá)?2?64?個象限，因此只保存所在象限的信息也足夠表征一個文檔了。

比較相似度

海明距離：?兩個碼字的對應(yīng)比特取值不同的比特數(shù)稱為這兩個碼字的海明距離。一個有效編碼集中,?任意兩個碼字的海明距離的最小值稱為該編碼集的海明距離。舉例如下：?10101?和?00110?從第一位開始依次有第一位、第四、第五位不同，則海明距離為?3.

異或：?只有在兩個比較的位不同時其結(jié)果是1?，否則結(jié)果為?0

對每篇文檔根據(jù)SimHash?算出簽名后，再計算兩個簽名的海明距離（兩個二進(jìn)制異或后?1?的個數(shù)）即可。根據(jù)經(jīng)驗(yàn)值，對?64?位的?SimHash?，海明距離在?3?以內(nèi)的可以認(rèn)為相似度比較高。

假設(shè)對64?位的?SimHash?，我們要找海明距離在?3?以內(nèi)的所有簽名。我們可以把?64?位的二進(jìn)制簽名均分成?4塊，每塊?16?位。根據(jù)鴿巢原理（也成抽屜原理，見組合數(shù)學(xué)），如果兩個簽名的海明距離在?3?以內(nèi)，它們必有一塊完全相同。

我們把上面分成的4?塊中的每一個塊分別作為前?16?位來進(jìn)行查找。?建立倒排索引。

如果庫中有2^34?個（大概?10?億）簽名，那么匹配上每個塊的結(jié)果最多有?2^(34-16)=262144?個候選結(jié)果?(假設(shè)數(shù)據(jù)是均勻分布，?16?位的數(shù)據(jù)，產(chǎn)生的像限為?2^16?個，則平均每個像限分布的文檔數(shù)則?2^34/2^16=2^(34-16))?，四個塊返回的總結(jié)果數(shù)為4*262144?（大概?100?萬）。原本需要比較?10?億次，經(jīng)過索引，大概就只需要處理?100?萬次了。由此可見，確實(shí)大大減少了計算量。