背景
提升產品體驗，節省用戶感知度。——想想，如果看到一堆相似性很高的新聞，對于用戶的留存會有很大的影響。
技術方案1、信息指紋算法
思路：為每個網頁計算出一組信息指紋(Fingerprint)。比較兩個網頁相同信息指紋數量，從而判斷內容的重疊性。
步驟：
1）提取網頁正文信息特征（通常是一組詞），并進行向量化處理（權重算法：如nf/df）。
2）取前N個信息特征，進行MD5哈希，得到信息指紋。 優點：算法簡單、工程好落地，不會受大數量問題影響。
技術方案2、分段簽名算法
算法思路：按規則把網頁切成N段，為每一段生成信息指紋。如果這N個信息指紋里面，有M個（閾值）相同， 則認為兩者是復制網頁。
缺點：小規模比較是很好的算法，對于大規模數據來說，算法復雜度相當高。
方案3、基于關鍵詞的復制網頁算法
方案4、基于句子的方式
算法思路：獲取標點符號左右兩邊各2個漢子或英文作為特征，來進行文本表示。
SimHash：局部敏感哈希(locality sensitive hash)
背景介紹：simhash是由 Charikar 在2002年提出來的！
算法思路：主要思想是降維，為每個文檔通過hash的方式，生成一個指紋（fingerprint)。
核心思想是將文本相似性問題轉換為集合的相似性問題!
設計的目的：是讓整個分布盡可能地均勻，形似的內容生成相近的hashcode。——即，hashcode的相似程度要
能直接反應輸入內容的相似程度（所以md5等傳統hash無法滿足需求）。
使用方：Google基于此算法實現網頁文件查重。
優點：相對傳統文本相似性方法（歐氏距離、海明距離、余弦角度），解決計算量龐大等問題。
缺點：500字以上效果比較明顯500字以內，效果不是很理想，可以調整海明距離的n值來調整（3升級為10）
1）分詞：提取網頁正文信息特征詞，形成去掉噪音詞(助詞、語氣詞、人稱代詞)的單詞序列，并為每個詞加上權重（詞出現次數）。
抽取方式：
1.1. 剔除所有英文、數字、標點字符
1.2.分詞，并標注詞性，僅保留實體詞性，如名詞、動詞；（技巧一！）
1.3.過濾掉常用實體詞（常用實體詞是通過對歷史銳推訓練而得，即建立自己的停止詞表）；（技巧二！）
1.4.計算保留實體詞的詞頻，并以此為權重，選擇權重大的詞語作為標簽；
1.5.標簽數組長度大于一個閾值（如3），才認為是有信息量的銳推，否則忽略。（技巧三！）
—其他簡單方案：
百度大搜的去重算法比較簡單，就是直接找出此文章的最長的n句話，做一遍hash簽名。n一般取3。
工程實現巨簡單，據說準確率和召回率都能到達80%以上。
2）hash及加權：
對于提取的信息特征詞進行hash值運算，轉變成bit值，根據每個位是否為1，進行權重加減處理。
權重設定：詞頻+詞位置
3）合并及降維：每個單詞的序列值累加，變成只有一個序列串。大于0 記為1，小于0記為0.
1、海明距離閾值選擇
模型效果：標題閾值、內容閾值
距離選擇，考慮因素：除考慮數據效果之外，還得考慮工程查詢效率。
2、提高性能的方式：
把64為simHash碼均分為漢明距離n+1塊，方便后續查找所有臨近simHash碼。
SimHash 海明 (Hamming)距離（一）
第一種是方案是查找待查詢文本的64位simhash code的所有3位以內變化的組合，大約需要四萬多次的查詢，參考下圖：
SimHash 海明 (Hamming)距離（二）
第二種方案是預生成庫中所有樣本simhash code的3位變化以內的組合，大約需要占據4萬多倍的原始空間，參考下圖
SimHash 海明 (Hamming)距離一、二方案分析
上述兩種方法，或者時間復雜度，或者空間復雜度，其一無法滿足實際的需求。我們需要一種方法，其時間復雜度優于前者，空間復雜度優于后者。
假設我們要尋找海明距離3以內的數值，根據抽屜原理，只要我們將整個64位的二進制串劃分為4塊，無論如何，匹配的兩個simhash code之間至少有一塊區域是完全相同的，如圖所示
SimHash 海明 (Hamming)距離(三)
由于我們無法事先得知完全相同的是哪一塊區域，因此我們必須采用存儲多份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的數量與每個table返回的結果呈此消彼長的關系，也就是說，時間效率與空間效率不可兼得!
這就是Google每天所做的，用來識別獲取的網頁是否與它龐大的、數以十億計的網頁庫是否重復。另外，simhash還可以用于信息聚類、文件壓縮等。
SimHash 算法原理
simhash用于比較大文本，比如500字以上效果都還蠻好，距離小于3的基本都是相似，誤判率也比較低。但是如果我們處理的是微博信息，最多也就140個字，使用simhash的效果并不那么理想。看如下圖，在距離為3時是一個比較折中的點，在距離為10時效果已經很差了，不過我們測試短文本很多看起來相似的距離確實為10。如果使用距離為3，短文本大量重復信息不會被過濾，如果使用距離為10，長文本的錯誤率也非常高，如何解決？——采用分段函數!
SimHash 算法原理——評估結果
1、dump 一天的新聞數據：
數據項要求：標題、內容、新聞原始地址。
2、評估指標
排重準確率（97%）：
數據集：排重新聞集
方式：人工（研發先評估、產品評估）
召回率（75%）：
數據集：訓練數據集-排重新聞集
方式：擴大海明距離，再進行人工評估
SimHash 算法原理——代碼片段
高效計算二進制序列中1的個數:這個函數來計算的話，時間復雜度是 O(n); 這里的n默認取值為3。由此可見還是蠻高效的。
參考資料
中文文檔simhash值計算
網頁文本的排重算法介紹
海量數據相似度計算之simhash和海明距離
短文本合并重復（去重）的簡單有效做法
海明距離查詢方案
浙公網安備 33010602011771號