相似文档查找算法之 simHash 简介及其 java 实现 - leejun_2005的个人页面 - 开源中国社区

相似文档查找算法之 simHash 简介及其 java 实现 - leejun_2005的个人页面 - 开源中国社区
simhash算法的输入是一个向量，输出是一个 f 位的签名值。为了陈述方便，假设输入的是一个文档的特征集合，每个特征有一定的权重。比如特征可以是文档中的词，其权重可以是这个词出现的次数。 simhash 算法如下：
1，将一个 f 维的向量 V 初始化为 0 ； f 位的二进制数 S 初始化为 0 ；
2，对每一个特征：用传统的 hash 算法对该特征产生一个 f 位的签名 b 。对 i=1 到 f ：
如果b 的第 i 位为 1 ，则 V 的第 i 个元素加上该特征的权重；
否则，V 的第 i 个元素减去该特征的权重。 
3，如果 V 的第 i 个元素大于 0 ，则 S 的第 i 位为 1 ，否则为 0 ；
4，输出 S 作为签名。

从上面的计算过程可以看出，simhash算法其实与随机超平面hash算法是相同的，simhash算法得到的两个签名的汉明距离，可以用来衡量原始向量的夹角。这其实是一种降维技术，将高维的向量用较低维度的签名来表征。
比较相似度
海明距离： 两个码字的对应比特取值不同的比特数称为这两个码字的海明距离。一个有效编码集中, 任意两个码字的海明距离的最小值称为该编码集的海明距离。举例如下： 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同，则海明距离为 3. 

异或： 只有在两个比较的位不同时其结果是1 ，否则结果为 0 

对每篇文档根据SimHash 算出签名后，再计算两个签名的海明距离（两个二进制异或后 1 的个数）即可。根据经验值，对 64 位的 SimHash ，海明距离在 3 以内的可以认为相似度比较高。 
假设对64 位的 SimHash ，我们要找海明距离在 3 以内的所有签名。我们可以把 64 位的二进制签名均分成 4块，每块 16 位。根据鸽巢原理（也成抽屉原理，见组合数学），如果两个签名的海明距离在 3 以内，它们必有一块完全相同。 
我们把上面分成的4 块中的每一个块分别作为前 16 位来进行查找。 建立倒排索引。

http://my.oschina.net/leejun2005/blog/150086
http://blog.sina.com.cn/s/blog_4f27dbd501013ysm.html
https://github.com/sing1ee/simhash-java
Read full article from 相似文档查找算法之 simHash 简介及其 java 实现 - leejun_2005的个人页面 - 开源中国社区