一、背景

信息流個(gè)性化推薦場景中依賴爬蟲抓取的海量新聞庫，這些新聞中不乏互相抄襲的新聞，這些內(nèi)容相似的文章，會(huì)造成內(nèi)容的同質(zhì)化并加重?cái)?shù)據(jù)庫的存儲(chǔ)負(fù)擔(dān)，更糟糕的是降低了信息流內(nèi)容的體驗(yàn)。所以需要一種準(zhǔn)確高效的文本去重算法。而最樸素的做法就是將所有文本進(jìn)行兩兩比較，簡單易理解，最符合人類的直覺，這種做法對(duì)于少量文本來說，實(shí)現(xiàn)起來很方便，但是對(duì)于海量文本來說是行不通的，所以應(yīng)在盡可能保證準(zhǔn)確性的同時(shí)，降低算法的時(shí)間復(fù)雜度。事實(shí)上，傳統(tǒng)比較兩個(gè)文本相似性的方法，大多是將文本分詞之后，轉(zhuǎn)化為特征向量距離的度量，比如常見的歐氏距離、海明距離或者余弦角度等等。下面以余弦相似度和simhash算法為例做簡單介紹。

1.1 余弦相似度

余弦相似度的核心思想是計(jì)算兩個(gè)向量的夾角余弦值來判斷兩個(gè)句子的相似度，以下面兩個(gè)句子為例：

第一步分詞：

句子A：我/喜歡/看/電視，不/喜歡/看/電影

句子B：我/不/喜歡/看/電視，也/不/喜歡/看/電影

第二步列出所有詞：

我，喜歡，看，電視，電影，不，也

第三步計(jì)算詞頻：

句子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]

到這里就可以將兩個(gè)句子的相似度轉(zhuǎn)換為兩個(gè)向量的相似度，我們可以把這兩個(gè)句子想象為空間中的兩條線段，都是從原點(diǎn)[0,0,0...]出發(fā)，指向不同的方向，兩條線段形成一個(gè)夾角，如果夾角為0，意味著方向相同線段重合，如果夾角為90度意味著形成直角，完全不相似，因此我們可以通過夾角來判斷相似度，夾角越小就代表越相似。

余弦相似度得到的結(jié)果較為精確，但當(dāng)面對(duì)大量文本時(shí)，計(jì)算文本向量的時(shí)間復(fù)雜度很高，這可能會(huì)影響性能。

1.2 simHash算法

simHash是谷歌提出來的一套用于文本去重的算法，將文本映射為一個(gè)01串，并且保證相似文本哈希之后得到的01串也是相似的，只在少數(shù)幾個(gè)位置上的0和1不一樣。為了表征原始文本的相似度，可以計(jì)算兩個(gè)01串之間在多少個(gè)位置上不同，這便是漢明距離，用來表征simHash算法下兩個(gè)文本之間的相似度，通常來說，越相似的文本，對(duì)應(yīng)simHash映射得到的01串之間的漢明距離越小。舉例：t1=“直擊兒科急診現(xiàn)狀忙碌不止 兒科接診進(jìn)行時(shí) ”t2=“兒科急診現(xiàn)狀直擊不停忙碌 兒科接診進(jìn)行時(shí) ”;可以看到，上面這兩個(gè)字符串雖然只有幾個(gè)字不同，但是通過簡單的Hash算法得到的hash值可能就完全不一樣了，因而無法利用得到的hash值來表征原始文本的相似性。然而通過simHash算法的映射后，得到的simHash值便是如下：

圖片

這兩個(gè)文本生成的兩個(gè)64位的01串只有標(biāo)紅的3個(gè)位置不同。通常來說，用于相似文本檢測中的漢明距離判斷標(biāo)準(zhǔn)就是3，也就是說，當(dāng)兩個(gè)文本對(duì)應(yīng)的simHash之間的漢明距離小于或等于3，則認(rèn)為這兩個(gè)文本為相似，如果是要去重的話，就只能留下其中一個(gè)。

下圖為在各種漢明距離的情況下simhash算法的準(zhǔn)確和召回率變化趨勢，可以看到在漢明距離為3時(shí)能夠達(dá)到較好的平衡：

圖片

相比計(jì)算余弦相似度，simhash算法可以快速計(jì)算文本的哈希值，而且能夠在哈希值之間計(jì)算漢明距離，從而衡量文本的相似度。simhash算法的優(yōu)點(diǎn)是它能夠快速處理大量文本，并且可以識(shí)別并過濾掉文本中的噪聲和重復(fù)內(nèi)容。

二、simhash實(shí)現(xiàn)步驟

