# simhash算法 ## 方法介紹 ### 背景 如果某一天，面試官問你如何設計一個比較兩篇文章相似度的算法？可能你會回答幾個比較傳統點的思路： - 一種方案是先將兩篇文章分別進行分詞，得到一系列特征向量，然后計算特征向量之間的距離（可以計算它們之間的歐氏距離、海明距離或者夾角余弦等等），從而通過距離的大小來判斷兩篇文章的相似度。 - 另外一種方案是傳統hash，我們考慮為每一個web文檔通過hash的方式生成一個指紋（finger print）。 下面，我們來分析下這兩種方法。 - 采取第一種方法，若是只比較兩篇文章的相似性還好，但如果是海量數據呢，有著數以百萬甚至億萬的網頁，要求你計算這些網頁的相似度。你還會去計算任意兩個網頁之間的距離或夾角余弦么？想必你不會了。 - 而第二種方案中所說的傳統加密方式md5，其設計的目的是為了讓整個分布盡可能地均勻，但如果輸入內容一旦出現哪怕輕微的變化，hash值就會發生很大的變化。 舉個例子，我們假設有以下三段文本： - the cat sat on the mat - the cat sat on a mat - we all scream for ice cream 使用傳統hash可能會得到如下的結果： - irb(main):006:0> p1 = 'the cat sat on the mat' - irb(main):007:0> p1.hash => 415542861 - irb(main):005:0> p2 = 'the cat sat on a mat' - irb(main):007:0> p2.hash => 668720516 - irb(main):007:0> p3 = 'we all scream for ice cream' - irb(main):007:0> p3.hash => 767429688 " 可理想當中的hash函數，需要對幾乎相同的輸入內容，產生相同或者相近的hash值，換言之，hash值的相似程度要能直接反映輸入內容的相似程度，故md5等傳統hash方法也無法滿足我們的需求。 ### 出世 車到山前必有路，來自于GoogleMoses Charikar發表的一篇論文“detecting near-duplicates for web crawling”中提出了simhash算法，專門用來解決億萬級別的網頁的去重任務。 simhash作為locality sensitive hash（局部敏感哈希）的一種： - 其主要思想是降維，將高維的特征向量映射成低維的特征向量，通過兩個向量的Hamming Distance來確定文章是否重復或者高度近似。 - 其中，Hamming Distance，又稱漢明距離，在信息論中，兩個等長字符串之間的漢明距離是兩個字符串對應位置的不同字符的個數。也就是說，它就是將一個字符串變換成另外一個字符串所需要替換的字符個數。例如：1011101 與 1001001 之間的漢明距離是 2。至于我們常說的字符串編輯距離則是一般形式的漢明距離。 如此，通過比較多個文檔的simHash值的海明距離，可以獲取它們的相似度。 ### 流程 simhash算法分為5個步驟：分詞、hash、加權、合并、降維，具體過程如下所述： - 分詞 - 給定一段語句，進行分詞，得到有效的特征向量，然后為每一個特征向量設置1-5等5個級別的權重（如果是給定一個文本，那么特征向量可以是文本中的詞，其權重可以是這個詞出現的次數）。例如給定一段語句：“CSDN博客結構之法算法之道的作者July”，分詞后為：“CSDN 博客 結構 之 法 算法 之 道 的 作者 July”，然后為每個特征向量賦予權值：CSDN(4) 博客(5) 結構(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5)，其中括號里的數字代表這個單詞在整條語句中的重要程度，數字越大代表越重要。 - hash - 通過hash函數計算各個特征向量的hash值，hash值為二進制數01組成的n-bit簽名。比如“CSDN”的hash值Hash(CSDN)為100101，“博客”的hash值Hash(博客)為“101011”。就這樣，字符串就變成了一系列數字。 - 加權 - 在hash值的基礎上，給所有特征向量進行加權，即W = Hash * weight，且遇到1則hash值和權值正相乘，遇到0則hash值和權值負相乘。例如給“CSDN”的hash值“100101”加權得到：W(CSDN) = 100101*4 = 4 -4 -4 4 -4 4，給“博客”的hash值“101011”加權得到：W(博客)=101011*5 = 5 -5 5 -5 5 5，其余特征向量類似此般操作。 - 合并 - 將上述各個特征向量的加權結果累加，變成只有一個序列串。拿前兩個特征向量舉例，例如“CSDN”的“4 -4 -4 4 -4 4”和“博客”的“5 -5 5 -5 5 5”進行累加，得到“4+5 -4+-5 -4+5 4+-5 -4+5 4+5”，得到“9 -9 1 -1 1”。 - 降維 - 對于n-bit簽名的累加結果，如果大于0則置1，否則置0，從而得到該語句的simhash值，最后我們便可以根據不同語句simhash的海明距離來判斷它們的相似度。例如把上面計算出來的“9 -9 1 -1 1 9”降維（某位大于0記為1，小于0記為0），得到的01串為：“1 0 1 0 1 1”，從而形成它們的simhash簽名。 其流程如下圖所示：  ### 應用 - 每篇文檔得到SimHash簽名值后，接著計算兩個簽名的海明距離即可。根據經驗值，對64位的 SimHash值，海明距離在3以內的可認為相似度比較高。 - 海明距離的求法：異或時，只有在兩個比較的位不同時其結果是1 ，否則結果為0，兩個二進制“異或”后得到1的個數即為海明距離的大小。 舉個例子，上面我們計算到的“CSDN博客”的simhash簽名值為“1 0 1 0 1 1”，假定我們計算出另外一個短語的簽名值為“1 0 1 0 0 0”，那么根據異或規則，我們可以計算出這兩個簽名的海明距離為2，從而判定這兩個短語的相似度是比較高的。 換言之，現在問題轉換為：對于64位的SimHash值，我們只要找到海明距離在3以內的所有簽名，即可找出所有相似的短語。 但關鍵是，如何將其擴展到海量數據呢？譬如如何在海量的樣本庫中查詢與其海明距離在3以內的記錄呢？ - 一種方案是查找待查詢文本的64位simhash code的所有3位以內變化的組合 - 大約需要四萬多次的查詢。 - 另一種方案是預生成庫中所有樣本simhash code的3位變化以內的組合 - 大約需要占據4萬多倍的原始空間。 這兩種方案，要么時間復雜度高，要么空間復雜度復雜，能否有一種方案可以達到時空復雜度的絕佳平衡呢？答案是肯定的： - 我們可以把 64 位的二進制simhash簽名均分成4塊，每塊16位。根據鴿巢原理（也稱抽屜原理），如果兩個簽名的海明距離在 3 以內，它們必有一塊完全相同。如下圖所示：  - 然后把分成的4 塊中的每一個塊分別作為前16位來進行查找，建倒排索引。 具體如下圖所示：  如此，如果樣本庫中存有2^34（差不多10億）的simhash簽名，則每個table返回2^(34-16)=262144個候選結果，大大減少了海明距離的計算成本。 - 假設數據是均勻分布，16位的數據，產生的像限為2^16個，則平均每個像限分布的文檔數則為2^34/2^16 = 2^(34-16)) ，四個塊返回的總結果數為 4* 262144 （大概 100 萬）。 - 這樣，原本需要比較10億次，經過索引后，大概只需要處理100萬次。 （部分內容及圖片參考自：http://grunt1223.iteye.com/blog/964564 ，后續圖片會全部重畫） ## 問題實例 待續。 @復旦李斌：simhash不是google發明的，是princeton的人早在stoc02上發表的。google在www07上的那篇論文只是在網頁查重上應用了下。事實上www07中的算法是stoc02中隨機超平面的一個極其巧妙的實現，bit差異的期望正好等于原姶向量的余弦。