文档章节

长文本去重

橙子666
 橙子666
发布于 2017/09/10 19:10
字数 1595
阅读 13
收藏 0
点赞 0
评论 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条最长的网页内容作为网页的签名,能够极大的降低排重系统复杂度,提高排重准确率,不失为一种好的选择。

© 著作权归作者所有

共有 人打赏支持
橙子666
粉丝 1
博文 33
码字总数 46552
作品 0
杭州
程序员
长文本去重缘起: (1)原创不易,互联网抄袭成风,很多原创内容在网上被抄来抄去,改来改去 (2)

缘起: (1)原创不易,互联网抄袭成风,很多原创内容在网上被抄来抄去,改来改去 (2)百度的网页库非常大,爬虫如何判断一个新网页是否与网页库中已有的网页重复呢? 这是本文要讨论的问题...

snowing1990 ⋅ 2016/03/03 ⋅ 0

Android控件笔记——使用TextView实现跑马灯效果

1、如何在Android中显示长文本? 在Android中,当我们要显示长文本的时候,如果不做任何操作,仅仅是在TextView中显示,则会自动换行。

落叶-归根 ⋅ 2016/05/12 ⋅ 1

中文主题建模工具包--Familia

Familia 开源项目包含文档主题推断工具、语义匹配计算工具以及基于工业级语料训练的三种主题模型:Latent Dirichlet Allocation(LDA)、SentenceLDA 和Topical Word Embedding(TWE)。 支持用户...

匿名 ⋅ 2017/07/18 ⋅ 1

JFinal 进行Update时,用编辑器保存的长文本,把SQL截断了,怎么处理?

@JFinal 你好,想跟你请教个问题:JFinal 进行Update时,用编辑器保存的长文本,把SQL截断了,怎么处理?

我在开源 ⋅ 2014/11/14 ⋅ 2

文本搜索工具--jsKeyword

jsKeyword 采用树形结构,可以从大量标签中迅速进行模糊检索,或从超长文本中检索标签,轻松实现搜索和自动完成功能。在线演示

Rijn ⋅ 2015/02/06 ⋅ 0

长文本数据怎么处理?

网站页面上面显示的长文本数据,你们是怎么处理的,我觉得用文件存,然后数据库里面存放文件地址,那么每次查询的时候io连接不是很耗时吗?

孙青彪 ⋅ 2013/11/26 ⋅ 4

Vintage Terminal 0.5.0 发布,终端模拟器

Vintage Terminal 0.5.0 增加对鼠标的支持,包括复制粘贴;长文本显示时更快的屏幕更新。 Vintage Terminal 是一个模拟 1980 年显示器外观的终端模拟器。...

oschina ⋅ 2013/08/21 ⋅ 0

清华对话式人工智能课题组六篇长文被ACL 2018、IJCAI-ECAI 2018录用

雷锋网 AI 科技评论按:本文首发于「人工智能THU」,作者钱桥,雷锋网(公众号:雷锋网) AI 科技评论获授权转载。 ACL 2018, the 56th Annual Meeting of the Association for Computational...

奕欣 ⋅ 04/26 ⋅ 0

mysql的varchar和longtext的选择

如果用于存储比较长文本,几千到一万左右的,用varchar还是longtext 据说MySQL5的varchar字段能支持到65532的长度,对于一般的文本足够了,还有没有用longtext的必要,这两种字段存取性能上是...

地瓜干 ⋅ 2014/06/26 ⋅ 3

利用word分词来计算文本相似度

word分词提供了多种文本相似度计算方式: 方式一:余弦相似度,通过计算两个向量的夹角余弦值来评估他们的相似度 实现类:org.apdplat.word.analysis.CosineTextSimilarity 用法如下: Stri...

杨尚川 ⋅ 2015/05/20 ⋅ 26

没有更多内容

加载失败,请刷新页面

加载更多

下一页

内核线程、轻量级进程、用户线程

线程与进程概念 在现代操作系统中,进程支持多线程。 进程是资源管理的最小单元; 线程是程序执行的最小单元。 即线程作为调度和分配的基本单位,进程作为资源分配的基本单位 一个进程的组成...

117 ⋅ 29分钟前 ⋅ 0

elasticsearch2.4.6升级为elasticsearch-5.5.0的经历

将elasticsearch-5.5.0 中的配置 path.data 指向原来的数据路径 即 path.data: /usr/local/src/elasticsearch-2.4.6/data 注意: elasticsearch-5.5.0 需要将jdk版本升级到1.8...

晨猫 ⋅ 30分钟前 ⋅ 1

lvm讲解 磁盘故障小案例

1

oschina130111 ⋅ 34分钟前 ⋅ 0

那些提升开发人员工作效率的在线工具

本文转载自公众号 Hollis 作为一个Java开发人员,经常要和各种各样的工具打交道,除了我们常用的IDE工具以外,其实还有很多工具是我们在日常开发及学习过程中要经常使用到的。 Hollis偏爱使用...

时刻在奔跑 ⋅ 46分钟前 ⋅ 0

restful风格 实现DELETE PUT请求 的web.xml的配置

import org.springframework.beans.factory.annotation.Autowired; import org.springframework.http.HttpStatus; import org.springframework.http.ResponseEntity; import org.springframe......

泉天下 ⋅ 51分钟前 ⋅ 0

Shell数组

Shell数组 Shell在编程方面比Windows批处理强大很多,无论是在循环、运算。 bash支持一维数组(不支持多维数组),并且没有限定数组的大小。类似与C语言,数组元素的下标由0开始编号。获取数...

蜗牛奔跑 ⋅ 今天 ⋅ 0

nmap为了开发方便 可以做简单的修改

因为nmap扫描是默认使用的是nse脚本,但是在开发的过程中需要修改后缀(主要是因为后缀为lua才能显示高亮,所以这里用一个取巧的办法) nse_main.lua文件中我们找到如下代码 local t, path = cn...

超级大黑猫 ⋅ 今天 ⋅ 0

springmvc获取axios数据为null情况

场景:前端用了vue没有用ajax与后台通信,用了axios,但是在代码运行过程中发现axios传递到后台的值接受到数据为null。 问题原因:此处的问题在与axios返回给后台的数据为json类型的,后台接...

王子城 ⋅ 今天 ⋅ 0

hadoop技术入门学习之发行版选择

经常会看到这样的问题:零基础学习hadoop难不难?有的人回答说:零基础学习hadoop,没有想象的那么难,也没有想象的那么容易。看到这样的答案不免觉得有些尴尬,这个问题算是白问了,因为这个...

左手的倒影 ⋅ 今天 ⋅ 0

806. Number of Lines To Write String - LeetCode

Question 806. Number of Lines To Write String Solution 思路:注意一点,如果a长度为4,当前行已经用了98个单元,要另起一行。 Java实现: public int[] numberOfLines(int[] widths, Str...

yysue ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部