Simhash在內容去重中的應用，你學會了嗎？
一、背景
信息流個性化推薦場景中依賴爬蟲抓取的海量新聞庫，這些新聞中不乏互相抄襲的新聞，這些內容相似的文章，會造成內容的同質化并加重數據庫的存儲負擔，更糟糕的是降低了信息流內容的體驗。所以需要一種準確高效的文本去重算法。而最樸素的做法就是將所有文本進行兩兩比較，簡單易理解，最符合人類的直覺，這種做法對于少量文本來說，實現起來很方便，但是對于海量文本來說是行不通的，所以應在盡可能保證準確性的同時，降低算法的時間復雜度。事實上，傳統比較兩個文本相似性的方法，大多是將文本分詞之后，轉化為特征向量距離的度量，比如常見的歐氏距離、海明距離或者余弦角度等等。下面以余弦相似度和simhash算法為例做簡單介紹。
1.1 余弦相似度
余弦相似度的核心思想是計算兩個向量的夾角余弦值來判斷兩個句子的相似度，以下面兩個句子為例：
第一步分詞：
句子A：我/喜歡/看/電視，不/喜歡/看/電影
句子B：我/不/喜歡/看/電視，也/不/喜歡/看/電影
第二步列出所有詞：
我，喜歡，看，電視，電影，不，也
第三步計算詞頻：
句子A：我1，喜歡2，看2，電視1，電影1，不1，也0
句子B：我1，喜歡2，看2，電視1，電影1，不2，也1
第四步，寫出詞向量：
句子A：[1,2,2,1,1,1,0]
句子B：[1,2,2,1,1,2,1]
到這里就可以將兩個句子的相似度轉換為兩個向量的相似度，我們可以把這兩個句子想象為空間中的兩條線段，都是從原點[0,0,0...]出發，指向不同的方向，兩條線段形成一個夾角，如果夾角為0，意味著方向相同線段重合，如果夾角為90度意味著形成直角，完全不相似，因此我們可以通過夾角來判斷相似度，夾角越小就代表越相似。
余弦相似度得到的結果較為精確，但當面對大量文本時，計算文本向量的時間復雜度很高，這可能會影響性能。
1.2 simHash算法
simHash是谷歌提出來的一套用于文本去重的算法，將文本映射為一個01串，并且保證相似文本哈希之后得到的01串也是相似的，只在少數幾個位置上的0和1不一樣。為了表征原始文本的相似度，可以計算兩個01串之間在多少個位置上不同，這便是漢明距離，用來表征simHash算法下兩個文本之間的相似度，通常來說，越相似的文本，對應simHash映射得到的01串之間的漢明距離越小。舉例：t1=“直擊兒科急診現狀忙碌不止 兒科接診進行時 ”t2=“兒科急診現狀直擊不停忙碌 兒科接診進行時 ”;可以看到，上面這兩個字符串雖然只有幾個字不同，但是通過簡單的Hash算法得到的hash值可能就完全不一樣了，因而無法利用得到的hash值來表征原始文本的相似性。然而通過simHash算法的映射后，得到的simHash值便是如下：
圖片
這兩個文本生成的兩個64位的01串只有標紅的3個位置不同。通常來說，用于相似文本檢測中的漢明距離判斷標準就是3，也就是說，當兩個文本對應的simHash之間的漢明距離小于或等于3，則認為這兩個文本為相似，如果是要去重的話，就只能留下其中一個。
下圖為在各種漢明距離的情況下simhash算法的準確和召回率變化趨勢，可以看到在漢明距離為3時能夠達到較好的平衡：
圖片
相比計算余弦相似度，simhash算法可以快速計算文本的哈希值，而且能夠在哈希值之間計算漢明距離，從而衡量文本的相似度。simhash算法的優點是它能夠快速處理大量文本，并且可以識別并過濾掉文本中的噪聲和重復內容。
二、simhash實現步驟
1、分詞，把需要判重的文本分詞，形成去掉噪音詞的單詞序列并為每個詞加上權重。我們假設權重分為5個級別（1~5）。比如：“ 美國“51區”雇員稱內部有9架飛碟，曾看見灰色外星人 ” ==> 分詞后為 “ 美國（4） 51區（5） 雇員（3） 稱（1） 內部（2） 有（1） 9架（3） 飛碟（5） 曾（1） 看見（3） 灰色（4） 外星人（5）”，括號里的權重代表重要程度，數字越大越重要，這里我們采用ansj分詞器，tf-idf的方式計算權重。生成一個詞和對應權重的map。
public static List\<String\> splitWords(String str) {
List\<String\> splitWords = new ArrayList\<String\>(1000);
Result terms = ToAnalysis.parse(str, forest);
for (int i = 0; i \< terms.size(); i++) {
Term term = terms.get(i);
String word = term.getName();
if (!"".equals(word.trim()) && !stopWords.contains(word)) {
splitWords.add(word);
}
}
return splitWords;
}
public Map\<String, Double\> extract(String str) {
List\<String\> words = WordsSegment.splitWords(str);
// 計算詞頻tf
int initialCapacity = Math.*max*((int) Math.*ceil*(words.size() / 0.75) + 1, 16);
Map\<String, Double\> wordmap = new HashMap\<String, Double\>(initialCapacity);
for (String word : words) {
if (!wordmap.containsKey(word)) {
wordmap.put(word, 1.0);
} else {
wordmap.put(word, wordmap.get(word) + 1);
}
}
Iterator\<Entry\<String, Double\>\> it = wordmap.entrySet().iterator();
while (it.hasNext()) {
Entry\<String, Double\> item = (Entry\<String, Double\>) it.next();
String word = item.getKey();
if (stopWords.contains(word) \|\| word.length() \< 2) {
it.remove();
continue;
}
// 計算權重idf
if (idfMap.containsKey(word)) {
double idf = wordmap.get(word) \* idfMap.get(word);
wordmap.put(word, idf);
} else {
double idf = wordmap.get(word) \* idfAverage;
wordmap.put(word, idf);
}
}
return wordmap;
}2、hash，通過hash算法把每個詞變成hash值，比如“美國”通過hash算法計算為 100101,“51區”通過hash算法計算為 101011。這樣我們的字符串就變成了一串串數字，還記得文章開頭說過的嗎，要把文章變為數字計算才能提高相似度計算性能，現在是降維過程進行時。
public static BigInteger fnv1aHash64(String str) {
BigInteger hash = FNV_64_INIT;
int len = str.length();
for (int i = 0; i \< len; i++) {
hash = hash.xor(BigInteger.valueOf(str.charAt(i)));
hash = hash.multiply(FNV_64_PRIME);
}
hash = hash.and(MASK_64);
return hash;
}3、加權，通過2步驟的hash生成結果，需要按照單詞的權重形成加權數字串，比如“美國”的hash值為“100101”，通過加權計算為“4 -4 -4 4 -4 4”；“51區”的hash值為“101011”，通過加權計算為 “ 5 -5 5 -5 5 5”。
4、合并，把上面各個單詞算出來的序列值累加，變成只有一個序列串。比如 “美國”的 “4 -4 -4 4 -4 4”，“51區”的 “ 5 -5 5 -5 5 5”， 把每一位進行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。這里作為示例只算了兩個單詞的，真實計算需要把所有單詞的序列串累加。
5、降維，把4步算出來的 “9 -9 1 -1 1 9” 變成 0 1 串，形成我們最終的simhash簽名。如果每一位大于0 記為 1，小于0 記為 0。最后算出結果為：“1 0 1 0 1 1”。
private void analysis(String content) {
Map\<String, Double\> wordInfos = wordExtractor.extract(content);
Map\<String, Double\> newwordInfo = valueUpSort(wordInfos);
wordInfos.entrySet().stream()
.sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
.forEachOrdered(x -\> newwordInfo.put(x.getKey(), x.getValue()));
double[] featureVector = new double[FNVHash.HASH_BITS];
Set\<String\> words = wordInfos.keySet();
for (String word : words) {
BigInteger wordhash = FNVHash.fnv1aHash64(word);
for (int i = 0; i \< FNVHash.HASH_BITS; i++) {
BigInteger bitmask = BigInteger.ONE.shiftLeft(FNVHash.HASH_BITS - i - 1);
if (wordhash.and(bitmask).signum() != 0) {
featureVector[i] += wordInfos.get(word);
} else {
featureVector[i] -= wordInfos.get(word);
}
}
}
BigInteger signature = BigInteger.ZERO;
StringBuffer hashBuffer = new StringBuffer();
for (int i = 0; i \< FNVHash.HASH_BITS; i++) {
if (featureVector[i] \>= 0) {
signature = signature.add(BigInteger.ONE.shiftLeft(FNVHash.HASH_BITS - i - 1));
hashBuffer.append("1");
} else {
hashBuffer.append("0");
}
}
this.hash = hashBuffer.toString();
this.signature = signature;
}算法部分流程圖如下：
圖片
三、空間換時間提高排重速度
通過這種特殊的局部敏感哈希算法看起來是解決了相似性對比的問題，但是，檢索一條漢明距離小于給定閾值的simhash時間復雜度是O(n2) ，這在海量數據下使用的代價是昂貴的。
為了解決這個問題，可以采用空間換時間的思路，假定漢明距離<3時認為文檔與給定文檔相似；每一個simHash都從高位到低位均分成4段，每一段都是16位。在建立倒排索引的過程中，這些截取出來的16位01串的片段，分別作為索引的key值，并將對應位置上具有這個片段的所有文本添加到這個索引的value域中。直觀上理解，首先有四個大桶，分別是1,2,3,4號（對應的是64位hash值中的第一、二、三、四段），在每一個大桶中，又分別有個小桶，這些小桶的編號從0000000000000000到1111111111111111.在建立索引時，每一個文本得到對應的simHash值后，分別去考察每一段（確定是1,2,3和4中的哪個大桶），再根據該段中的16位hash值，將文本放置到對應大桶中對應編號的小桶中。索引建立好后，由于相似文本一定會存在于某一個16位hash值的桶中，因此針對這些分段的所有桶進行去重（可以并行做），便可以將文本集合中的所有相似文本去掉。
1、設漢明距離<n時認為文檔與給定文檔相似；
2、將simhash值分為n段，則漢明距離<n時兩串simhash之間至少有一段完全相同；
3、將信息保存到哈希表中，其中n段中的每一段都作為key，simhash值作為value。
圖片
這樣，檢索速度最快為OO(1)，最慢為O(n)，遠優于原本的O(n^2)，缺點是空間膨脹到原來的n倍。通常n為4，是一個可以接受的膨脹倍率。
因此，我們把64位的01串分隔為4份，每份以key-list的結構存入redis中，當新的文章需要判斷時，則分四段分別到索引中查找。
private void buildContenIndex(String docId, String simHash, String title, String url, String content_index_name, String eid, String oid) {
long storageTime = System.*currentTimeMillis*();
String simHashFragment1 = simHash.substring(0, 16);
String simHashFragment2 = simHash.substring(16, 32);
String simHashFragment3 = simHash.substring(32, 48);
String simHashFragment4 = simHash.substring(48, 64);
String redisKey1 = content_index_name + "_" + simHashFragment1;
String redisKey2 = content_index_name + "_" + simHashFragment2;
String redisKey3 = content_index_name + "_" + simHashFragment3;
String redisKey4 = content_index_name + "_" + simHashFragment4;
String value = docId + "\\001" + title + "\\001" + simHash + "\\001" + url + "\\001" + storageTime + "\\001" + eid;
NewRedisCrud.set2list(redisKey1, value, oid);
NewRedisCrud.set2list(redisKey2, value, oid);
NewRedisCrud.set2list(redisKey3, value, oid);
NewRedisCrud.set2list(redisKey4, value, oid);
}四、總結
內容去重有很多應用場景，simhash作為谷歌選來作為網頁內容去重的一種算法，在海量數據去重的效率上有著明顯的速度優勢，相對傳統文本相似性方法，simhash的降維解決了計算量龐大的問題，但對短文本的去重準確率上有較明顯的欠缺，因此我們在了解業務的背景和需求后才能做出相對合理的選擇。
