simhash实现论文查重

参考论文来源 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理，为了便于理解尽量不使用数学公式，分为这几步(标准做法)：

完整的算指纹的算法：

按照这种市面上的通用做法，传入的map 可以是无序的

有一个小问题提请注意 直接用 1<

两种方式的比较：

这里先引入一个概念： 抽屉原理

假设我们要寻找海明距离3以内的数值，根据抽屉原理，只要我们将整个64位的二进制串划分为4块，无论如何，匹配的两个simhash code之间 至少 有一块区域是完全相同的，如下图所示：

由于我们无法事先得知完全相同的是哪一块区域，因此我们必须采用存储多份table的方式。在本例的情况下，我们需要存储4份table，并将64位的simhash code等分成4份；对于每一个输入的code，我们通过精确匹配的方式，查找前16位相同的记录作为候选记录，如下图所示：

让我们来总结一下上述算法的实质： 假定我们最大判重海明距离为MAX_HD 1、将64位的二进制串等分成MAX_HD+1块 2、PUT操作：调整上述64位二进制，将任意一块作为前16位，总共有MAX_HD+1种组合，生成MAX_HD+1份table 3、GET操作：采用精确匹配的方式在MAX_HD+1份table中查找前16位，若找不到，说明不重复，做PUT操作；若找到了，则对剩余链做海明距离计算。 4、如果样本库中存有2^34 （差不多10亿）的哈希指纹，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本

为何要分桶？ 两个字符串通过SimHash码和海明距离比较好判断是否相似，假设计算海明距离的时间为基本操作时间。如果有海量的数据，一一比较计算的次数为 1 + 2 + 3 + ......+ n ，时间复杂度为 O(n^2) 级别。这样的时间复杂度肯定是不能接受的。

构建索引

将SimHashCode添加到索引

查询与索引库中比较的最近的海明距离

其中 bit[n] = 2^n ,索引降低比较时算法时间复杂度的方法是 将SimHashCode 比特位分成8段

其实这里也是用上了抽屉原理的，各位看官自己思考下吧。

分词 -->另写一篇博客说明

需要说明的一点： 分词的时候需要去掉停用词等噪音词，分词是该算法特征抽取的关键一步。