一、什么是SimHash

SimHash算法是Google在2007年发表的论文《Detecting Near-Duplicates for Web Crawling》中提到的一种指纹生成算法，被应用在Google搜索引擎网页去重的工作之中。

对于文本去重这个问题，常见的解决办法有余弦算法、欧式距离、Jaccard相似度、最长公共子串等方法。但是这些方法并不能对海量数据高效的处理。 比如说，在搜索引擎中，会有很多相似的关键词，用户所需要获取的内容是相似的，但是搜索的关键词却是不同的，如“北京好吃的火锅“和”哪家北京的火锅好吃“，是两个可以等价的关键词，然而通过普通的hash计算，会产生两个相差甚远的hash串。而通过SimHash计算得到的Hash串会非常的相近，从而可以判断两个文本的相似程度。

二、局部性敏感哈希

说到hash可能我们第一个想到的是md5这种信息摘要算法，可能两篇文本只有一个标点符号的差距，但是两篇文本A和B的md5值差异就非常大，感兴趣的可以试验一下看看。

有时候我们希望的是原本相同的文章做了微小改动之后的哈希值也是相似的，这种哈希算法称为局部敏感哈希LSH(Locality Sensitive Hashing)，这样我们就能从哈希值来推断相似的文章。

局部敏感哈希算法使得在原来空间相似的样本集合，进行相关运算映射到特定范围空间时仍然是相似的，这样还不够，还需要保证原来不相似的哈希之后仍然极大概率不相似，这种双向保证才让LSH的应用成为可能。

三、simhash的基本过程

SimHash算法主要有五个过程：分词、Hash、加权、合并、降维。

1.分词（可以用一些分词工具来实现）

使用分词手段将文本分割成关键词的特征向量，分词方法有很多，我用了jieba分词来实现，你可以先去除停用词，当然也可以不去除，根据自己的需求选择，假设分割后的特征实词如下：

12306 服务器 故障 车次 加载失败 购买 候补订单 支付 官方 消费者 建议 卸载 重装 切换网络 耐心 等

目前的词只是进行了分割，但是词与词含有的信息量是不一样的，比如12306 服务器 故障 这三个词就比 支付 卸载 重装更能表达文本的主旨含义，这也就是所谓信息熵的概念。 为此我们还需要设定特征词的权重，方法有很多，简单一点的可以使用TF-IDF来实现。

2.Hash

前面我们使用分词方法和权重分配将文本就分割成若干个带权重的实词，比如权重使用1-5的数字表示，1最低5最高，这样我们就把原文本处理成如下的样式：

12306(5) 服务器(4) 故障(4) 车次(4) 加载失败(3) 购买(2) 候补订单(4) 支付(2) 官方(2) 消费者(3) 建议(1) 卸载(3) 重装(3) 切换网络(2) 耐心(1) 等待(1)

然后，通过hash函数对每一个词向量进行映射，产生一个n位二进制串，一般常用的位数为32、64、128。

3.加权

前面的计算我们已经得到了每个词向量的Hash串和该词向量对应的权重，这一步我们计算权重向量W=hash*weight。 具体的计算过程如下：hash二进制串中为1的，w = 1 * weight，二进制串中为0的，w = weight * -1. 举个例子，12306的带权重哈希值为 [5 -5 -5 5 5 5 -5 -5]，服务器的带权重哈希值为 [-4 4 4 4 -4 4 -4 4]

4.合并

对于一个文本，我们计算出了文本分词之后每一个特征词的权重向量，在合并这个阶段，我们把文本所有词向量的权重向量相累加，得到一个新的权重向量，假定最终结果为 [18 9 -6 -9 22 -35 12 -5]

5.降维

对于前面合并后得到的文本的权重向量，大于0的位置1，小于等于0的位置0，就可以得到该文本的SimHash值，以上面提到的 [18 9 -6 -9 22 -35 12 -5] 为例，我们得到 [1 1 0 0 1 0 1 0] 这个bit串，也就是论文中提及的该文本的指纹。 到此为止，我们已经计算出了一个文本的SimHash值。那么，如何判断两个文本是否相似呢？我们要用到海明距离。

四、相似度判断

对于两个文本的SimHash的相似度判断，我们使用海明距离来计算。 什么是海明距离呢？ 简单的说，海明距离可以理解为，两个二进制串之间相同位置不同的个数。

举个例子，[1，1，1，0，0，0]和[1，1，1，1，1，1]的海明距离就是3。

