字符串匹配算法之SimHash算法 – cococo点点

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。

参考

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/

 

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。欢迎转载,请注明出处:
转载自:cococo点点 http://www.cnblogs.com/coder2012

本文链接:http://www.cnblogs.com/coder2012/p/3293288.html,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量