短文本合并重复(去重)的简单有效做法

标签: 文本 合并 有效 | 发表时间:2012-06-12 18:05 | 作者:旁观者
出处:http://www.cnblogs.com/zhengyun_ustc/

短文本合并重复(去重)的简单有效做法

2012/6/12

不大合适的SimHash

前些日子看了Charikar SimHash的介绍《 Simhash算法原理和网页查重应用》,核心思想是用一个f位的hash值来表示文件的特征值,然后使用hash值之间的Hamming距离来衡量相似性。输入的是一个文档的特征集合,输出的是f位的二进制数S。

于是用来测试短文本(长度在8个中文字符~45个中文字符之间)相似性,做法很简单:

1.将短文本做分词,得到分词数组,数组每一个元素都转为hash字符串。

2.利用simhash算法来计算分词数组的simhash值。

3.利用simhash的similarity算法计算simhash1和simhash2的相似度。

这种做法的缺点是:

1.误判率高。

如下图所示,

  http://s4.sinaimg.cn/middle/72995dcc4c0c38b09c313&690

SimHash可能不适合做这种短标题的重复度判断,虽然 SimHash在空间消耗和计算复杂性方面相对Shingle和BloomFilter占优

 

介绍一下 2009年2月份我们做 Twitter锐推榜时是如何做的

Twitter中对于热门事件的中文表达多种多样,转发时又往往会追加很多格式的各种内容,造成了相似内容的短文本的信息指纹不同,在这种情况下,段国成认为需要先为短文本抽取标签,再通过标签来计算相似度进行锐推合并。

1. 短文本抽取标签的方法:

1.1. 剔除所有英文、数字、标点字符;

1.2. 剔除所有Twitter用户名;

1.3.分词,并标注词性, 仅保留实体词性,如名词、动词;(技巧一!)

1.4. 过滤掉常用实体词(常用实体词是通过对历史锐推训练而得,即建立自己的停止词表);(技巧二!)

1.5.计算保留实体词的词频,并以此为权重,选择权重大的词语作为标签;

1.6.标签 数组长度大于一个阈值(如3),才认为是有信息量的锐推,否则忽略。(技巧三!)

 

2. 合并相似短文本(即我们所说的Retweet )方法:

2.1.以每个标签作为Shingle特征(即核心思想还是“一个数据段分成若干Shingle,每个Shingle计算出一个hash值,然后组成一个以hash值为元素的数组,以此作为特征值或叫信息指纹来表示这个数据段”);

2.2.以网页去重领域中 改进的 Shingle 方法来进行计算 近期内(目的:缩小计算范围)锐推的相似度(Shingle算法的核心思想是将文本相似性问题转换为集合的相似性问题,改进的Shingle方法的时间复杂度近似于线性);

2.3.对相似程度大于一定阈值的、不同信息指纹的热门锐推,再次扫描出来,将它们的热度进行合并。

 

以上结果就构成了 @rtmeme 的运算机制。它特别适合处理十几个、几十个汉字的短文本合并重复,适用于微博领域。

 

也看到有人这么做:先Shingle再SimHash,不知道是否适合海量短文本合并重复,回头试试看。

@郑昀 于北京

 

 

推荐阅读:

1、

『我认为腾讯目前的O2O产品其实是没任何借鉴意义的,因为真的做得比较差。但我们也有一点做好的决心。……所以尽管我们在局部解决了闭环的问题,但实际上整个O2O的闭环仍然是遥遥无期的事情。』——《戴志康:让我焦躁并痛苦着的O2O》 http://t.cn/zOFL5Cc

2、

#O2O是个伪概念#:知乎O2O系列问答: http://t.cn/SzuEjr ;清科投资集团对O2O的解读: http://t.cn/zOgcikN ;黄绍麟:O2O和无线电子商务是伪概念 http://t.cn/zOfodfZ

3、

推荐阅读:『而Google的 #simhash#算法产生的签名,可以用来比较原始内容的相似度时,便很想了解这种神奇的算法的原理。出人意料,这个算法并不深奥,其思想是非常清澈美妙的。』——《Simhash算法原理和网页查重应用》 http://t.cn/zOrhqUb

4、

旧文推荐阅读:『我的团长我的团中,学生李梁对龙文章说,我相信你们能战胜日本人,但问题仍然存在。李鸿章们不遗余力地修铁路、办实业,但问题依然存在。 器物上的改变是不会解决问题的。』 http://t.cn/zOlg0Kg

 

赠图一枚:

http://ww4.sinaimg.cn/large/70a90346gw1dtjk9sv096j.jpg

本文链接

相关 [文本 合并 有效] 推荐:

