在互聯(lián)網(wǎng)出現(xiàn)之前，“抄”很不方便，一是“源”少，而是發(fā)布渠道少；而在互聯(lián)網(wǎng)出現(xiàn)之后，“抄”變得很簡(jiǎn)單，鋪天蓋地的“源”源源不斷，發(fā)布渠道也數(shù)不勝數(shù)，博客論壇甚至是自建網(wǎng)站，而爬蟲(chóng)還可以讓“抄”完全自動(dòng)化不費(fèi)勁。這就導(dǎo)致了互聯(lián)網(wǎng)上的“文章”重復(fù)性很高。這里的“文章”只新聞、博客等文字占據(jù)絕大部分內(nèi)容的網(wǎng)頁(yè)。

中文新聞網(wǎng)站的“轉(zhuǎn)載”（其實(shí)就是抄）現(xiàn)象非常嚴(yán)重，這種“轉(zhuǎn)載”幾乎是全文照抄，或改下標(biāo)題，或是改下編輯姓名，或是文字個(gè)別字修改。所以，對(duì)新聞網(wǎng)頁(yè)的去重很有必要。

一、去重算法原理

文章去重（或叫網(wǎng)頁(yè)去重）是根據(jù)文章（或網(wǎng)頁(yè)）的文字內(nèi)容來(lái)判斷多個(gè)文章之間是否重復(fù)。這是爬蟲(chóng)爬取大量的文本行網(wǎng)頁(yè)（新聞網(wǎng)頁(yè)、博客網(wǎng)頁(yè)等）后要進(jìn)行的非常重要的一項(xiàng)操作，也是搜索引擎非常關(guān)心的一個(gè)問(wèn)題。搜索引擎中抓取的網(wǎng)頁(yè)是海量的，海量文本的去重算法也出現(xiàn)了很多，比如minihash, simhash等等。

在工程實(shí)踐中，對(duì)simhash使用了很長(zhǎng)一段時(shí)間，有些缺點(diǎn)，一是算法比較復(fù)雜、效率較差；二是準(zhǔn)確率一般。

網(wǎng)上也流傳著百度采用的一種方法，用文章最長(zhǎng)句子的hash值作為文章的標(biāo)識(shí)，hash相同的文章（網(wǎng)頁(yè)）就認(rèn)為其內(nèi)容一樣，是重復(fù)的文章（網(wǎng)頁(yè)）。

這個(gè)所謂的“百度算法”對(duì)工程很友好，但是實(shí)際中還是會(huì)有很多問(wèn)題。中文網(wǎng)頁(yè)的一大特點(diǎn)就是“天下文章一大抄”，各種博文、新聞幾乎一字不改或稍作修改就被網(wǎng)站發(fā)表了。這個(gè)特點(diǎn)，很適合這個(gè)“百度算法”。但是，實(shí)際中個(gè)別字的修改，會(huì)導(dǎo)致被轉(zhuǎn)載的最長(zhǎng)的那句話不一樣，從而其hash值也不一樣了，最終結(jié)果是，準(zhǔn)確率很高，召回率較低。

為了解決這個(gè)問(wèn)題，我提出了nshash（top-n longest sentences hash)算法，即：取文章的最長(zhǎng)n句話（實(shí)踐下來(lái)，n=5效果不錯(cuò)）分別做hash值，這n個(gè)hash值作為文章的指紋，就像是人的5個(gè)手指的指紋，每個(gè)指紋都可以唯一確認(rèn)文章的唯一性。這是對(duì)“百度算法”的延伸，準(zhǔn)確率還是很高，但是召回率大大提高，原先一個(gè)指紋來(lái)確定，現(xiàn)在有n個(gè)指紋來(lái)招回了。

二、算法實(shí)現(xiàn)

該算法的原理簡(jiǎn)單，實(shí)現(xiàn)起來(lái)也不難。比較復(fù)雜一點(diǎn)的是對(duì)于一篇文章（網(wǎng)頁(yè)）返回一個(gè)similar_id，只要該ID相同則文章相似，通過(guò)groupby similar_id即可達(dá)到去重目的。

為了記錄文章指紋和similar_id的關(guān)系，我們需要一個(gè)key-value數(shù)據(jù)庫(kù)，本算法實(shí)現(xiàn)了內(nèi)存和硬盤(pán)兩種key-value數(shù)據(jù)庫(kù)類(lèi)來(lái)記錄這種關(guān)系：

