如何分析SimHash與重復信息識別

今天就跟大家聊聊有關如何分析SimHash與重復信息識別，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

隨著信息爆炸時代的來臨，互聯(lián)網(wǎng)上充斥著著大量的近重復信息，有效地識別它們是一個很有意義的課題。例如，對于搜索引擎的爬蟲系統(tǒng)來說，收錄重復的網(wǎng)頁是毫無意義的，只會造成存儲和計算資源的浪費；同時，展示重復的信息對于用戶來說也并不是最好的體驗。造成網(wǎng)頁近重復的可能原因主要包括： 

• 鏡像網(wǎng)站

• 內(nèi)容復制

• 嵌入廣告

• 計數(shù)改變

• 少量修改

一個簡化的爬蟲系統(tǒng)架構如下圖所示： 

事實上，傳統(tǒng)比較兩個文本相似性的方法，大多是將文本分詞之后，轉化為特征向量距離的度量，比如常見的歐氏距離、海明距離或者余弦角度等等。兩兩比較固然能很好地適應，但這種方法的一個最大的缺點就是，無法將其擴展到海量數(shù)據(jù)。例如，試想像Google那種收錄了數(shù)以幾十億互聯(lián)網(wǎng)信息的大型搜索引擎，每天都會通過爬蟲的方式為自己的索引庫新增的數(shù)百萬網(wǎng)頁，如果待收錄每一條數(shù)據(jù)都去和網(wǎng)頁庫里面的每條記錄算一下余弦角度，其計算量是相當恐怖的。 

我們考慮采用為每一個web文檔通過hash的方式生成一個指紋（fingerprint）。傳統(tǒng)的加密式hash，比如md5，其設計的目的是為了讓整個分布盡可能地均勻，輸入內(nèi)容哪怕只有輕微變化，hash就會發(fā)生很大地變化。我們理想當中的哈希函數(shù)，需要對幾乎相同的輸入內(nèi)容，產(chǎn)生相同或者相近的hashcode，換句話說，hashcode的相似程度要能直接反映輸入內(nèi)容的相似程度。很明顯，前面所說的md5等傳統(tǒng)hash無法滿足我們的需求。 

simhash是locality sensitive hash（局部敏感哈希）的一種，最早由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出。Google就是基于此算法實現(xiàn)網(wǎng)頁文件查重的。我們假設有以下三段文本： 

• 
  

• the cat sat on the mat

• the cat sat on a mat

• we all scream for ice cream

使用傳統(tǒng)hash可能會產(chǎn)生如下的結果： 

引用

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會應該產(chǎn)生類似如下的結果： 

引用

irb(main):003:0> p1.simhash 
=> 851459198 
00110010110000000011110001111110 

irb(main):004:0> p2.simhash 
=> 847263864 
00110010100000000011100001111000 

irb(main):002:0> p3.simhash 
=> 984968088 
00111010101101010110101110011000

海明距離的定義，為兩個二進制串中不同位的數(shù)量。上述三個文本的simhash結果，其兩兩之間的海明距離為(p1,p2)=4，(p1,p3)=16以及(p2,p3)=12。事實上，這正好符合文本之間的相似度，p1和p2間的相似度要遠大于與p3的。 

如何實現(xiàn)這種hash算法呢？以上述三個文本為例，整個過程可以分為以下六步： 
1、選擇simhash的位數(shù)，請綜合考慮存儲成本以及數(shù)據(jù)集的大小，比如說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、使用傳統(tǒng)的32位hash函數(shù)計算各個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以內(nèi)的文本都可以認為是近重復文本。當然，具體數(shù)值需要結合具體業(yè)務以及經(jīng)驗值來確定。 
  
使用上述方法產(chǎn)生的simhash可以用來比較兩個文本之間的相似度。問題是，如何將其擴展到海量數(shù)據(jù)的近重復檢測中去呢？譬如說對于64位的待查詢文本的simhash code來說，如何在海量的樣本庫（>1M）中查詢與其海明距離在3以內(nèi)的記錄呢？下面在引入simhash的索引結構之前，先提供兩種常規(guī)的思路。第一種是方案是查找待查詢文本的64位simhash code的所有3位以內(nèi)變化的組合，大約需要四萬多次的查詢，參考下圖： 
另一種方案是預生成庫中所有樣本simhash code的3位變化以內(nèi)的組合，大約需要占據(jù)4萬多倍的原始空間，參考下圖： 

顯然，上述兩種方法，或者時間復雜度，或者空間復雜度，其一無法滿足實際的需求。我們需要一種方法，其時間復雜度優(yōu)于前者，空間復雜度優(yōu)于后者。 

假設我們要尋找海明距離3以內(nèi)的數(shù)值，根據(jù)抽屜原理，只要我們將整個64位的二進制串劃分為4塊，無論如何，匹配的兩個simhash code之間至少有一塊區(qū)域是完全相同的，如下圖所示： 

由于我們無法事先得知完全相同的是哪一塊區(qū)域，因此我們必須采用存儲多份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的數(shù)量與每個table返回的結果呈此消彼長的關系，也就是說，時間效率與空間效率不可兼得，參看下圖： 

事實上，這就是Google每天所做的，用來識別獲取的網(wǎng)頁是否與它龐大的、數(shù)以十億計的網(wǎng)頁庫是否重復。另外，simhash還可以用于信息聚類、文件壓縮等。 

看完上述內(nèi)容，你們對如何分析SimHash與重復信息識別有進一步的了解嗎？如果還想了解更多知識或者相關內(nèi)容，請關注億速云行業(yè)資訊頻道，感謝大家的支持。