在处理大规模数据的时候，我们一般使用64位的SimHash，正好可以被一个long型存储。这种时候，海明距离在3以内就可以认为两个文本是相似的。 五、大规模数据下的海明距离计算 我们在存储时将64bit simhash值均分为4份每份16bit长，然后使用每一份作为key，value是每一份simhash值对应的二进制向量： 当新来一个文本生成哈希值S’之后，按照相同的规则生成abcd四部分，之后逐个进行哈希对比，这个时间复杂度是O(1)： 如果abcd四个作为key都不存在，那么可以认为S’没有相似的文本； 如果abcd四个key中有命中，那么就开始遍历对应key的value，查看是否满足<=3的海明距离确定相似性；（一般64位编码的simhash值对应的海明距离阈值设为3） 如果上一个命中的key未找到相似文本，则继续遍历剩下的key，重复相同的过程，直至所有的key全部遍历完或者命中相似文本，则结束。 六、参考文献： https://blog.csdn.net/Daverain/article/details/80919418 ↗ https://cloud.tencent.com/developer/article/1189493 ↗

文章二

本文要解决的是这样一个问题：

有一段文本线索：

“延安西路921号，进门左边第三棵树，有一个一百三十年前的……”

我想从一个亿级数据库里，把包含这段线索的相似文本都捞出来，找到它背后更多的故事。 这是一个相似匹配的问题（文本相似匹配基础→ 词频与余弦相似度）。但是，亿级数据库，用传统的相似度计算方法太慢了，我们需要一个文本查询方法，可以快速的把一段文本的相似文本查出来。

在实际的文本处理工作中，不解决海量查询这一基本问题，耗时等待是非常可怕的。比如我们时常要对海量相似文本进行去重、或者对海量相似文本的聚类等。

具体场景为：在搜索引擎中查询一段文本，10分钟后才能返回？对微博上某种近一周的文本进行聚类，要等1个月？（说到聚类，效果好一点的聚类方法如DBSCAN，时间复杂度很高，耗时是非常让人绝望的，这个后续还会介绍）。

你会发现，很多时候，如果不先解决掉大规模相似文本的问题，后面很多高大上的分析、模型都做不了，这也是为什么我文本分析这个系列中，我先介绍“大规模文本处理”，而没有先介绍word2vec、LSTM等方法的原因。

在前面的文章里（→哈希函数），我们介绍过一种叫哈希函数的东西，他可以把文本转换成一段哈希指纹。从而对文本进行量化降维。但是，我们希望转换之后，相似的文本还能保持相似，比如 “最美数说君”，hash之后是 12345，“最帅数说君”，hash之后是12346，还能保持差不多的相似。这个是最难的，满足这种特性的hash函数，叫做局部敏感性哈希（LSH）。

本文要介绍的SimHash，就是其中的一种，谷歌就是用它来对海量文本进行去重。

一、SimHash原理

1、Simhash的使用

Simahash方法最早由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出。SimHash是将一段文本hash成一串二进制的指纹（如0010110），然后配用海明距离进行两两文本的比较。海明距离，说白了就是看两段二进制指纹有多少不一样，具体可以看这里→ 常用距离/相似度 一览。流程如下图所示：

一般来说，如果海明距离小于3，则认为这两个文本是相似文本。那么SimHash是如何计算的呢？

2、Simhash 的计算

我们以 “Python is sexy” 为例，展示以下 一段文本的SimHash过程：

先给一个总的流程图：

（1）分词、给定权重

首先是分词，且给定每一个词的权重。

这里我们采用四字母为单位来切词（我们把大小写归一化、空格去掉），权重统一为1：

[Pyth：1, ytho：1, thon：1, honi：1, onis：1, niss：1, isse：1, ssex：1, sexy：1]

（2）传统hash

把每一个词用传统方法hash成数字（即 hashcode），这里位数根据存储成本和数据集大小来选取，一般多选64位：

Pyth：
0010001010010001101111101000111010100011110110111010100010110011


ytho：
0001110111100111000110010001111000001001001111000110110100011000


......

（3）加权

每一个分词的 hashcode 中，对应位上如果为1，则该位加上权重w，这里权重为1，即+1,；对应位上如果不为1，则该位减去权重w，这里即-1。

