算法简介
simHash是用来网页去重最常用的hash方法，速度很快
simhash算法的输入是一个向量，输出是一个f位的签名值。为了陈述方便，假设输入的是一个文档的特征集合，每个特征有一定的权重。比如特征可以是文档中的词，其权重可以是这个词出现的次数。
算法步骤
simhash算法分为5个步骤：分词、hash、加权、合并、降维，具体过程如下所述：
- 分词
给定一段语句，进行分词，得到有效的特征向量，然后为每一个特征向量设置1-5等5个级别的权重。
- hash
通过hash函数计算各个特征向量的hash值，hash值为二进制数01组成的n-bit签名。
- 加权
在hash值的基础上，给所有特征向量进行加权，即W = Hash * weight，且遇到1则hash值和权值正相乘，遇到0则hash值和权值负相乘。
- 合并
将上述各个特征向量的加权结果累加，变成只有一个序列串。
- 降维
对于n-bit签名的累加结果，如果大于0则置1，否则置0，从而得到该语句的simhash值，最后我们便可以根据不同语句simhash的海 明距离来判断它们的相似度。
算法应用
例如：
需要计算“CSDN博客”的simhash签名值为“1 0 1 0 1 1”，假定我们计算出另外一个短语的签名值为“1 0 1 0 0 0”，那么根据异或规则，我们可以计算出这两个签名的海明距离为2，从而判定这两个短语的相似度是比较高的。
简单来说，现在问题转换为：对于64位的SimHash值，我们只要找到海明距离在3以内的所有签名，即可找出所有相似的短语。现在关键是，如何将其扩展到海量数据呢？譬如如何在海量的样本库中查询与其海明距离在3以内的记录呢？
- 一种方案是查找待查询文本的64位simhash code的所有3位以内变化的组合
- 大约需要四万多次的查询
- 另一种方案是预生成库中所有样本simhash code的3位变化以内的组合
- 大约需要占据4万多倍的原始空间
这两种方案，要么时间复杂度高，要么空间复杂度复杂，能否有一种方案可以达到时空复杂度的绝佳平衡呢？答案是肯定的：
- 我们可以把 64 位的二进制simhash签名均分成4块，每块16位。根据鸽巢原理（也称抽屉原理），如果两个签名的海明距离在 3 以内，它们必有一块完全相同。
- 然后把分成的4 块中的每一个块分别作为前16位来进行查找，建倒排索引。
这样看来，如果样本库中存有2^34的simhash签名，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本。
- 假设数据是均匀分布，16位的数据，产生的像限为2^16个，则平均每个像限分布的文档数则为2^34/2^16 = 2^(34-16)) ，四个块返回的总结果数为 4* 262144。
- 原本需要比较10亿次，经过索引后，大概只需要处理100万次。
閱讀更多 咱小二 的文章
