由于实验室和互联网基本没啥关系，也就从来没有关注过数据挖掘相关的东西。在实际工作中，第一次接触到匹配和聚类等工作，虽然用一些简单的匹配算法可以做小数据的聚类，但数据量达到一定的时候就束手无策了。
所以，趁着周末把这方面的东西看了看，做个笔记。
来历
google的论文“detecting near-duplicates for web crawling”--------simhash。
Google采用这种算法来解决万亿级别的网页的去重任务。
基本思想
simhash算法的主要思想是降维，将高维的特征向量映射成一个低维的特征向量，通过两个向量的Hamming Distance来确定文章是否重复或者高度近似。
步骤：
- 对于给定的一段语句，进行分词，得到有效的特征向量
- 为每一个特征向量设置一个权值
- 对每一个特征向量计算hash值，为01组成的n-bit签名
- 所有特征向量进行加权（1则为正，0则为负），然后累加
- 对于n-bit签名的累加结果，如果>0置1，否则置0
- 得到该语句的simhash值
- 根据不同语句simhash的海明距离就来判断相似程度
解析的不好，看一下大神画的图，你就会懂了
问题
simhash用于比较大文本，比如500字以上效果都还蛮好，距离小于3的基本都是相似，误判率也比较低。
这样的话，小文本呢？如何解决？
该博客给出一个思路是，将短文本抽象出有序关键字，计算此有序字串的simhash值，寻找simhash相等的集合，缩小的搜索范围。还提到了并查集和bloom filter。
本文转自cococo点点博客园博客，原文链接：http://www.cnblogs.com/coder2012/p/3293288.html，如需转载请自行联系原作者
