`

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

阅读更多

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

4
4
分享到:
评论

相关推荐

    短文本相似度计算

    在IT领域,尤其是在信息检索与自然语言处理方向,短文本相似度计算是一个核心议题,它涉及到如何有效地评估两段简短文本之间的语义关联性。本文将深入探讨短文本相似度计算的关键方法与挑战,基于《短文本相似度计算...

    paddle_nlp_之词或者句子相似度计算.zip

    本压缩包文件“paddle_nlp_之词或者句子相似度计算.zip”可能包含了一些使用PaddleNLP实现的词和句子相似度计算的示例代码或教程,旨在帮助用户理解和应用相关技术。 首先,我们来了解一下词和句子相似度计算的基本...

    文本语义相似度计算方法研究及应用

    文本相似度计算一直是自然语言处理领域研究中的一个基础问题。而文本语义相似度计算则是在文本相似度计算基础上增加了语义分析,在语义层面对文本相似度作进一步的分析研究,具有广阔的应用背景。本文针对句子级别的...

    基于深度学习的短文本语义相似度计算

    基于深度学习的短文本语义相似度计算,通过深度学习的思想计算语义相似度

    文本相似度计算

    在压缩包中的"similarity"文件,可能是包含示例代码、数据集或教程,用于展示如何利用Levenshtein距离或其他方法进行文本相似度计算。通过学习这些资源,我们可以深入理解如何将这些理论知识应用于实际项目,解决如...

    中文短语文本相似度计算新方法.pdf

    ### 中文短语文本相似度计算新方法 #### 一、引言 本文介绍了一种新的中文短语文本相似度计算方法,旨在解决短语文本的分类、聚类以及信息查询等问题。通过合理地计算文本之间的相似度及其变化趋势,这种方法能够...

    中文短语相似度计算方法研究及应用

    在信息大爆炸所带来的大量文本信息的数据堆积中,很大一部分是短文本数据或短语数据,因此,在短文本数据信息的处理问题上,短语的相似度计算变得越来越重要。本文就是针对中文短语信息的处理问题,提出了一种新的中文...

    【短文本相似度】传统方法BM25解决短文本相似度问题.pdf

    本文将详细介绍BM25算法,并通过具体的编程代码来展示如何实现BM25算法用于短文本相似度计算。 首先,BM25算法是基于概率模型的信息检索领域的算法。它的核心思想是在计算文档与查询的相似度时,将文档长度和查询项...

    弦相似算法计算 短文本相似度

    综上所述,短文本相似度计算涉及到多种算法,如弦相似性(编辑距离)、Jaccard相似度以及TF-IDF。在实际应用中,根据具体需求选择合适的算法或组合使用,能更准确地评估文本之间的相似程度。而源码软件则为开发者...

    孪生网络(SiameseNetwork)在句子语义相似度计算中的应用

    伪孪生网络:两个网络结构相同但不共享参数,或者两个网络结构不同,当两个句子结构上不同,或者来自不同的领域,或者时句子和图片之间的相似度计算时选择该模型;另外孪生网络的损失函数一般选择Contras

    人工智能-深度学习-基于深度学习的中文句子相似度计算研究.pdf

    随着互联网技术的飞速发展和信息化建设的进步,中文短文本数据在互联网上激增。这为自然语言处理中的关键任务——句子相似度计算带来了新的挑战和机遇。句子相似度计算在信息检索、文本分类、机器翻译、智能客服问答...

    基于汉明距离的文本相似度计算

    - **适应性强**:适用于各种类型的文本数据,无论是短文本还是长文档都能有效处理。 #### 结论 本文提出了一种基于汉明距离的文本相似度计算方法,该方法通过将文本转换为二进制码字的形式,利用汉明距离来衡量...

    短文本数据分类

    随着互联网的快速发展,海量的短文本数据在网络上不断产生,比如社交媒体上的帖子、产品评论、新闻标题等。这些短文本虽然简短,但蕴含着丰富的信息,对于企业了解用户需求、把握市场趋势具有重要意义。因此,如何...

    调用百度AI平台上的短文本相似度API

    调用百度AI平台上的短文本相似度API,调用api接口,实现测试。

    simhash算法的java实现simhash-java.zip

    特点计算字符串的 simhash通过构建智能索引来计算所有字符串之间的相似性,因此可以处理大数据使用使用输入文件和输出文件运行 Maininputfile 的格式(参见 src / test_in):一个文件每行用 utf8 字符集outputfile...

    人工智能大作业:关于计算文本相似度的深度神经网络模型与算法研究分析(BERT、SentenceBERT、SimCSE).zip

    在文本相似度计算中,BERT可以生成高质量的文本表示,使得相似文本在向量空间中距离更近。 SentenceBERT则是BERT的一个扩展,专门针对句子级别的表示进行了优化。它通过引入句子对的联合训练,使得模型能更好地捕捉...

    simhash算法

    - 对于短文本,可以考虑结合其他方法如TF-IDF、词向量(Word2Vec、GloVe等)来增强Simhash的表现,或者增加文本的上下文信息,提高相似度计算的准确性。 总之,Simhash算法在文本相似度检测中具有较高的效率和精度...

    论文研究-基于词项语义组合的文本相似度计算方法研究.pdf

    文本之间在相似度比较时...将这种结合关键词组合关系的相似度比较方法运用于短文本的相似度比较中,数据采用微软语义释义语料库,实验结果表明,短文本相似度计算的准确率和F1值都有了提高,其中F1值的提高较为明显。

Global site tag (gtag.js) - Google Analytics