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