1、分詞，把需要判重的文本分詞，形成去掉噪音詞的單詞序列并為每個(gè)詞加上權(quán)重。我們假設(shè)權(quán)重分為5個(gè)級(jí)別（1~5）。比如：“ 美國“51區(qū)”雇員稱內(nèi)部有9架飛碟，曾看見灰色外星人 ” ==> 分詞后為 “ 美國（4） 51區(qū)（5） 雇員（3） 稱（1） 內(nèi)部（2） 有（1） 9架（3） 飛碟（5） 曾（1） 看見（3） 灰色（4） 外星人（5）”，括號(hào)里的權(quán)重代表重要程度，數(shù)字越大越重要，這里我們采用ansj分詞器，tf-idf的方式計(jì)算權(quán)重。生成一個(gè)詞和對(duì)應(yīng)權(quán)重的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);  
// 計(jì)算詞頻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;  
 }  
// 計(jì)算權(quán)重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算法把每個(gè)詞變成hash值，比如“美國”通過hash算法計(jì)算為 100101,“51區(qū)”通過hash算法計(jì)算為 101011。這樣我們的字符串就變成了一串串?dāng)?shù)字，還記得文章開頭說過的嗎，要把文章變?yōu)閿?shù)字計(jì)算才能提高相似度計(jì)算性能，現(xiàn)在是降維過程進(jìn)行時(shí)。

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、加權(quán)，通過2步驟的hash生成結(jié)果，需要按照單詞的權(quán)重形成加權(quán)數(shù)字串，比如“美國”的hash值為“100101”，通過加權(quán)計(jì)算為“4 -4 -4 4 -4 4”；“51區(qū)”的hash值為“101011”，通過加權(quán)計(jì)算為 “ 5 -5 5 -5 5 5”。

4、合并，把上面各個(gè)單詞算出來的序列值累加，變成只有一個(gè)序列串。比如 “美國”的 “4 -4 -4 4 -4 4”，“51區(qū)”的 “ 5 -5 5 -5 5 5”， 把每一位進(jìn)行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。這里作為示例只算了兩個(gè)單詞的，真實(shí)計(jì)算需要把所有單詞的序列串累加。

5、降維，把4步算出來的 “9 -9 1 -1 1 9” 變成 0 1 串，形成我們最終的simhash簽名。如果每一位大于0 記為 1，小于0 記為 0。最后算出結(jié)果為：“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;  
}

算法部分流程圖如下：

圖片

三、空間換時(shí)間提高排重速度

通過這種特殊的局部敏感哈希算法看起來是解決了相似性對(duì)比的問題，但是，檢索一條漢明距離小于給定閾值的simhash時(shí)間復(fù)雜度是O(n2) ，這在海量數(shù)據(jù)下使用的代價(jià)是昂貴的。

為了解決這個(gè)問題，可以采用空間換時(shí)間的思路，假定漢明距離<3時(shí)認(rèn)為文檔與給定文檔相似；每一個(gè)simHash都從高位到低位均分成4段，每一段都是16位。在建立倒排索引的過程中，這些截取出來的16位01串的片段，分別作為索引的key值，并將對(duì)應(yīng)位置上具有這個(gè)片段的所有文本添加到這個(gè)索引的value域中。直觀上理解，首先有四個(gè)大桶，分別是1,2,3,4號(hào)（對(duì)應(yīng)的是64位hash值中的第一、二、三、四段），在每一個(gè)大桶中，又分別有個(gè)小桶，這些小桶的編號(hào)從0000000000000000到1111111111111111.在建立索引時(shí)，每一個(gè)文本得到對(duì)應(yīng)的simHash值后，分別去考察每一段（確定是1,2,3和4中的哪個(gè)大桶），再根據(jù)該段中的16位hash值，將文本放置到對(duì)應(yīng)大桶中對(duì)應(yīng)編號(hào)的小桶中。索引建立好后，由于相似文本一定會(huì)存在于某一個(gè)16位hash值的桶中，因此針對(duì)這些分段的所有桶進(jìn)行去重（可以并行做），便可以將文本集合中的所有相似文本去掉。

1、設(shè)漢明距離<n時(shí)認(rèn)為文檔與給定文檔相似；

2、將simhash值分為n段，則漢明距離<n時(shí)兩串simhash之間至少有一段完全相同；

3、將信息保存到哈希表中，其中n段中的每一段都作為key，simhash值作為value。

圖片

這樣，檢索速度最快為OO(1)，最慢為O(n)，遠(yuǎn)優(yōu)于原本的O(n^2)，缺點(diǎn)是空間膨脹到原來的n倍。通常n為4，是一個(gè)可以接受的膨脹倍率。

因此，我們把64位的01串分隔為4份，每份以key-list的結(jié)構(gòu)存入redis中，當(dāng)新的文章需要判斷時(shí)，則分四段分別到索引中查找。

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);  
}

四、總結(jié)

內(nèi)容去重有很多應(yīng)用場景，simhash作為谷歌選來作為網(wǎng)頁內(nèi)容去重的一種算法，在海量數(shù)據(jù)去重的效率上有著明顯的速度優(yōu)勢，相對(duì)傳統(tǒng)文本相似性方法，simhash的降維解決了計(jì)算量龐大的問題，但對(duì)短文本的去重準(zhǔn)確率上有較明顯的欠缺，因此我們在了解業(yè)務(wù)的背景和需求后才能做出相對(duì)合理的選擇。