海量数据相似度计算之simhash短文本查找

标签: 数据 相似 计算 | 发表时间:2013-09-09 07:34 | 作者:
出处:http://www.iteye.com

在前一篇文章 《 海量数据相似度计算之simhash和海明距离》 介绍了simhash的原理,大家应该感觉到了算法的魅力。但是随着业务的增长 simhash的数据也会暴增,如果一天100w,10天就1000w了。我们如果插入一条数据就要去比较1000w次的simhash,计算量还是蛮大,普通PC 比较1000w次海明距离需要 300ms ,和5000w数据比较需要1.8 s。看起来相似度计算不是很慢,还在秒级别。给大家算一笔账就知道了:

随着业务增长需要一个小时处理100w次,一个小时为3600 *1000 = 360w毫秒,计算一下一次相似度比较最多只能消耗 360w / 100w = 3.6毫秒。300ms慢吗,慢!1.8S慢吗,太慢了!很多情况大家想的就是升级、增加机器,但有些时候光是增加机器已经解决不了问题了,就算增加机器也不是短时间能够解决的,需要考虑分布式、客户预算、问题解决的容忍时间?头大时候要相信人类的智慧是无穷的,泡杯茶,听下轻音乐:)畅想下宇宙有多大,宇宙外面还有什么东西,程序员有什么问题能够难倒呢?

加上客户还提出的几个,汇总一下技术问题:

  • 1、一个小时需要比较100w次,也就是每条数据和simhash库里的数据比较需要做到3.6毫秒。
  • 2、两条同一时刻发出的文本如果重复也只能保留一条。
  • 3、希望保留2天的数据进行比较去重,按照目前的量级和未来的增长,2天大概在2000w — 5000w 中间。
  • 4、短文本和长文本都要去重,经过测试长文本使用simhash效果很好,短文本使用simhash 准备度不高。

目前我们估算一下存储空间的大小,就以JAVA 来说,存储一个simhash 需要一个原生态 lang 类型是64位 = 8 byte,如果是 Object 对象还需要额外的 8 byte,所以我们尽量节约空间使用原生态的lang类型。假设增长到最大的5000w数据, 5000w * 8byte = 400000000byte = 400000000/( 1024 * 1024) = 382 Mb,所以按照这个大小普通PC服务器就可以支持,这样第三个问题就解决了。

比较5000w次怎么减少时间呢?其实这也是一个查找的过程,我们想想以前学过的查找算法: 顺序查找、二分查找、二叉排序树查找、索引查找、哈希查找。不过我们这个不是比较数字是否相同,而是比较海明距离,以前的算法并不怎么通用,不过解决问题的过程都是通用的。还是和以前一样,不使用数学公式,使用程序猿大家都理解的方式。还记得JAVA里有个HashMap吗?我们要查找一个key值时,通过传入一个key就可以很快的返回一个value,这个号称查找速度最快的数据结构是如何实现的呢?看下hashmap的内部结构:

java hashmap内部结构

如果我们需要得到key对应的value,需要经过这些计算,传入key,计算key的hashcode,得到7的位置;发现7位置对应的value还有好几个,就通过链表查找,直到找到v72。其实通过这么分析,如果我们的hashcode设置的不够好,hashmap的效率也不见得高。借鉴这个算法,来设计我们的simhash查找。通过顺序查找肯定是不行的,能否像hashmap一样先通过键值对的方式减少顺序比较的次数。看下图:

大规模simhash算法优化

存储
1、将一个64位的simhash code拆分成4个16位的二进制码。(图上红色的16位)
2、分别拿着4个16位二进制码查找当前对应位置上是否有元素。(放大后的16位)
3、对应位置没有元素,直接追加到链表上;对应位置有则直接追加到链表尾端。(图上的 S1 — SN)

查找
1、将需要比较的simhash code拆分成4个16位的二进制码。
2、分别拿着4个16位二进制码每一个去查找simhash集合对应位置上是否有元素。
2、如果有元素,则把链表拿出来顺序查找比较,直到simhash小于一定大小的值,整个过程完成。

原理
借鉴hashmap算法找出可以hash的key值,因为我们使用的simhash是局部敏感哈希,这个算法的特点是只要相似的字符串只有个别的位数是有差别变化。那这样我们可以推断两个相似的文本,至少有16位的simhash是一样的。具体选择16位、8位、4位,大家根据自己的数据测试选择,虽然比较的位数越小越精准,但是空间会变大。分为4个16位段的存储空间是单独simhash存储空间的4倍。之前算出5000w数据是 382 Mb,扩大4倍1.5G左右,还可以接受:)

通过这样计算,我们的simhash查找过程全部降到了1毫秒以下。就加了一个hash效果这么厉害?我们可以算一下,原来是5000w次顺序比较,现在是少了2的16次方比较,前面16位变成了hash查找。后面的顺序比较的个数是多少? 2^16 = 65536, 5000w/65536 = 763 次。。。。实际最后链表比较的数据也才 763次!所以效率大大提高!

到目前第一点降到3.6毫秒、支持5000w数据相似度比较做完了。还有第二点同一时刻发出的文本如果重复也只能保留一条和短文本相识度比较怎么解决。其实上面的问题解决了,这两个就不是什么问题了。

  • 之前的评估一直都是按照线性计算来估计的,就算有多线程提交相似度计算比较,我们提供相似度计算服务器也需要线性计算。比如同时客户端发送过来两条需要比较相似度的请求,在服务器这边都进行了一个排队处理,一个接着一个,第一个处理完了在处理第二个,等到第一个处理完了也就加入了simhash库。所以只要服务端加了队列,就不存在同时请求不能判断的情况。
  • simhash如何处理短文本?换一种思路,simhash可以作为局部敏感哈希第一次计算缩小整个比较的范围,等到我们只有比较700多次比较时,就算使用我们之前精准度高计算很慢的编辑距离也可以搞定。当然如果觉得慢了,也可以使用余弦夹角等效率稍微高点的相似度算法。

