注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

gmd20的个人空间

// 编程和生活

 
 
 

日志

 
 

Google比较两个网页内容是否相似的算法simhash  

2010-11-02 23:36:59|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

simhash算法的输入是一个向量,输出是一个f位的签名值。为了陈述方便,假设输入的是一个文档的特征集合,每个特征有一定的权重。比如特征可以是文档中的词(根据每个词随机生成一个不同的表示64位数就可以了),其权重可以是这个词出现的次数。simhash算法如下:

1 1,将一个f维的向量V初始化为0;f位的二进制数S初始化为0;
2 2,对每一个特征:用传统的hash算法对该特征产生一个f位的签名b。对i=1到f:
3     如果b的第i位为1,则V的第i个元素加上该特征的权重;
4     否则,V的第i个元素减去该特征的权重。  
5 3,如果V的第i个元素大于0,则S的第i位为1,否则为0;

6 4,输出S作为签名。

======================================================

算法的关键就是把可以通过词的出现次数计算得到一个可以表示文档是否相似的64的数值签名。然后可以通过比较两个签名的相同位数来区分是不是相同等文档了,一般去相同位数 k=3 ???不过比较现在文档生成出来的64位数和其他的以前抓取过的所有的网页的64位数是不是只有3个位不同也不是一件很简单的事。Google文档说一种是为所有的签名64位数进行排序,一种是位64数生成所有的k=3的可能的组合表。不过Google把两种办法结合起来使用,而且因为这个签名都是很随机的,除非是类似文档,相同的位比较多,才有可能每几个位都是一样的,所以它是把这个64位划分为几个区域,一个一个区域的进去比较,应该会快很多。

这种把多维数据简化到f维数据算法叫做 Locality_sensitive_hashing   ???

这个应该是一个通用的算法,应该也可以用于其他方面的相似比较多匹配吧?? 我在想是否能应用与象棋程序的盘面相似比较呢???

具体参考 http://www.cnblogs.com/linecong/archive/2010/08/28/simhash.html 的说明

Google的论文原文 名字是 :“ Detecting near-duplicates for web crawling. ” 可以找来看一下, Google的人是参考的Charikar“Similarity estimation techniques from rounding algorithms” 这篇论文的结论来的。

http://www.cnblogs.com/linecong/archive/2010/08/28/simhash.html 一文列出的相关文档有:

附参考文献:

[1] Detecting near-duplicates for web crawling.

[2] Similarity estimation techniques from rounding algorithms.

[3] http://en.wikipedia.org/wiki/Locality_sensitive_hashing

[4] http://www.coolsnap.net/kevin/?p=23

哈哈,不知道我这篇文章和 http://www.cnblogs.com/linecong/archive/2010/08/28/simhash.html 这篇比较的结果会不会是k<3 呢

  评论这张
 
阅读(857)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017