短文本合并重复(去重)的简单有效做法

- - 博客园_旁观者
短文本合并重复(去重)的简单有效做法. 不大合适的SimHash. 前些日子看了Charikar SimHash的介绍《 Simhash算法原理和网页查重应用》,核心思想是用一个f位的hash值来表示文件的特征值,然后使用hash值之间的Hamming距离来衡量相似性. 输入的是一个文档的特征集合,输出的是f位的二进制数S.

java合并PDF

- - Java - 编程语言 - ITeye博客
15.         * * 合並pdf文件 * * @param files 要合並文件數組(絕對路徑如{ "e:\\1.pdf", "e:\\2.pdf" ,. 17.         * 合並後新產生的文件絕對路徑如e:\\temp.pdf,請自己刪除用過後不再用的文件請 * @return boolean.

mysql-merge合并表

- - CSDN博客编程语言推荐文章
注意: 1 每个子表的结构必须一致,主表和子表的结构需要一致, 2 每个子表的索引在merge表中都会存在,所以在merge表中不能根据该索引进行唯一性检索. 3 子表需要是MyISAM引擎 4 AUTO_INCREMENT 不会按照你所期望的方式工作. 建表语句 create table tablename(正常的字段)engine=merge insert_method=last insert_method: 有两个值如下: LAST 如果你执行insert 指令来操作merge表时,插入操作会把数据添加到最后一个子表中.

合并和比较度量

- liang - SEM WATCH
往往我们在做分析的时候需要结合各类基本的指标进行二次计算合并得到一个可以用于进行综合评价或比较的度量,这个过程中就需要涉及到一些指标的合并技巧,和比较基准的设定. 其实之前“数据上下文”的系列文章中也一再强调了我们需要为指标设定合理的参考系来评价指标的趋势或表现的好坏,之前提供了一系列的方法,但这篇文章里面要介绍的方法应该是最简单方便的,同时不失实用性,得益于《用户体验度量》这本书中的介绍,所以这篇文章更像是一篇读书笔记,内容基本整理总结自《用户体验度量》第8章——合并和比较度量,当然不再局限于用户体验层面,结合了网站分析层面的思考.

ffmpeg裁剪合并视频

- - inJava
这里裁剪是指时间轴裁剪,不是空间裁剪. 比如说,你想把视频的从一分20秒开始,30秒的视频裁剪出来,保存成一个视频. ffmpeg提供简单的命令参数:. -ss 开始时间,如: 00:00:20,表示从20秒开始;. -t 时长,如: 00:00:10,表示截取10秒长的视频;. -i 输入,后面是空格,紧跟着就是输入视频文件;.

hive小文件合并

- - 互联网 - ITeye博客
    hive仓库表数据最终是存储在HDFS上,由于Hadoop的特性,对大文件的处理非常高效. 而且大文件可以减少文件元数据信息,减轻NameNode的存储压力. 但是在数据仓库中,越是上层的表汇总程度就越高,数据量也就越小,而且这些表通常会有日期分区,随着时间的推移,HDFS的文件数目就会逐步增加.

SVN:合并一个分支到主干

- - P.Linux Laboratory
本文内容遵从 CC版权协议, 可以随意转载, 但必须以超链接形式标明文章原始出处和作者信息及版权声明网址: http://www.penglixun.com/tech/program/svn_merge_branch_trunk.html. 原文在此,我只是翻译: http://www.sepcot.com/blog/2007/04/SVN-Merge-Branch-Trunk.

优化 RequireJS 项目(合并与压缩)

- - 博客 - 伯乐在线
英文原文: Optimize (Concatenate and Minify) RequireJS Projects,编译: oschina. 本文将演示如何合并与压缩一个基于RequireJS的项目. 本文中将用到苦干个工具,这其中就包括 Node.js. 因此,如果你手头上还没有Node.js可以 点击此处下载一个.

hbase权威指南: store file合并(compaction)

- - CSDN博客推荐文章
          hbase为了防止小文件(被刷到磁盘的menstore)过多,以保证保证查询效率,hbase需要在必要的时候将这些小的store file合并成相对较大的store file,这个过程就称之为compaction. 在hbase中,主要存在两种类型的compaction:minor  compaction和major compaction.

Hadoop Namenode HA 合并到主干

- - NoSQLFan
Hadoop 的 Namenode 单点问题一直广受诟病,而这个问题最近将会得到解决,对Namenode 的HA方案已经完成实施并合并到主干,经过严格的测试后将会在后续版本中发布. HA方案中,主要进行了如下的一些工作:. 其主要原理是将NameNode分为两种角色,Active和Standby,Active就是正在进行服务的NameNode,而Standby又分三种情况.