前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Simhash海量数据之鸽笼原理的应用

Simhash海量数据之鸽笼原理的应用

原创
作者头像
netkiddy
修改2019-04-23 11:11:11
1.2K0
修改2019-04-23 11:11:11
举报
文章被收录于专栏:非典型程序猿

导语

上一文中从0到1,了解NLP中的文本相似度说到了simhash,结尾的时候,我们提到其主要适用于在海量数据比较时候高效率,那么具体是如何实现的呢?

首先我们来描述下问题:

当我们在使用simhash比较时,依然是对文本进行一一比对,按这个思路,在海量数据几百亿的数量下,这与通过余弦复杂度直接比较的时间复杂度完全一样,随着文本的增多,几乎无法得到适用。

鸽笼原理

针对这个问题,Google在论文中也给出了相应的解决方案,方案中借助的数学原理,就是鸽笼原理。在我们具体介绍方法之前,先来看一下鸽笼原理,根据Wiki百科介绍,对于鸽笼原理,最为简单的一种表述法为:

  • 若有n个笼子和n+1只鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少2只鸽子。

另一种表述为:

  • 若有n个笼子和kn+1只鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少k+1只鸽子。

集合论的表述如下:

  • 若A是n+1元集,B是n元集,则不存在从A到B的单射

从上述描述来看,鸽笼原理是非常简单的,然而,在实际使用鸽笼原理经常会得到一些有趣的结论,这在上述的wiki页面上有着详细的描述,就不在这赘述了。

问题分解

那么当我们了解了鸽笼原理之后,再回过头来看看上面simhash的问题,首先我们做一些前提假设:

  • 我们simhash中使用的fingerprint为64bit
  • 判定为相似的汉明距离为<=3

此时,对于两个fingerprint A和B,我们将它们每16bit一组分别划分为4组:

  • A0(0-15bit),A1(16-31bit),A2(32-47bit),A3(48-63bit);
  • B0(0-15bit),B1(16-31bit),B2(32-47bit),B3(48-63bit);

我们将上述的64bit分割出来的4组分别看成4个鸽笼,如果A和B是两个相似的fingerprint(即他们的bit位差距最大为3bit),我们就可以将这3个不同的bit位我们可以看成是3个鸽子。那么,在0~3共4个分组(笼子)中,肯定有一个笼子是空的。因此,我们可以得出这样的结论:对于两个64bit的fingerprint,当判定相似的汉明距离为3时,两两相似的fingerprint必定有一份16bit是完全相同的。

在得到上述的知识之后,我们便可以通过降维来大幅度降低simhash的比较次数。由于我们无法事先得知完全相同的是哪一块区域,因此我们必须采用存储多份table的方式。在本例的情况下,我们需要存储4份table,并将64位的simhash code等分成4份。然后将4份数据通过K-V数据库或倒排索引存储起来K为16位截断指纹,V为K相等时剩余的48位指纹集合,查询时候,精确匹配这个指纹的4个16位截断。对于每一个输入的code,我们通过精确匹配的方式,查找前16位相同的记录作为候选记录,如下图所示:

1、将64bit的二进制串每16bit等分成四块;

2、将上述任意一块作为前16bit,总共有四种组合,生成四份table;

3、采用精确匹配的方式查找前16位;

4、如果样本库中存有2^34个fingerprint,则每个table返回2^34/2^16=2^(34-16)=262,144个候选结果,4个table共4*262,144=1,048,576 =100万左右;

通过上述的降维操作,我们可以大大减少了海明距离的计算成本,原来需要比较2^34=171亿次,现在只需要比较100万次,即可得到结果。不过,需要注意的是,table的数量与每个table返回的结果呈此消彼长的关系,也就是说,时间效率与空间效率不可兼得。

参考文献

https://blog.csdn.net/u010454030/article/details/49102565

https://www2007.cpsc.ucalgary.ca/papers/paper215.pdf

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 导语
  • 鸽笼原理
  • 问题分解
  • 参考文献
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档