SimHash是一种文本表示的方法，和TF-IDF一样，但是TF-IDF需要遍历所有文本来计算得到文本的表示，计算量较大。

一.SimHash的计算过程

1.分词

对于中文文本来说，一般都要先进行分词才能进一步得到文本的表示向量。

首先按照一定粒度进行分词，比如‘我爱编程’这句话，可以切分为‘我/爱/编程’

2.将分词结果映射为定长的二进制编码

比如经过hash算法之后，得到的hash值为
我 1 0 1 0
爱 0 1 1 0
编程 1 0 0 0

3.将二进制编码进行转换

将二进制编码中的‘0’变成‘-1’。其目的是将映射后的词语放置在整个空间中，而不是某一个象

限，这样可以让数据点分布得更均匀一点。

则新的编码为：

我 1 -1 1 -1
爱 -1 1 1 -1
编程 1 -1 -1 -1

4.计算文档的初始编码

将所有词语的编码加起来则变成： 1，-1， 1， -3

5.计算文档的最终编码

将文档编码中大于0的元素写为1，小于0的元素写为0，则最终编码为： 1，0， 1， 0

二.SimHash的去重过程

方法一.通过比较文本与文本之间的海明距离

计算每两篇文档之间的海明距离，然后对距离不超过3的文档对进行去重处理。这样的话，我们需要计算(M-1+0)*M/2词相似度，计算量非常大。

方法二.倒排索引

我们可以使用倒查索引来降低计算量。以64位simhash编码表示的数据集为例，我们可以构建64个倒查索引，对应simhash码的64个维度；每个倒查索引只有两个key，即0和1，表示文本编码在这个维度上的取值；这样，我们就可以把所有的文档，按照simhash编码在各维度上的取值，放到各个倒查索引中。

在实际去重的时候，每遍历到一个不重复的文档，就把它添加到64个倒查索引中。

在考察一篇文档是否重复的时候，我们首先把64个倒查索引中，与当前文档编码匹配的部分召回，然后比对当前文档与召回文档的相似度，进而判断是否重复。这种查询方式比4.1所述的方式，需要比对的次数要少很多。

当然，这种倒查索引的key还是比较稠密，每次查询会召回比较多的文档。

参考 https://zhuanlan.zhihu.com/p/92155250

cs