缘起： （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} = |
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
