在前一篇文章 《海量数据相似度计算之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短文本查找

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

  1. 您好,我有点没看懂,能麻烦解释一下吗======================原文======================查找:1、将需要比较的simhash code拆分成4个16位的二进制码。2、分别拿着4个16位二进制码每一个去查找simhash集合对应位置上是否有元素。2、如果有元素,则把链表拿出来顺序查找比较,直到simhash小于一定大小的值,整个过程完成。======================原文======================step 2拿出四个list,step 3是把这四个list里的元素都比一遍 对于海明距离小于某个阈值的就认为相似或者重复 就不接着找了。是这么理解的吗?

  2. 不好意思,最近在外面休婚嫁,大概说一下:先是变成4的map,每个map的key值有一个list,然后先根据map找到key,再遍历key里的list

  3. 你好 挺喜欢你的comment部分,但是有一个bug,回复第一条comment的时候,会新发一条comment,而不是回复。另外可以分享一下你的这部分源代码吗?zzc3615@gmail.com

  4. 你说的是查找吗?只要有一个索引片的距离小于一定的比例,这个就判断为相似,不用找其他索引片了。不需要把所有索引片加在一起计算汉明距离

  5. 我有点明白你的思路了,跟我做的(我猜想)还是有蛮多不一样的。我做的是这样的,比如分4片,每片16bits,假设总距离最大是10,那么每一片需要查找的最大距离就是ceil(2.5) = 3。为16bit生成一个3个1、13个0的全排列,这就是需要查找的所有可能的hash码,在每片上找到以后,还需要与64bit的全码比较,如果确实全距离<=10,就算做相似。根据我用的测试数据,16bits相近而总距离相差较多的比例非常大,所以我是二次查找的。有可能你用的数据符合某种特性(确实我用的既不是文本也不是simhash),所以不需要再检查一次全距离

  6. 存储: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小于一定大小的值,整个过程完成。这个过程感觉还不是很明了,我想问这个元素是个什么样的元素?

  7. 我测试跑了花140ms,很不客气的说,请求分享博主源码,wushuiyong@huamanshu.com

  8. “2、分别拿着4个16位二进制码每一个去查找simhash集合对应位置上是否有元素。” 博主,你好!如果每个16位对应的simhash数量过多的话,遍历比较同样很耗时,这个有办法继续优化一下吗?

  9. 博主问一下,为什么要切分成四个16位的map,而不是8个8位的map呢,难道不可以吗?是因为切分成8位的计算量大吗?还是有其他原因。

  10. 您好,问一下simhash对于长文本准确性还行,但对于短文本来说,准确性没有那么理想,你现在有什么好的解决方案了吗?望指教。

  11. 博主,我貌似知道了为什么是16位了,因为二进制最高位数是16位,不知道理解的对不对。

  12. 博主说了,具体选择16位、8位、4位,大家根据自己的数据测试选择,虽然比较的位数越小越精准,但是空间会变大。

  13. 你这样说也是可以的,不过更关键的原因是空间和时间的取舍,你想取8位也是可以,不过占用的空间更大,如果你数据量不大或者有这么多内存也是没关系的

  14. 单个程序不同的机器有可能达不到,看下你的机器配置,数据量,我们是在8核 16G,10个线程同时运行得出来的一个线性时间

  15. “对应位置没有元素,直接追加到链表上;对应位置有则直接追加到链表尾端。”前半句 对应位置没有元素,直接追加到链表上 是什么意思?

  16. 查找过程和插入过程是同时进行的,就是说对应位置还没有此文本的simhash值,就把这个值加到链表上,下次遇到相同的simhash值就能过滤了

  17. “分别拿着4个16位二进制码每一个去查找simhash集合对应位置上是否有元素”,有两个文本,有4位simhash不一样,4位分别分布在被分成的4个16位中,这样不是查不出这两个文本相似吗?实际上,只有4位simhash不一样,相似度还是挺高的。这里能确保的好像只有3个simhash不一样的一定能查找出来。

  18. 同感,拆分的数量(上述4)要比约定为相似的simhash位数(上述3)大才有用吗?

  19. 根据自己的理解和其他资料(当然包括该篇)写的simhash去重算法介绍。http://blog.csdn.net/sunny_ss12/article/details/46958155

  20. Pingback: [Algorithm] 使用SimHash进行海量文本去重 - IT大道

  21. Pingback: [Algorithm] 使用SimHash进行海量文本去重 - IT大道

  22. Pingback: [Algorithm] 使用SimHash进行海量文本去重 | 07客博客

  23. 如果你的总距离最大是10集中在4个分片中的某一个分片时,是不是“每一片需要查找的最大距离就是ceil(2.5) = 3”这句话就不合理了?

  24. 博主高人,那么我还想问下:如果不是短文比对,而是用这篇短文内的一段话来比对找到对应的短文该用哪种方法啊?谢谢了!

  25. 你这个其实是有问题的,四个片都要查找,另外你怎么确认命中的哪四片是一个simhash拆分出来的。而且就算你知道 你需要四片都对比才准确,不然被你漏掉的片距离很大呢。

  26. 其实不是要查文本,而是要查是不是有相似文本,所以其实楼主这个方法我觉得从根本上就是错的。

required

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> 

注意: 评论者允许使用'@user空格'的方式将自己的评论通知另外评论者。例如, ABC是本文的评论者之一,则使用'@ABC '(不包括单引号)将会自动将您的评论发送给ABC。使用'@all ',将会将评论发送给之前所有其它评论者。请务必注意user必须和评论者名相匹配(大小写一致)。