【深度好文】simhash文本去重流程

    對於類似於頭條客戶端而言,推薦的每一刷的新聞都必須是不同的新聞,這就需要對新聞文本進行排重。傳統的去重一般是對文章的url鏈接進行排重,但是對於抓取的網頁來說,各大平臺的新聞可能存在重復,對於隻通過文章url進行排重是不靠譜的,為瞭解決這個痛點於是就提出瞭用simhash來解決這個難題。


1.簡介

    傳統的Hash算法隻負責將原始內容盡量均勻隨機地映射為一個簽名值,原理上僅相當於偽隨機數產生算法。即便是兩個原始內容隻相差一個字節,所產生的簽名也很可能差別很大,所以傳統的Hash是無法在簽名的維度上來衡量原內容的相似度。而SimHash本身屬於一種局部敏感hash,其主要思想是降維,將高維的特征向量轉化成一個f位的指紋(fingerprint),通過算出兩個指紋的海明距離(hamming distince)來確定兩篇文章的相似度,海明距離越小,相似度越低(根據 Detecting Near-Duplicates for Web Crawling 論文中所說),一般海明距離為3就代表兩篇文章相同。     

simhash也有其局限性,在處理小於500字的短文本時,simhash的表現並不是很好,所以在使用simhash前一定要註意這個細節。

2.背景

如何設計一個比較兩篇文章相似度的算法?可能你會回答幾個比較傳統點的思路:

  • 一種方案是先將兩篇文章分別進行分詞,得到一系列特征向量,然後計算特征向量之間的距離(可以計算它們之間的歐氏距離、海明距離或者夾角餘弦等等),從而通過距離的大小來判斷兩篇文章的相似度。
  • 另外一種是傳統hash,我們考慮為每一個web文檔通過hash的方式生成一個指紋(finger print)。

下面我們來分析一下這兩種方法:

  • 采取第一種方法,若是隻比較兩篇文章的相似性還好,但如果是海量數據呢,有著數以百萬甚至億萬的網頁,要求你計算這些網頁的相似度。你還會去計算任意兩個網頁之間的距離或夾角餘弦麼?那樣做的話時間復雜度,空間復雜度可想而知。
  • 而第二種方案中所說的傳統加密方式md5,其設計的目的是為瞭讓整個分佈盡可能地均勻,但如果輸入內容一旦出現哪怕輕微的變化,hash值就會發生很大的變化。

3.simhash與hash算法的區別

    傳統Hash算法隻負責將原始內容盡量均勻隨機地映射為一個簽名值,原理上僅相當於偽隨機數產生算法。傳統hash算法產生的兩個簽名,如果不相等,除瞭說明原始內容不相等外,不再提供任何信息,因為即使原始內容隻相差一個字節,所產生的簽名也很可能差別很大,所以傳統Hash是無法在簽名的維度上來衡量原內容的相似度。而SimHash本身屬於一種局部敏感哈希算法,它產生的hash簽名在一定程度上可以表征原內容的相似度。     我們主要解決的是文本相似度計算,要比較的是兩個文章是否相似,當然我們降維生成瞭hash簽名也是用於這個目的。看到這裡,估計大傢就明白瞭,即使把文章中的字符串變成 01 串,我們使用的simhash算法也還是可以用於計算相似度,而傳統的hash卻不行。我們可以來做個測試,兩個相差隻有一個字符的文本串,“你媽媽喊你回傢吃飯哦,回傢羅回傢羅” 和 “你媽媽叫你回傢吃飯啦,回傢羅回傢羅”。

4.simhash原理

算法過程大致如下:

  1. 對文本分詞,得到N維特征向量(默認為64維)
  2. 為分詞設置權重(tf-idf)
  3. 為特征向量計算哈希
  4. 對所有特征向量加權,累加(目前僅進行非加權累加)
  5. 對累加結果,大於零置一,小於零置零
  6. 得到文本指紋(fingerprint)

具體流程實現

simhash的算法具體分為5個步驟:分詞、hash、加權、合並、降維,具體過程如下:

1.分詞

  • 給定一段語句或者一段文本,進行分詞,得到有效的特征向量,然後為每一個特征向量設置一個5個級別(1—5)權值。例如給定一段語句:“生活本沒有路,走的人多瞭就成瞭路,要相信陽光總在風雨後”,分詞後結果為:生活 沒有 成瞭 相信 陽光 風雨,然後為每個特征向量賦予權值: 生活(5) 沒有(2) 成瞭(1) 相信(2) 陽光(3) 風雨(2),其中括號裡的數字代表這個單詞在整條語句中的重要程度,數字越大代表越重要。

