python知⽹查重_⽤Python写了个检测抄袭⽂章去重算法
（nshash）
中国⼈有句话叫“天下⽂章⼀⼤抄”，但是在正规场合下“抄”是要付出代价的，⽐如考试、写论⽂是不能抄的，⼀旦被发现后果相当严重。在互联⽹出现之前，“抄”很不⽅便，⼀是“源”少，⽽是发布渠道少；⽽在互联⽹出现之后，“抄”变得很简单，铺天盖地
的“源”源源不断，发布渠道也数不胜数，博客论坛甚⾄是⾃建⽹站，⽽爬⾍还可以让“抄”完全⾃动化不费劲。这就导致了互联⽹上
的“⽂章”重复性很⾼。这⾥的“⽂章”只新闻、博客等⽂字占据绝⼤部分内容的⽹页。
我在猿⼈学⽹站上写了⼀个《⼤规模异步新闻爬⾍》的教程，⾥⾯涉及了如何抓取⽹页、如何提取正⽂内容，却没有将如何去重。中⽂新闻⽹站的“转载”(其实就是抄)现象⾮常严重，这种“转载”⼏乎是全⽂照抄，或改下标题，或是改下编辑姓名，或是⽂字个别字修改。所以，对新闻⽹页的去重很有必要。
⼀、去重算法原理
⽂章去重(或叫⽹页去重)是根据⽂章(或⽹页)的⽂字内容来判断多个⽂章之间是否重复。这是爬⾍爬取⼤
量的⽂本⾏⽹页(新闻⽹页、博客⽹页等)后要进⾏的⾮常重要的⼀项操作，也是搜索引擎⾮常关⼼的⼀个问题。搜索引擎中抓取的⽹页是海量的，海量⽂本的去重算法也出现了很多，⽐如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篇新闻⽹页内容的测试结果如下:
leveldb使用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 = _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中保存的新闻⽹页进⾏去重的例⼦。
附：论⽂查重算法
这个nshash的思想可以运⽤到论⽂查重。万⽅数据、知⽹等论⽂⽹站都有查重功能，你上传你的论⽂，它们⼏分钟后就可以在它⼏千万的论⽂库中⽐较出跟你论⽂相似的论⽂，并给出⼀些重复的百分百。其背后的算法，我猜⼤致和nshash的思想类似。
⾸先，它要对论⽂库的所有论⽂进⾏索引，以⽅便后⾯的查重时快速查。索引什么呢？就是对每篇论⽂的句⼦都做hash，索引这些hash 值。具体实现上不⼀定是⼀句话⼀个hash值，可能是ngram分句，⽐如每10个字符就算⼀句话。
其次，把你的论⽂安装上述⽅法分句计算hash值，在上⼀步建好的索引中查你论⽂句⼦的hash值，并到对应的论⽂ID，然后再把你的论⽂和到的论⽂进⾏更详细的对⽐，计算相似百分百等等。
看到查重算法背后的实现，你可能就有了“抄”论⽂的妙计：把原⽂的句⼦主动句变为被动句，添加或删减个别字，⽤同义词替换等等。这写可能都是逃过查重算法法眼的“窍门”。但是，算法在对“句⼦”计算hash前做些特别的处理，就可以让你的“窍门”变成“死门”。⽐如，
主动句变被动句：把“句⼦”分词后，按照字符串排序，不管你怎么打乱句⼦，最后经过排序都⼀样；
加减个别字： 为了让句⼦意思准确，你加减的字往往是“的，了，吗”等⽆意义的虚词，也就是停⽤词。这下有了，排序前先去掉停⽤词。你加不加都⼀样；
同义词替换：替换就替换，这事⼉我也⼲，排序前我先做同义词替换，最终⼤家都换成⼀样的。
所以说，写论⽂、写⽂章还是⽤⼼⾃⼰写，别偷懒也别想歪门邪道，哈哈哈。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。