Google采用这种算法来解决万亿级别的网页的去重任务。

由于实验室和互联网基本没啥关系，也就从来没有关注过数据挖掘相关的东西。在实际工作中，第一次接触到匹配和聚类等工作，虽然用一些简单的匹配算法可以做小数据的聚类，但数据量达到一定的时候就束手无策了。

所以，趁着周末把这方面的东西看了看，做个笔记。

来历

Google的论文detecting near-duplicates for web crawling(Simhash)。

基本思想

SimHash算法的主要思想是降维，将高维的特征向量映射成一个低维的特征向量，通过两个向量的Hamming Distance来确定文章是否重复或者高度近似。

算法步骤：　　

1. 对于给定的一段语句，进行分词，得到有效的特征向量
2. 为每一个特征向量设置一个权值
3. 对每一个特征向量计算hash值，为01组成的n-bit签名
4. 所有特征向量进行加权（1则为正，0则为负），然后累加
5. 对于n-bit签名的累加结果，如果>0置1，否则置0
6. 得到该语句的simhash值
7. 根据不同语句simhash的海明距离就来判断相似程度
   　　
   具体如图，
   

问题

Simhash用于比较大文本，比如500字以上效果都还蛮好，距离小于3的基本都是相似，误判率也比较低。

这样的话，小文本呢？如何解决？

该博客给出一个思路是，将短文本抽象出有序关键字，计算此有序字串的simhash值，寻找simhash相等的集合，缩小的搜索范围。还提到了并查集和bloom filter。

参考

http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity.html
http://www.cnblogs.com/zhengyun_ustc/archive/2012/06/12/sim.html
http://blog.jobbole.com/21928/