SimHash算法

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

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

来历

　　google的论文“detecting near-duplicates for web crawling”--------simhash。

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

基本思想

　　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。

本文转自cococo点点博客园博客，原文链接：http://www.cnblogs.com/coder2012/p/3293288.html，如需转载请自行联系原作者