2.hash

  • 通過hash函數計算各個特征向量的hash值,hash值為二進制數01組成的n-bit簽名。比如“生活”的hash值Hash(生活)為110101,“沒有”的hash值Hash(沒有)為“101001”。就這樣,字符串就變成瞭一系列數字。

3.加權

  • 在hash值的基礎上,給所有特征向量進行加權,即W = Hash * weight,且遇到1則hash值和權值正相乘,遇到0則hash值和權值負相乘。例如給“生活”的hash值“110101”加權得到:W(生活) = 110101 5 = 5 5 -5 5 -5 5,給“沒有”的hash值“101001”加權得到:W(沒有)=101001 2 = 2 -2 2 -2 -2 2,其餘特征向量類似此般操作。

4.合並

  • 將上述各個特征向量的加權結果累加,變成隻有一個序列串。拿前兩個特征向量舉例,例如“生活”的“5 5 -5 5 -5 5”和“沒有”的“2 -2 2 -2 -2 2”進行累加,得到“5+2 5-2 -5+2 5-2 -5-2 5+2”,得到“7 3 -3 3 -7 7”。

5.降維

  • 對於n-bit簽名的累加結果,如果大於0則置1,否則置0,從而得到該語句的simhash值,最後我們便可以根據不同語句simhash的海明距離來判斷它們的相似度。例如把上面計算出來的“9 -9 1 -1 1 9”降維(某位大於0記為1,小於0記為0),得到的01串為:“1 1 0 1 0 1”,從而形成它們的simhash簽名。

整個過程的流程圖為:

5、simhash的簽名距離計算

    我們把庫裡的文本都轉換為simhash簽名,並轉換為long類型存儲,空間大大減少。現在我們雖然解決瞭空間,但是如何計算兩個simhash的相似度呢?難道是比較兩個simhash的01有多少個不同嗎?對的,其實也就是這樣,我們通過海明距離(Hamming distance)就可以計算出兩個simhash到底相似不相似。兩個simhash對應二進制(01串)取值不同的數量稱為這兩個simhash的海明距離。舉例如下: 10101 和 00110 從第一位開始依次有第一位、第四、第五位不同,則海明距離為3。對於二進制字符串的a和b,海明距離為等於在a XOR b運算結果中1的個數(普遍算法)。

    我們可以把 64 位的二進制simhash簽名均分成4塊,每塊16位。根據鴿巢原理(也稱抽屜原理),如果兩個簽名的海明距離在 3 以內,它們必有一塊完全相同。如下圖所示:

6、simhash的存儲和查找

  1. 我們需要將64位simhash均分為4份,然後每份作為key存儲到redis
  2. 采用精確匹配的方式查找前16位
  3. 找到則拿出來計算與被比較的simahsh距離,小於3則判斷為相似(當然具體問題具體分析,這個值可以調整)
  4. 如果樣本庫中存有2^34(差不多10億)的哈希指紋,則每個table返回2^(34-16)=262144個候選結果,大大減少瞭海明距離的計算成本

7、聊聊Jaccard相似度與漢明距離

7.1 Jaccard相似度

     Jaccard 系數,又叫Jaccard相似性系數,用來比較樣本集中的相似性和分散性的一個概率。 公式:

給定兩個集合A,B jaccard 系數定義為A與B交集的大小與並集大小的比值,jaccard值越大說明相似度越高

7.2 漢明距離

    在信息理論中,Hamming Distance 表示兩個等長字符串在對應位置上不同字符的數目,我們以d(x, y)表示字符串x和y之間的漢明距離。從另外一個方面看,漢明距離度量瞭通過替換字符的方式將字符串x變成y所需要的最小的替換次數。

舉例說明以下字符串間的漢明距離為:

  • "karolin" and "kathrin" is 3.
  • "karolin" and "kerstin" is 3.
  • 1011101 and 1001001 is 2.
  • 2173896 and 2233796 is 3.

8、【實戰】新聞文本去重服務詳細流程

上面陸陸續續講瞭這麼多理論知識想必大傢也是一頭霧水,接下來我們通過實戰來講述整體流程。

本文將文本排重做成瞭一個接口,首先給去重接口傳一些必要的參數,針對新聞文本為例(url:鏈接 title:文本標題 content:內容)。依次是進行url排重、title排重、content排重,如果三種都沒有找到,則建立url、title、content索引存儲到redis。具體流程圖如下:

8.1、URL排重

1.建立URL索引:

key: url_index_name+"_"+urlMD5。url_index_name為索引名字,urlMD5表示url的MD5值
value: docId+"t"+url+"t"+storageTime。 docId為新聞的事件id,url表示新聞鏈接,storageTime表示存入redis的時間戳

赞(0)