短文本合并重復(fù)（去重）的簡單有效做法

2012/6/12

不大合適的SimHash

前些日子看了Charikar SimHash的介紹《Simhash算法原理和網(wǎng)頁查重應(yīng)用》，核心思想是用一個f位的hash值來表示文件的特征值，然后使用hash值之間的Hamming距離來衡量相似性。輸入的是一個文檔的特征集合，輸出的是f位的二進(jìn)制數(shù)S。

于是用來測試短文本（長度在8個中文字符～45個中文字符之間）相似性，做法很簡單：

1.將短文本做分詞，得到分詞數(shù)組，數(shù)組每一個元素都轉(zhuǎn)為hash字符串。

2.利用simhash算法來計算分詞數(shù)組的simhash值。

3.利用simhash的similarity算法計算simhash1和simhash2的相似度。

這種做法的缺點(diǎn)是：

1.誤判率高。

如下圖所示，

SimHash可能不適合做這種短標(biāo)題的重復(fù)度判斷，雖然SimHash在空間消耗和計算復(fù)雜性方面相對Shingle和BloomFilter占優(yōu)。

介紹一下2009年2月份我們做Twitter銳推榜時是如何做的

Twitter中對于熱門事件的中文表達(dá)多種多樣，轉(zhuǎn)發(fā)時又往往會追加很多格式的各種內(nèi)容，造成了相似內(nèi)容的短文本的信息指紋不同，在這種情況下，段國成認(rèn)為需要先為短文本抽取標(biāo)簽，再通過標(biāo)簽來計算相似度進(jìn)行銳推合并。

1.短文本抽取標(biāo)簽的方法：

1.1. 剔除所有英文、數(shù)字、標(biāo)點(diǎn)字符；

1.2. 剔除所有Twitter用戶名；

1.3.分詞，并標(biāo)注詞性，僅保留實體詞性，如名詞、動詞；（技巧一?。?/p>

1.4.過濾掉常用實體詞（常用實體詞是通過對歷史銳推訓(xùn)練而得，即建立自己的停止詞表）；（技巧二?。?/p>

1.5.計算保留實體詞的詞頻，并以此為權(quán)重，選擇權(quán)重大的詞語作為標(biāo)簽；

1.6.標(biāo)簽數(shù)組長度大于一個閾值（如3），才認(rèn)為是有信息量的銳推，否則忽略。（技巧三?。?/p>

2.合并相似短文本（即我們所說的Retweet）方法：

2.1.以每個標(biāo)簽作為Shingle特征（即核心思想還是“一個數(shù)據(jù)段分成若干Shingle，每個Shingle計算出一個hash值，然后組成一個以hash值為元素的數(shù)組，以此作為特征值或叫信息指紋來表示這個數(shù)據(jù)段”）；

2.2.以網(wǎng)頁去重領(lǐng)域中改進(jìn)的Shingle方法來進(jìn)行計算近期內(nèi)（目的：縮小計算范圍）銳推的相似度（Shingle算法的核心思想是將文本相似性問題轉(zhuǎn)換為集合的相似性問題，改進(jìn)的Shingle方法的時間復(fù)雜度近似于線性）；

2.3.對相似程度大于一定閾值的、不同信息指紋的熱門銳推，再次掃描出來，將它們的熱度進(jìn)行合并。

以上結(jié)果就構(gòu)成了 @rtmeme 的運(yùn)算機(jī)制。它特別適合處理十幾個、幾十個漢字的短文本合并重復(fù)，適用于微博領(lǐng)域。

也看到有人這么做：先Shingle再SimHash，不知道是否適合海量短文本合并重復(fù)，回頭試試看。

@鄭昀 于北京

推薦閱讀：

1、

『我認(rèn)為騰訊目前的O2O產(chǎn)品其實是沒任何借鑒意義的，因為真的做得比較差。但我們也有一點(diǎn)做好的決心?！员M管我們在局部解決了閉環(huán)的問題，但實際上整個O2O的閉環(huán)仍然是遙遙無期的事情。』——《戴志康：讓我焦躁并痛苦著的O2O》http://t.cn/zOFL5Cc

2、

#O2O是個偽概念#：知乎O2O系列問答：http://t.cn/SzuEjr ；清科投資集團(tuán)對O2O的解讀：http://t.cn/zOgcikN ；黃紹麟：O2O和無線電子商務(wù)是偽概念 http://t.cn/zOfodfZ

3、

推薦閱讀：『而Google的#simhash#算法產(chǎn)生的簽名，可以用來比較原始內(nèi)容的相似度時，便很想了解這種神奇的算法的原理。出人意料，這個算法并不深奧，其思想是非常清澈美妙的?！弧禨imhash算法原理和網(wǎng)頁查重應(yīng)用》http://t.cn/zOrhqUb

4、

舊文推薦閱讀：『我的團(tuán)長我的團(tuán)中，學(xué)生李梁對龍文章說，我相信你們能戰(zhàn)勝日本人，但問題仍然存在。李鴻章們不遺余力地修鐵路、辦實業(yè)，但問題依然存在。 器物上的改變是不會解決問題的?！?a title="http://www.rzrgm.cn/zhengyun_ustc/archive/2009/03/16/change.html" target="_blank" rel="noopener nofollow">http://t.cn/zOlg0Kg

贈圖一枚：