Pyth：
-1 -1 2 -1 -1 -1 2 -1 2 -1 -1 2 -1 -1 -1 2 2 -1 2 2 2 2 2 -1 2 -1 -1 -1 2 2 2 -1 2 -1 2 -1 -1 -1 2 2 2 2 -1 2 2 -1 2 2 2 -1 2 -1 2 -1 -1 -1 2 -1 2 2 -1 -1 2 2


ytho：
-1 -1 -1 2 2 2 -1 2 2 2 2 -1 -1 2 2 2 -1 -1 -1 2 2 -1 -1 2 -1 -1 -1 2 2 2 2 -1 -1 -1 -1 -1 2 -1 -1 2 -1 -1 2 2 2 2 -1 -1 -1 2 2 -1 2 2 -1 2 -1 -1 -1 2 2 -1 -1 -1


......

（4）合并

现在每个分词都有64位的二进制表示，我们将每一位进行纵向累加，也就是将每个分词的第1位累加，得到总的第1位，每个分词的第2位累加，得到总的第2位，同理第3位、第4位……第64位。最终得到了一个总的64位的二进制表示：

Python is sexy：
-5, -5, -1, 1, 3, -3, -1, -3, -5, -1, -1, 3, 1, -3, 1, -1, 3, -1, -3, 1, 1, -3, 3, -3, -1, 5, -1, 1, -3, 1, -7, 3, 5, -1, 3, -1, 1, 1, -3, -3, 1, -1, -1, -1, -1, 1, -1, 7, 3, 3, -3, -1, 3, 5, 1, 5, -1, -1, 3, 1, 5, 3, 1, -3

（5）0/1处理

对于64位的每一位，如果大于0，则赋值为1，否则为0：

Python is sexy 的最终 simhash 二进制指纹：

0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0

以上，就是一段文本的Simhash过程。它的好处是相似的两段文本，Simhash 之后的值仍然能保持相似，而且经过了降维，储存空间也大大减少，计算效率会提高很多。一般来说，两端simhash的海明距离如果在3以内，就认为是相似文本。

你可能会问，为什么？为什么这种 Hash 方法可以让相似的文本仍然相似？Simhash的发明人 Charikar 的论文中并没有给出具体的证明，但由于 Simhash 是由随机超平面hash算法演变而来的，有人根据这个给出了证明，大家可以搜搜看。

二、加速查询：抽屉原理

虽然 Simhash 可以减少单次计算的耗时，海量文本来说，匹配的计算量还是很大的。如果数据库里有几百亿数据，那就意味着要匹配几百亿次。因此，我们需要一种方法来减少匹配。

对于两段文本，我们分别映射成64位hash指纹之后，再每个文本分为四份，每个部分16位。对于这两段文本，如果海明距离在3以内，则它们对应的4个部分，至少有一个部分是一样的。

因为，海明距离小于3，意味着，最多有3个位点有区别，而3个差异位点分布在四个部分，至少有一个部分是没有相同的。

这就好比把3个球放到4个抽屉里面，一定有一个抽屉是空的，所以叫“抽屉原理”。

基于此，可以把一段64位指纹分成 K-V格式（Key-Value），K就是其中四个部分中的一个部分，V就是剩下3个部分。我们在匹配的时候，只要精确匹配K，K相同了，再去匹配V，这样可以大大减少计算量。

但问题是，我怎么知道差异位点分布在哪一部分？

所以，一段文本的Simhash指纹，我们需要复制成四次存储，以text1为例，simhash 成64位之后，我们分成四个部分，A1-A2-A3-A4。我们把这段存储四份，以使得每一部分都做一次K，剩下其他三个为V：

① K: A1, V: A2-A3-A4

② K: A2, V: A1-A3-A4

③ K: A3, V: A1-A2-A4

④ K: A4, V: A1-A2-A3

这样就可以保证不会有遗漏。

那么，用这一套方法，最终能减少多少查询呢？给大家算一笔账：

假设数据库中有 2^30 条数据，也就是差不多10亿条数据：

如果不用抽屉原理，那么就得与10亿条数据一一查询，即10亿次。 使用了抽屉原理，即与16位的K先查询。 想象一下由0/1组成的16位数字，可能有多少？最多2^16种K（每一位有0/1两种可能，一共有16位，排列组合一下）； 2^30数据，一共2^16种K，那么每个K-V返回的最大数量也就2^(30-16)=16384个候选结果，4个K的话，总的结果也就16384*4=65536，约66W。 这样一来，原来需要比较10亿次，现在只需要比较66万即可。

项目：去Github搜一下就有，可以找来看看，还是比较容易懂的。