在互聯網出現之前，“抄”很不方便，一是“源”少，而是發布渠道少；而在互聯網出現之后，“抄”變得很簡單，鋪天蓋地的“源”源源不斷，發布渠道也數不勝數，博客論壇甚至是自建網站，而爬蟲還可以讓“抄”完全自動化不費勁。這就導致了互聯網上的“文章”重復性很高。這里的“文章”只新聞、博客等文字占據絕大部分內容的網頁。

中文新聞網站的“轉載”（其實就是抄）現象非常嚴重，這種“轉載”幾乎是全文照抄，或改下標題，或是改下編輯姓名，或是文字個別字修改。所以，對新聞網頁的去重很有必要。

一、去重算法原理

文章去重（或叫網頁去重）是根據文章（或網頁）的文字內容來判斷多個文章之間是否重復。這是爬蟲爬取大量的文本行網頁（新聞網頁、博客網頁等）后要進行的非常重要的一項操作，也是搜索引擎非常關心的一個問題。搜索引擎中抓取的網頁是海量的，海量文本的去重算法也出現了很多，比如minihash, simhash等等。

在工程實踐中，對simhash使用了很長一段時間，有些缺點，一是算法比較復雜、效率較差；二是準確率一般。

網上也流傳著百度采用的一種方法，用文章最長句子的hash值作為文章的標識，hash相同的文章（網頁）就認為其內容一樣，是重復的文章（網頁）。

這個所謂的“百度算法”對工程很友好，但是實際中還是會有很多問題。中文網頁的一大特點就是“天下文章一大抄”，各種博文、新聞幾乎一字不改或稍作修改就被網站發表了。這個特點，很適合這個“百度算法”。但是，實際中個別字的修改，會導致被轉載的最長的那句話不一樣，從而其hash值也不一樣了，最終結果是，準確率很高，召回率較低。

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

二、算法實現

該算法的原理簡單，實現起來也不難。比較復雜一點的是對于一篇文章（網頁）返回一個similar_id，只要該ID相同則文章相似，通過groupby similar_id即可達到去重目的。

為了記錄文章指紋和similar_id的關系，我們需要一個key-value數據庫，本算法實現了內存和硬盤兩種key-value數據庫類來記錄這種關系：

HashDBLeveldb 類：基于leveldb實現, 可用于海量文本的去重；

HashDBMemory 類：基于Python的dict實現，可用于中等數量（只要Python的dict不報內存錯誤）的文本去重。

這兩個類都具有get()和put()兩個方法，如果你想用Redis或MySQL等其它數據庫來實現HashDB，可以參照這兩個類的實現進行實現。

HashDBLeveldb類的實現

HashDBMemory類的實現

從效率上看，肯定是HashDBMemory速度更快。利用nshash對17400篇新聞網頁內容的測試結果如下:

HashDBLeveldb: 耗時2.47秒； HashDBMemory: 耗時1.6秒；

具體測試代碼請看 example/test.py。

有了這兩個類，就可以實現nshash的核心算法了。

首先，對文本進行分句，以句號、感嘆號、問號、換行符作為句子的結尾標識，一個正在表達式就可以分好句了。

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

最后，我們需要根據這n個hash值給文本內容一個similar_id，通過上面兩種HashDB的類的任意一種都可以比較容易實現。其原理就是，similar_id從0開始，從HashDB中查找這n個hash值是否有對應的similar_id，如果有就返回這個對應的similar_id；如果沒有，就讓當前similar_id加1作為這n個hash值對應的similar_id，將這種對應關系存入HashDB，并返回該similar_id即可。

這個算法實現為NSHash類：

NSHash類的實現

三、使用方法 ?

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

NSHash 類有三個參數：

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

至于如何利用similar_id進行海量文本的去重，這要結合你如何存儲、索引這些海量文本。可參考 example/test.py 文件。這個test是對excel中保存的新聞網頁進行去重的例子。

總結

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