要判断两篇文章是否相同，我们可以使用文章的 md5 来判断。但是，一般情况下，文章可能只是改动了一小部分，在搜索引擎中，这种情况是非常常见的，所以需要一种算法来检测相似的文章（near-duplicate)。Simhash 是一个相似度散列算法，也就是说内容相似的文本会产生近似的哈希值。Google 就使用 simhash 作为网页判重的标准。

Simhash 通常采用 64-bit 的数字来作为一个文章的代表，而当两个文章的哈希值差异小于等于 3 位的时候，也就是汉明距离小于等于 3 的时候。

simhash 计算过程

生成 shingle, n-shingling 就是把一个句子或者文章分成 n 个连续单词的组合，然后去重。

比如： the cat sat on the cat

第一步，分组： the cat, cat sat, sat on, on the, the cat
第二步，去重： the cat, cat sat, sat on, on the

文章相似度的检测主要分为两个部分：

1. 哈希值的构建，也就是 simhash 的算法
2. 查询系统，给定一篇文章，我们需要查询与他 hash 值类似的文章。

对于中文的 Simhash 计算，首先需要的是分词。但是，不同的分词软件，甚至不同的版本，可能产生截然不同的词，这也就会导致同一个文本计算出来的 Simhash 都不一样。考虑到算法的稳定性，分词并不是一个很好的方案，还不如直接用 3-gram.

工程实现

整个工程实现需要以下几个步骤：

1. 文本预处理
2. 倒排索引建立
3. 查询索引建立 group

4.

海量文本聚类

来自参考资料 6

做反欺诈时我们做过每天 kw 量级的帖子准实时聚类，用的是 dbscan+simhash 算法，DBSCAN 算法的显著优点是聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。simhash 算法能够把帖子用一个 hash 来表示，减少对比复杂度，为了减少对比数据量，我们把 64 位的 simhash 每 16 位分成 4 段，只对比四段中至少一段完全一样的。我们把 dbscan 聚类得到的核心点放在一个单独的核心点表中，把每分钟发布的帖子和核心点做 simhash 对比，如果发现该帖子和某核心点密度可达，则把该帖子加入该核心点的聚类，上线后效果不错，每分钟准实时聚类无延时。

参考

1. http://matpalm.com/resemblance/jaccard_coeff/
2. http://blog.csdn.net/c289054531/article/details/8082952
3. 这篇文章一般，有很多谬误
4. 唯一一篇讲明白了 LSH 原理的文章，如何从高位到低维映射的同时保留相似性
5. https://github.com/1e0ng/simhash
6. https://www.zhihu.com/question/20399584/answer/168309597
7. https://mattilyra.github.io/2017/05/23/document-deduplication-with-lsh.html