文本相似度判断-simhash算法学习笔记

Note: This article is available in Chinese only. 本文暂无英文版本。 View original

先放原始论文。。以此表达对这个算法的敬意 orz

论文链接

问题引出：
#

那天百度一面，frog 学姐问了我如何判断两篇新闻稿相似度的问题….我满篇口胡，也只是回答了一些诸如从图片上考虑、或者去掉 stop word 之后得到特征向量再计算余弦值之类的传统想法。

今天看到了 Google 在用的网页去重算法（？）。感觉好神奇，准备面试到现在，第一个让我感到惊异而不是套路的算法 orz

对于处理**大规模文本（500 字以上吧）**的时候效果很好，但是算法思想却又非常简单。

这才是算法的美丽之处吧。leetcode 上的那些纱布技巧也好意思叫算法？

网页去重，其实本质还是网页相似度的计算，首先是两篇，之后还可以推广到海量数据。

算法初探：
#

simhash 算法，字面上也可以看出，是一种 hash 算法，那么它和一般的 hash 有什么不同呢？

最大的问题在于，传统 hash 的设计目的之一是使得映射后的值的分布尽可能均匀，对于同样的 key 会有同样的 value，但是每当 key 有轻微的变化的时候，value 就会千差万别。

举个例子：

“你妈妈喊你回家吃饭哦，回家罗回家罗” 和 “你妈妈叫你回家吃饭啦，回家罗回家罗”。
通过simhash计算结果为：
1000010010101101111111100000101011010001001111100001001011001011
1000010010101101011111100000101011010001001111100001101010001011
通过 hashcode计算为：
1111111111111111111111111111111110001000001100110100111011011110
1010010001111111110010110011101

也就是说，没办法通过 hash 之后得到的值的差异，去分析 key 的相似程度。

而 simhash 就是通过某种方法进行 hash，使得 hash 之后得到的 value 可以反映 key 的相似度。

流程
#

simhash算法分为5个步骤：分词、hash、加权、合并、降维，具体过程如下所述：
分词
给定一段语句，进行分词，得到有效的特征向量，然后为每一个特征向量设置1-5等5个级别的权重（如果是给定一个文本，那么特征向量可以是文本中的词，其权重可以是这个词出现的次数）。例如给定一段语句：“CSDN博客结构之法算法之道的作者July”，分词后为：“CSDN 博客结构之法算法之道的作者 July”，然后为每个特征向量赋予权值：CSDN(4) 博客(5) 结构(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5)，其中括号里的数字代表这个单词在整条语句中的重要程度，数字越大代表越重要。
hash
通过hash函数计算各个特征向量的hash值，hash值为二进制数01组成的n-bit签名。比如“CSDN”的hash值Hash(CSDN)为100101，“博客”的hash值Hash(博客)为“101011”。就这样，字符串就变成了一系列数字。
加权
在hash值的基础上，给所有特征向量进行加权，即W = Hash * weight，且遇到1则hash值和权值正相乘，遇到0则hash值和权值负相乘。例如给“CSDN”的hash值“100101”加权得到：W(CSDN) = 100101 _4 = 4 -4 -4 4 -4 4，给“博客”的hash值“101011”加权得到：W(博客)=101011 _5 = 5 -5 5 -5 5 5，其余特征向量类似此般操作。
合并
将上述各个特征向量的加权结果累加，变成只有一个序列串。拿前两个特征向量举例，例如“CSDN”的“4 -4 -4 4 -4 4”和“博客”的“5 -5 5 -5 5 5”进行累加，得到“4+5 -4+-5 -4+5 4+-5 -4+5 4+5”，得到“9 -9 1 -1 1”。
降维
对于n-bit签名的累加结果，如果大于0则置1，否则置0，从而得到该语句的simhash值，最后我们便可以根据不同语句simhash的海明距离来判断它们的相似度。例如把上面计算出来的“9 -9 1 -1 1 9”降维（某位大于0记为1，小于0记为0），得到的01串为：“1 0 1 0 1 1”，从而形成它们的simhash签名。
每篇文档得到SimHash签名值后，接着计算两个签名的海明距离即可。根据经验值，对64位的 SimHash值，海明距离在3以内的可认为相似度比较高。
海明距离的求法：异或时，只有在两个比较的位不同时其结果是 1，否则结果为 0，两个二进制“异或”后得到 1 的个数即为海明距离的大小。

推广到海量数据：
#

关键是，如何将其扩展到海量数据呢？譬如如何在海量的样本库中查询与其海明距离在3以内的记录呢？
一种方案是查找待查询文本的64位simhash code的所有3位以内变化的组合
大约需要四万多次的查询。
另一种方案是预生成库中所有样本simhash code的3位变化以内的组合
大约需要占据4万多倍的原始空间。
这两种方案，要么时间复杂度高，要么空间复杂度复杂，能否有一种方案可以达到时空复杂度的绝佳平衡呢？答案是肯定的：
我们可以把 64 位的二进制simhash签名均分成4块，每块16位。根据鸽巢原理（也称抽屉原理），如果两个签名的海明距离在 3 以内，它们必有一块完全相同。如下图所示：
然后把分成的4 块中的每一个块分别作为前16位来进行查找，建倒排索引。
具体如下图所示：
如此，如果样本库中存有2^34（差不多10亿）的simhash签名，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本。
假设数据是均匀分布，16位的数据，产生的象限为2^16个，则平均每个象限分布的文档数则为2^34/2^16 = 2^(34-16)，四个块返回的总结果数为 4×262144（大概 100 万）。
这样，原本需要比较10亿次，经过索引后，大概只需要处理100万次。