simhash算法的方法介绍背景有一天，面试官问我如何设计比较两篇文章相似度的算法。 关于传统点，你可能会回答一些想法：
一种方案是先将两篇文章分别分词，得到一系列特征向量，然后计算特征向量之间的距离，以距离大小判断两篇文章的相似度。 另一种方案是传统的散列，考虑对每个web文档以散列方式生成指纹(finger print )。 那么，让我们来分析一下这两种方法。
第一种方法，如果只比较两个文章的相似性，但如果是庞大的数据，就有几百万到几亿页，要求计算这些页面的相似度。 也可以计算任意两页之间的距离或角度吗？ 你不会再做了吧。 第二个方案中叙述的传统的加密方式md5，以使分布整体尽可能均匀为目的，但只要输入内容稍有变化，哈希值就会有很大的变化。 例如，假设您有以下三个文本：
在thecatsatonthematthecatsatonamatweallscreamforicecream中使用传统混列可能会导致以下结果：
IRB(main ) :00633600 P1=' thecatsatonthemat ' IRB ) main ) :00733600 P1.hash=415542861 IRB (main ) ) ) ) )。005:0 p2=' thecatsatonamat ' IRB (main ) :00733600 p2.hash=668720516 IRB (main ) ) ) ) )。007:0 P3=' weallscreamforicecream ' IRB (main ) :007:0 p3.hash=767429688 '对于几乎相同的输入内容，理想的hash函数
出人头地的车在到达山上之前一定有路。 从GoogleMoses Charikar发表的论文“detecting near-duplicatesforwebcrawling”中提出simhash算法，解决亿万级别网页的繁重任务。
simhash作为locality sensitive hash（局部敏感哈希）的一种： 其主要思想是降维，将高维的特征向量映射成低维的特征向量，通过两个向量的Hamming Distance来确定文章是否重复或者高度近似。 其中，Hamming Distance，又称汉明距离，在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。也就是说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如：1011101 与 1001001 之间的汉明距离是 2。至于我们常说的字符串编辑距离则是一般形式的汉明距离。如此，通过比较多个文档的simHash值的海明距离，可以获取它们的相似度。
流程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的个数即为海明距离的大小。举个例子，上面我们计算到的“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（差不多10亿）的simhash签名，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本。
假设数据是均匀分布，16位的数据，产生的像限为2^16个，则平均每个像限分布的文档数则为2^34/2^16 = 2^(34-16)) ，四个块返回的总结果数为 4* 262144 （大概 100 万）。 这样，原本需要比较10亿次，经过索引后，大概只需要处理100万次。（部分内容及图片参考自：http://grunt1223.iteye.com/blog/964564 ，后续图片会全部重画）
来源：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/06.03.md