参考:
我的数学之美系列二 —— simhash与重复信息识别

原创文章,转载请注明: 转载自 LANCEYAN.COM

本文链接地址:  海量数据相似度计算之simhash短文本查找



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [数据 相似 计算] 推荐:

海量数据相似度计算之simhash短文本查找

- - ITeye博客
在前一篇文章 《 海量数据相似度计算之simhash和海明距离》 介绍了simhash的原理,大家应该感觉到了算法的魅力. 但是随着业务的增长 simhash的数据也会暴增,如果一天100w,10天就1000w了. 我们如果插入一条数据就要去比较1000w次的simhash,计算量还是蛮大,普通PC 比较1000w次海明距离需要 300ms ,和5000w数据比较需要1.8 s.

海量数据相似度计算之simhash和海明距离

- - CSDN博客架构设计推荐文章
通过  采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析. 分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法. 常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等. 这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重.

URL相似度计算的思考

- - IT技术博客大学习
在做一些web相关的工作的时候,我们往往可能需要做一些对url的处理,其中包括对相似的url的识别和处理. 这就需要计算两个url的相似度. 那么怎么进行url相似度的计算的. 我首先想到的是把一个url看作是一个字符串,这样就简化成两个字符串相似度的计算. 字符串相似度计算有很多已经比较成熟的算法,比如“ 编辑距离算法”,该算法描述了两个字符串之间转换需要的最小的编辑次数;还有一些其他的比如“ 最长公共字串”等方法.

相似度计算常用方法综述

- - 搜索研发部官方博客
       相似度计算用于衡量对象之间的相似程度,在数据挖掘、自然语言处理中是一个基础性计算. 其中的关键技术主要是两个部分,对象的特征表示,特征集合之间的相似关系. 在信息检索、网页判重、推荐系统等,都涉及到对象之间或者对象和对象集合的相似性的计算. 而针对不同的应用场景,受限于数据规模、时空开销等的限制,相似度计算方法的选择又会有所区别和不同.

如何计算两个文档的相似度(一)

- - 我爱自然语言处理
前几天,我发布了一个和在线教育相关的网站: 课程图谱,这个网站的目的通过对公开课的导航、推荐和点评等功能方便大家找到感兴趣的公开课,特别是目前最火的Coursera,Udacity等公开课平台上的课程. 在发布之前,遇到的一个问题是如何找到两个相关的公开课,最早的计划是通过用户对课程的关注和用户对用户的关注来做推荐,譬如“你关注的朋友也关注这些课程”,但是问题是网站发布之前,我还没有积累用户关注的数据.

如何计算两个文档的相似度(三)

- - 我爱自然语言处理
上一节我们用了一个简单的例子过了一遍 gensim的用法,这一节我们将用 课程图谱的实际数据来做一些验证和改进,同时会用到 NLTK来对课程的英文数据做预处理. 为了方便大家一起来做验证,这里准备了一份Coursera的课程数据,可以在这里下载: coursera_corpus,总共379个课程,每行包括3部分内容:课程名\t课程简介\t课程详情, 已经清除了其中的html tag, 下面所示的例子仅仅是其中的课程名:.

如何计算两个文档的相似度(二)

- - 我爱自然语言处理
上一节我们介绍了一些背景知识以及 gensim , 相信很多同学已经尝试过了. 这一节将从gensim最基本的安装讲起,然后举一个非常简单的例子用以说明如何使用gensim,下一节再介绍其在 课程图谱上的应用. 二、gensim的安装和使用. gensim依赖 NumPy和 SciPy这两大Python科学计算工具包,一种简单的安装方法是pip install,但是国内因为网络的缘故常常失败.

文本相似度计算-google的simHash汉明距离

- - 行业应用 - ITeye博客
       针对文本相似性计算,很多开发朋友首先想到的应该是使用向量空间模型VSM(Vector Space Model). 使用VSM计算相似度,先对文本进行分词,然后建立文本向量,把相似度的计算转换成某种特征向量距离的计算,比如余弦角、欧式距离、Jaccard相似系数等. 这种方法存在很大一个问题:需要对文本两两进行相似度比较,无法扩展到海量文本的处理.

相似度计算常用方法综述

- - 互联网实践
相似度计算用于衡量对象之间的相似程度,在数据挖掘、自然语言处理中是一个基础性计算. 其中的关键技术主要是两个部分,对象的特征表示,特征集合之间的相似关系. 在信息检索、网页判重、推荐系统等,都涉及到对象之间或者对象和对象集合的相似性的计算. 而针对不同的应用场景,受限于数据规模、时空开销等的限制,相似度计算方法的选择又会有所区别和不同.

IKAnalyzer中文分词,计算句子相似度

- - 两只蜗牛 - 关注生活,关注旅游
IKAnalyzer中文分词,计算句子相似度.     IKAnalyzer是一个开源的,基于java语言开发的轻量级的中文分词工具包. 以开源项目Luence为应用主体的,结合词典分词和文法分析算法的中文分词组件. 独立于Lucene项目,同时提供了对Lucene的默认优化实现. (简介来源: 百度百科).