HashDBLeveldb 類(lèi)：基于leveldb實(shí)現(xiàn), 可用于海量文本的去重；

HashDBMemory 類(lèi)：基于Python的dict實(shí)現(xiàn)，可用于中等數(shù)量（只要Python的dict不報(bào)內(nèi)存錯(cuò)誤）的文本去重。

這兩個(gè)類(lèi)都具有g(shù)et()和put()兩個(gè)方法，如果你想用Redis或MySQL等其它數(shù)據(jù)庫(kù)來(lái)實(shí)現(xiàn)HashDB，可以參照這兩個(gè)類(lèi)的實(shí)現(xiàn)進(jìn)行實(shí)現(xiàn)。

HashDBLeveldb類(lèi)的實(shí)現(xiàn)

HashDBMemory類(lèi)的實(shí)現(xiàn)

從效率上看，肯定是HashDBMemory速度更快。利用nshash對(duì)17400篇新聞網(wǎng)頁(yè)內(nèi)容的測(cè)試結(jié)果如下:

HashDBLeveldb: 耗時(shí)2.47秒； HashDBMemory: 耗時(shí)1.6秒；

具體測(cè)試代碼請(qǐng)看 example/test.py。

有了這兩個(gè)類(lèi)，就可以實(shí)現(xiàn)nshash的核心算法了。

首先，對(duì)文本進(jìn)行分句，以句號(hào)、感嘆號(hào)、問(wèn)號(hào)、換行符作為句子的結(jié)尾標(biāo)識(shí)，一個(gè)正在表達(dá)式就可以分好句了。

其次，挑選最長(zhǎng)的n句話，分別進(jìn)行hash計(jì)算。hash函數(shù)可以用Python自帶模塊hashlib中的md5， sha等等，也可以用我在爬蟲(chóng)教程中多次提到的farmhash。

最后，我們需要根據(jù)這n個(gè)hash值給文本內(nèi)容一個(gè)similar_id，通過(guò)上面兩種HashDB的類(lèi)的任意一種都可以比較容易實(shí)現(xiàn)。其原理就是，similar_id從0開(kāi)始，從HashDB中查找這n個(gè)hash值是否有對(duì)應(yīng)的similar_id，如果有就返回這個(gè)對(duì)應(yīng)的similar_id；如果沒(méi)有，就讓當(dāng)前similar_id加1作為這n個(gè)hash值對(duì)應(yīng)的similar_id，將這種對(duì)應(yīng)關(guān)系存入HashDB，并返回該similar_id即可。

這個(gè)算法實(shí)現(xiàn)為NSHash類(lèi)：

NSHash類(lèi)的實(shí)現(xiàn)

三、使用方法 

import nshash
nsh = nshash.NSHash(name='test', hashfunc='farmhash', hashdb='memory')
similar_id = nsh.get_similar(doc_text)

NSHash 類(lèi)有三個(gè)參數(shù)：

• name ： 用于hashdb保存到硬盤(pán)的文件名，如果hashdb是HashDBMemory, 則用pickle序列化到硬盤(pán)；如果是HashDBLeveldb，則leveldb目錄名為：name+'.hashdb'。name按需隨便起即可。
• hashfunc : 計(jì)算hash值的具體函數(shù)類(lèi)別，目前實(shí)現(xiàn)兩種類(lèi)型： md5 和 farmhash 。默認(rèn)是 md5 ，方便Windows上安裝farmhash不方便。
• hashdb ：默認(rèn)是 memory 即選擇HashDBMemory，否則是HashDBLeveldb。

至于如何利用similar_id進(jìn)行海量文本的去重，這要結(jié)合你如何存儲(chǔ)、索引這些海量文本?？蓞⒖?code> example/test.py 文件。這個(gè)test是對(duì)excel中保存的新聞網(wǎng)頁(yè)進(jìn)行去重的例子。

總結(jié)

以上所述是小編給大家介紹的使用Python檢測(cè)文章抄襲及去重算法原理解析 ,希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
如果你覺(jué)得本文對(duì)你有幫助，歡迎轉(zhuǎn)載，煩請(qǐng)注明出處，謝謝！

最新評(píng)論