資訊專欄INFORMATION COLUMN
摘要：中文網(wǎng)頁的一大特點就是天下文章一大抄，各種博文新聞幾乎一字不改或稍作修改就被網(wǎng)站發(fā)表了。這個特點，很適合這個百度算法。但是，實際中個別字的修改，會導致被轉載的最長的那句話不一樣，從而其值也不一樣了，最終結果是，準確率很高，召回率較低。
在互聯(lián)網(wǎng)出現(xiàn)之前，“抄”很不方便，一是“源”少，而是發(fā)布渠道少；而在互聯(lián)網(wǎng)出現(xiàn)之后，“抄”變得很簡單，鋪天蓋地的“源”源源不斷，發(fā)布渠道也數(shù)不勝數(shù)，博客論壇甚至是自建網(wǎng)站，而爬蟲還可以讓“抄”完全自動化不費勁。這就導致了互聯(lián)網(wǎng)上的“文章”重復性很高。這里的“文章”只新聞、博客等文字占據(jù)絕大部分內(nèi)容的網(wǎng)頁。
中文新聞網(wǎng)站的“轉載”（其實就是抄）現(xiàn)象非常嚴重，這種“轉載”幾乎是全文照抄，或改下標題，或是改下編輯姓名，或是文字個別字修改。所以，對新聞網(wǎng)頁的去重很有必要。
一、去重算法原理文章去重（或叫網(wǎng)頁去重）是根據(jù)文章（或網(wǎng)頁）的文字內(nèi)容來判斷多個文章之間是否重復。這是爬蟲爬取大量的文本行網(wǎng)頁（新聞網(wǎng)頁、博客網(wǎng)頁等）后要進行的非常重要的一項操作，也是搜索引擎非常關心的一個問題。搜索引擎中抓取的網(wǎng)頁是海量的，海量文本的去重算法也出現(xiàn)了很多，比如minihash, simhash等等。
在工程實踐中，對simhash使用了很長一段時間，有些缺點，一是算法比較復雜、效率較差；二是準確率一般。
網(wǎng)上也流傳著百度采用的一種方法，用文章最長句子的hash值作為文章的標識，hash相同的文章（網(wǎng)頁）就認為其內(nèi)容一樣，是重復的文章（網(wǎng)頁）。
這個所謂的“百度算法”對工程很友好，但是實際中還是會有很多問題。中文網(wǎng)頁的一大特點就是“天下文章一大抄”，各種博文、新聞幾乎一字不改或稍作修改就被網(wǎng)站發(fā)表了。這個特點，很適合這個“百度算法”。但是，實際中個別字的修改，會導致被轉載的最長的那句話不一樣，從而其hash值也不一樣了，最終結果是，準確率很高，召回率較低。
為了解決這個問題，我提出了nshash（top-n longest sentences hash)算法，即：取文章的最長n句話（實踐下來，n=5效果不錯）分別做hash值，這n個hash值作為文章的指紋，就像是人的5個手指的指紋，每個指紋都可以唯一確認文章的唯一性。這是對“百度算法”的延伸，準確率還是很高，但是召回率大大提高，原先一個指紋來確定，現(xiàn)在有n個指紋來招回了。
二、算法實現(xiàn)該算法的原理簡單，實現(xiàn)起來也不難。比較復雜一點的是對于一篇文章（網(wǎng)頁）返回一個similar_id，只要該ID相同則文章相似，通過groupby similar_id即可達到去重目的。
為了記錄文章指紋和similar_id的關系，我們需要一個key-value數(shù)據(jù)庫，本算法實現(xiàn)了內(nèi)存和硬盤兩種key-value數(shù)據(jù)庫類來記錄這種關系：
HashDBLeveldb 類：基于leveldb實現(xiàn), 可用于海量文本的去重；
HashDBMemory 類：基于Python的dict實現(xiàn)，可用于中等數(shù)量（只要Python的dict不報內(nèi)存錯誤）的文本去重。
這兩個類都具有get()和put()兩個方法，如果你想用Redis或MySQL等其它數(shù)據(jù)庫來實現(xiàn)HashDB，可以參照這兩個類的實現(xiàn)進行實現(xiàn)。
HashDBLeveldb類的實現(xiàn)
HashDBMemory類的實現(xiàn)
從效率上看，肯定是HashDBMemory速度更快。利用nshash對17400篇新聞網(wǎng)頁內(nèi)容的測試結果如下:
HashDBLeveldb: 耗時2.47秒；
HashDBMemory: 耗時1.6秒；
具體測試代碼請看 example/test.py。
有了這兩個類，就可以實現(xiàn)nshash的核心算法了。
首先，對文本進行分句，以句號、感嘆號、問號、換行符作為句子的結尾標識，一個正在表達式就可以分好句了。
其次，挑選最長的n句話，分別進行hash計算。hash函數(shù)可以用Python自帶模塊hashlib中的md5， sha等等，也可以用我在爬蟲教程中多次提到的farmhash。
最后，我們需要根據(jù)這n個hash值給文本內(nèi)容一個similar_id，通過上面兩種HashDB的類的任意一種都可以比較容易實現(xiàn)。其原理就是，similar_id從0開始，從HashDB中查找這n個hash值是否有對應的similar_id，如果有就返回這個對應的similar_id；如果沒有，就讓當前similar_id加1作為這n個hash值對應的similar_id，將這種對應關系存入HashDB，并返回該similar_id即可。
這個算法實現(xiàn)為NSHash類：
NSHash類的實現(xiàn)
三、使用方法import nshash nsh = nshash.NSHash(name="test", hashfunc="farmhash", hashdb="memory") similar_id = nsh.get_similar(doc_text)
NSHash類有三個參數(shù)：
name： 用于hashdb保存到硬盤的文件名，如果hashdb是HashDBMemory, 則用pickle序列化到硬盤；如果是HashDBLeveldb，則leveldb目錄名為：name+’.hashdb’。name按需隨便起即可。
hashfunc: 計算hash值的具體函數(shù)類別，目前實現(xiàn)兩種類型：md5和farmhash。默認是md5，方便Windows上安裝farmhash不方便。
hashdb：默認是memory即選擇HashDBMemory，否則是HashDBLeveldb。
至于如何利用similar_id進行海量文本的去重，這要結合你如何存儲、索引這些海量文本。可參考example/test.py文件。這個test是對excel中保存的新聞網(wǎng)頁進行去重的例子。
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://www.ezyhdfw.cn/yun/43999.html
摘要：新問題拋出有沒有一種簽名算法，如果文本非常相似，簽名值也非常相似呢二文本相似性的簽名算法上文提出的問題，可以用局部敏感哈希解決，局部敏感哈希是一類文本越相似，哈希值越相似的算法，有興趣的同學自行百度，這里分享一下的思路。 緣起：（1）原創(chuàng)不易，互聯(lián)網(wǎng)抄襲成風，很多原創(chuàng)內(nèi)容在網(wǎng)上被抄來抄去，改來改去（2）百度的網(wǎng)頁庫非常大，爬蟲如何判斷一個新網(wǎng)頁是否與網(wǎng)頁庫中已有的網(wǎng)頁重復呢？這是本文要...
摘要：專題系列共計篇，主要研究日常開發(fā)中一些功能點的實現(xiàn)，比如防抖節(jié)流去重類型判斷拷貝最值扁平柯里遞歸亂序排序等，特點是研究專題之函數(shù)組合專題系列第十六篇，講解函數(shù)組合，并且使用柯里化和函數(shù)組合實現(xiàn)模式需求我們需要寫一個函數(shù)，輸入，返回。 JavaScript 專題之從零實現(xiàn) jQuery 的 extend JavaScritp 專題系列第七篇，講解如何從零實現(xiàn)一個 jQuery 的 ext...
摘要：網(wǎng)絡黑白一書所抄襲的文章列表這本書實在是垃圾，一是因為它的互聯(lián)網(wǎng)上的文章拼湊而成的，二是因為拼湊水平太差，連表述都一模一樣，還抄得前言不搭后語，三是因為內(nèi)容全都是大量的科普，不涉及技術也沒有干貨。 《網(wǎng)絡黑白》一書所抄襲的文章列表 這本書實在是垃圾，一是因為它的互聯(lián)網(wǎng)上的文章拼湊而成的，二是因為拼湊水平太差，連表述都一模一樣，還抄得前言不搭后語，三是因為內(nèi)容全都是大量的科普，不涉及技術...
摘要：它在實踐中被成功地用于檢測學生程序提交中的剽竊行為。這項措施應該反映原始程序中由比賽覆蓋的部分代幣。這個程序集根本不包含任何剽竊行為，因此將其命名為。在節(jié)目集中有個抄襲對。 摘要：JPlag是一個Web服務，可以在給定的集合中找到類似的程序對的程序。它在實踐中被成功地用于檢測學生Java程序提交中的剽竊行為。能支持的語言除了java之外,還有C、C++和Scheme。我們描述Jpalg...
閱讀 1513·2021-09-22 15:43
閱讀 2217·2019-08-30 15:54
閱讀 1224·2019-08-30 10:51
閱讀 2147·2019-08-29 18:35
閱讀 479·2019-08-26 11:58
閱讀 2534·2019-08-26 11:38
閱讀 2499·2019-08-23 18:35
閱讀 3723·2019-08-23 18:33
