文档章节

长文本去重缘起: (1)原创不易,互联网抄袭成风,很多原创内容在网上被抄来抄去,改来改去 (2)

snowing1990
 snowing1990
发布于 2016/03/03 19:05
字数 1628
阅读 24
收藏 0
点赞 1
评论 0

缘起:

(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条最长的网页内容作为网页的签名,能够极大的降低排重系统复杂度,提高排重准确率,不失为一种好的选择。

本文转载自:

共有 人打赏支持
snowing1990
粉丝 4
博文 90
码字总数 2952
作品 0
程序员
针对抄袭和盗版的一点想法

前两天刚得知博文被抄袭时,我的第一反应是很气愤,在微博、qq空间及csdn的qq群等地方都发表了心情,我想引起一些关注,进而得到一定的回馈。 如今心情平复下来,再回过头来一想,又有了一些...

涂宗勋
2016/04/16
79
0
我们完全有必要对抄袭这个事情敏感

山寨和抄袭是中国互联网上永恒的话题。近年来常见的几种说法: 抄袭和模仿是必经阶段。 太阳底下无新事,没有什么东西是完全原创的。 中国互联网公司都抄,但不是每家都能抄成功。抄不等于成...

红薯
2012/04/17
1K
15
1025 - 花钱证明自己是好人

这几天断断续续在思考软件抄袭的事。 Pin、时间块这些 App 相继被朴素级抄袭,有很多的共同点: 本身都是很优秀的产品,被 App Store 首页多次推荐 开发者我都认识,至少是神交 抄袭都反应出...

atJason
2017/10/25
0
0
国内 App 市场“烂透了”?

用户界面全拷贝 离职带走程序源代码 互抄现象频现 预装模式压制创业者 4月26日,世界知识产权日,所有登录网易邮箱的用户都会看到这样一幅画面:左边一个艺术家打扮的人画出了一只叼着橄榄枝...

红薯
2012/04/29
4.6K
50
程序员都喜欢抄袭“代码”,而且还拿着高薪?难道这么无法无天

  你们知道程序员最熟悉,最熟练,最常用的两个快捷键是哪两个吗?没错,估计你现在心中所想的就是:ctrl+c 和 ctrl+v ,俗名为:复制和粘贴。对于大部分程序员来说:复制和粘贴就是他敲代...

万能的大白
2017/12/06
0
0
[图] 腾讯VS网易:邮箱“隔空掐架”

继不久前网易指责腾讯抄袭其新闻客户端之后,近日,网易邮箱与腾讯邮箱又开始“隔空掐架”,引发了大量网友的围观和热议。4 月12日,网易公司宣布,旗下重要的移动互联网产品网易新闻客户端,...

虫虫
2012/04/25
3.1K
25
分词应用 Pin 开发者发文斥责锤子 Big Bang 抄袭

Big Bang 是在锤子发布 M1/M1L 时,主打的新 Smaerisan OS 当中内置的三大功能之一,随后锤子也将这其开源。不过近日,以智慧分词为核心的大爆炸功能在近期引来了非议。 iOS 端智慧分词软件 ...

王练
2017/07/15
1K
34
Unity3D AR技术 vuforia SDK

原创文章如需转载请注明:转载自 脱莫柔Unity3D学习之旅 QQ群:【119706192】 本文链接地址: Unity3D AR技术 vuforia SDK 公司新项目要使用ar技术(增强现实),网上搜了些相关资料发现使用最...

Ida62
2014/05/08
0
0
IT伦理与道德:腾讯 - 帝国是“抄”出来的?

虽然我们还处于青年时代,但诞生于1998年,和我们一般大的腾讯,作为一家企业,已经非常成熟,是行业中的精英了。但近二十年来,腾讯一直摆脱不了一个话题,一个涉及伦理道德的问题—抄袭。在...

xbnpie
2017/12/04
0
0
技术人员如何跟传统行业打交道?

前几天,读了一本书叫《高难度谈话》,这本书主要讲的就是「沟通」问题,而本书的主题就是「人」——我们这些并不完美却真实的人。人是一种复杂的个体,我们每个人都有自己的观点、思想和感情...

OneAPM蓝海讯通
2016/01/06
5
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

实现异步有哪些方法

有哪些方法可以实现异步呢? 方式一:java 线程池 示例: @Test public final void test_ThreadPool() throws InterruptedException { ScheduledThreadPoolExecutor scheduledThre......

黄威
今天
0
0
linux服务器修改mtu值优化cpu

一、jumbo frames 相关 1、什么是jumbo frames Jumbo frames 是指比标准Ethernet Frames长的frame,即比1518/1522 bit大的frames,Jumbo frame的大小是每个设备厂商规定的,不属于IEEE标准;...

六库科技
今天
0
0
牛客网刷题

1. 二维数组中的查找(难度:易) 题目描述 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入...

大不了敲一辈子代码
今天
0
0
linux系统的任务计划、服务管理

linux任务计划cron 在linux下,有时候要在我们不在的时候执行一项命令,或启动一个脚本,可以使用任务计划cron功能。 任务计划要用crontab命令完成 选项: -u 指定某个用户,不加-u表示当前用...

黄昏残影
昨天
0
0
设计模式:单例模式

单例模式的定义是确保某个类在任何情况下都只有一个实例,并且需要提供一个全局的访问点供调用者访问该实例的一种模式。 实现以上模式基于以下必须遵守的两点: 1.构造方法私有化 2.提供一个...

人觉非常君
昨天
0
0
《Linux Perf Master》Edition 0.4 发布

在线阅读:https://riboseyim.gitbook.io/perf 在线阅读:https://www.gitbook.com/book/riboseyim/linux-perf-master/details 百度网盘【pdf、mobi、ePub】:https://pan.baidu.com/s/1C20T......

RiboseYim
昨天
1
0
conda 换源

https://mirrors.tuna.tsinghua.edu.cn/help/anaconda/ conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free/conda config --add channels https://mir......

阿豪boy
昨天
1
0
Confluence 6 安装补丁类文件

Atlassian 支持或者 Atlassian 缺陷修复小组可能针对有一些关键问题会提供补丁来解决这些问题,但是这些问题还没有放到下一个更新版本中。这些问题将会使用 Class 类文件同时在官方 Jira bug...

honeymose
昨天
0
0
非常实用的IDEA插件之总结

1、Alibaba Java Coding Guidelines 经过247天的持续研发,阿里巴巴于10月14日在杭州云栖大会上,正式发布众所期待的《阿里巴巴Java开发规约》扫描插件!该插件由阿里巴巴P3C项目组研发。P3C...

Gibbons
昨天
1
0
Tomcat介绍,安装jdk,安装tomcat,配置Tomcat监听80端口

Tomcat介绍 Tomcat是Apache软件基金会(Apache Software Foundation)的Jakarta项目中的一个核心项目,由Apache、Sun和其他一些公司及个人共同开发而成。 java程序写的网站用tomcat+jdk来运行...

TaoXu
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部