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

导语

上一文中从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

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

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

编辑于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券