摘要：新问题抛出有没有一种签名算法，如果文本非常相似，签名值也非常相似呢二文本相似性的签名算法上文提出的问题，可以用局部敏感哈希解决，局部敏感哈希是一类文本越相似，哈希值越相似的算法，有兴趣的同学自行百度，这里分享一下的思路。
缘起：
（1）原创不易，互联网抄袭成风，很多原创内容在网上被抄来抄去，改来改去
（2）百度的网页库非常大，爬虫如何判断一个新网页是否与网页库中已有的网页重复呢？
这是本文要讨论的问题（尽量用大家都能立刻明白的语言和示例表述）。
一、传统签名算法与文本完整性判断
问题抛出：
（1）运维上线一个bin文件，将文件分发到4台线上机器上，如何判断bin文件全部是一致的？
（2）用户A将消息msg发送给用户B，用户B如何判断收到的msg_t就是用户A发送的msg？
思路：
一个字节一个字节的比对两个大文件或者大网页效率低，我们可以用一个签名值（例如md5值）代表一个大文件，签名值相同则认为大文件相同（先不考虑冲突率）
回答：
（1）将bin文件取md5，将4台线上机器上的bin文件也取md5，如果5个md5值相同，说明一致
（2）用户A将msg以及消息的md5同时发送给用户B，用户B收到msg_t后也取md5，得到的值与用户A发送过来的md5值如果相同，则说明msg_t与msg相同
结论：md5是一种签名算法，常用来判断数据的完整性与一致性
md5设计原则：两个文本哪怕只有1个bit不同，其md5签名值差别也会非常大，故它只适用于“完整性”check，不适用于“相似性”check。
新问题抛出：
有没有一种签名算法，如果文本非常相似，签名值也非常相似呢？
二、文本相似性的签名算法
上文提出的问题，可以用局部敏感哈希LSH（Locality Sensitive Hash）解决，局部敏感哈希是一类文本越相似，哈希值越相似的hash算法，有兴趣的同学自行百度，这里分享一下minHash的思路。
问题的提出：什么是minHash？
回答：minHash是局部敏感哈希的一种，它常用来快速判定集合的相似性，也常用于检测网页的重复性，其思路为，用相同的规则抽取集合中的少部分元素代表整个集合，如果少部分元素的重合度很高，非常可能整个集合的重复度也很高。
举例：待判定的集合为A{1, 7, 5, 9, 3, 11, 15, 13}
已有的集合为：
B{10, 8, 2, 4, 6, 0, 1, 16},
C{100, 700, 500, 900, 300, 1100, 1500,1300},
D{1, 3, 2, 4, 6, 5, 8, 7}
假设使用部分元素代替全体集合的规则为：集合内元素进行排序，取值最小的4个（这个过程有信息损失，我们可以认为是一个hash过程）
处理结果为：
A{1, 3, 5, 7}
B{0, 1, 2, 4} => A与B有1个元素相同
C{100, 300, 500, 700} => A与C有0个元素相同
D{1, 2, 3, 4} => A与D有2个元素相同
判断结论：我们认为集合A与集合D是最相似的
这个例子有点2，但基本能说明整体思路，实际在执行的过程中：
（1）我们可以使用更多的元素来代表集合，以提高准确性（例如，将上例中的4个元素代表集合升级为8个元素代表集合）
（2）我们可以使用更多的hash函数来代表集合，以提高准确性（例如，上例除了“排序后取值最小的4个元素代表集合”，还可以增加一个哈希函数“排序后取值最大的4个元素代表集合”）
（3）minHash可以量化评判相似度，亦可以评判网页是否重复（一个分类问题），设定相似度阈值，高于阈值为重复，低于阈值为不重复
（4）实际排重过程中，网页库中的哈希值都可以提前计算，只有待判定的集合或者网页的哈希值需要临时计算
三、minHash与长文本重复度检测有什么关系
目前看来没什么关系，但如果我们能将每一个长文本用一个集合来表示，就能将长文本的相似度用minHash来解决了。
问题的提出：如何将长文本转化为集合？
回答：我去，分词不是就可以么
举例：待判定的长文本为A{我是58沈剑，我来自58到家}
已有网页库集合为：
B{我是一只来自58的狼}
C{58到家，服务到家}
D{这事和我没关系，我是凑数的}
使用分词将上述文本集合化：
A{我，58，沈剑，来自，到家}
B{我，58，来自，狼}
C{58，服务，到家}
D{事，我，凑数，关系}
判断结论：当当当当，转化为集合后，可以快速判断A与B的相似度最高，当然实际执行过程中，除了分词还得考虑词频，用这种方法对长文本进行相似度检测，准确率非常高（文本越长越准）
四、还有没有更有效的方法
使用上述方法进行文本相似度检测，需要进行中文分词，词频统计，哈希值计算，相似度计算，计算量微大。
然而，抄袭成风，一字不改的风气，让技术有了更广阔的优化空间，赞！
怎么优化呢？
不再进行分词，而是进行“分句”，用标点符号把长文按照句子分开，使用N个句子集合（例如一篇文章中5条最长的句子作为签名，注意，长句子比短句子更具有区分性）作为文章的签名，在抄袭成风的互联网环境下，此法判断网页的重复度能大大降低工程复杂度，并且准确度也异常的高。
五、结论
在抄袭成风的互联网环境下，采用“分句”的方式，用5条最长的网页内容作为网页的签名，能够极大的降低排重系统复杂度，提高排重准确率，不失为一种好的选择。
摘“ 架构师之路”，不错的订阅号！ 58---沈剑
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/25918.html
摘要：如有感兴趣，请自行查阅相关文档，进一步的了解前端的性能优化单行文本去重单行文本去重可兼容不支持接口的浏览器这里应该很好明白是在干什么吧需要传入一个初始空字符串参数，否则你将得到的是一个字符串被拆分后的数组。 之前偶然看到一篇使用正则实现字符去重及多行去重的文章。感觉写的有点糙，而且性能也不够高，对新手的使用和理解都有一点难度。于是忍不住就搞了一个比较可爱的出来。而且不是一般的可爱，因为...
摘要：中文网页的一大特点就是天下文章一大抄，各种博文新闻几乎一字不改或稍作修改就被网站发表了。这个特点，很适合这个百度算法。但是，实际中个别字的修改，会导致被转载的最长的那句话不一样，从而其值也不一样了，最终结果是，准确率很高，召回率较低。 在互联网出现之前，抄很不方便，一是源少，而是发布渠道少；而在互联网出现之后，抄变得很简单，铺天盖地的源源源不断，发布渠道也数不胜数，博客论坛甚至是自建网...
摘要：简述用途报告或删除文件中重复的行。命令读取由参数指定的标准输入或文件。如果执行成功，命令退出，返回值。这个标志和标志是等价的。退出状态该命令返回以下退出值命令运行成功。补充文件经过处理后在它的输出文件中可能会出现重复的行。 简述 用途 报告或删除文件中重复的行。 语法 uniq [ -c | -d | -u ] [ -f Fields ] [ -s Characters ] [ -Fi...
摘要：前言今天，把自己之前封装过的一部分小功能操作分享出现，都是一些可以说是比较常用，实现起来比较简单，代码又比较少的一些功能或操作，比如关键词变色，数组打乱，数组去重等。关键词变色这个功能很常见，特别是在搜索引擎执行搜索的时候。 1.前言 今天，把自己之前封装过的一部分小功能操作分享出现，都是一些可以说是比较常用，实现起来比较简单，代码又比较少的一些功能或操作，比如关键词变色，数组打乱，数...
阅读 2542·2021-11-22 13:52
阅读 965·2021-10-14 09:43
阅读 3383·2019-08-30 15:56
阅读 2819·2019-08-30 13:22
阅读 3128·2019-08-30 13:10
阅读 1415·2019-08-26 13:45
阅读 957·2019-08-26 11:47
阅读 2598·2019-08-23 18:13
