Simhash的巧妙

标签: 技术 LSH Simhash 海明距离 | 发表时间:2014-06-14 14:54 | 作者:丕子
出处:http://www.zhizhihu.com

Simhash是locality sensitive hash(局部敏感哈希)的一种,最早由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出。Google就是基于此算法实现网页文件查重的《Detecting near-duplicates for web crawling》。

算法思路比较简单,这里不再赘述,其中比较容易被人忽视的但是又比较重要的两点是:

1、 与余弦相似度的关系:simhash源于随机超平面算法,可以推导出与余弦相似度的关系。

2、 索引:google在把simhash用来做分布去重的时候,海明距离小于4的即为相似的网页。simhash为64位,那么根据鸽巢原理,把hash平均分为4份的话,至少有一份是完全相同的。那么对于一个网页,你就可以建4个KV结构的map或索引,平均分成4份,每一份作为一个key。

假设是存在数据库的话,新来一个网页,计算了simhash, 前16位为key将数据库中的已有网页取出来,进行两两计算海明距离即可,就不需要进行全库比较了,大大大提高了计算效率。

可以很轻松的实现到mapreduce框架中。

其中,第2点对于系统是极为重要的。

您可能也喜欢:

漫话距离(By Dahua Lin@MIT)

马氏距离(Mahalanobis distance)和欧氏距离(Euclidean distance )

距离度量-L1距离和L2距离的概念

亡灵序曲配姚明

麦蒂:我没和阿帅吵架,我这周复出
无觅

相关 [simhash] 推荐:

Simhash的巧妙

- - 丕子
Simhash是locality sensitive hash(局部敏感哈希)的一种,最早由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出. Google就是基于此算法实现网页文件查重的《Detecting near-duplicates for web crawling》.

Simhash算法原理和网页查重应用

- - 互联网旁观者
传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法. 产生的两个签名,如果相等,说明原始内容在一定概率下是相等的;如果不相等,除了说明原始内容不相等外,不再提供任何信息,因为即使原始内容只相差一个字节,所产生的签名也很可能差别极大. 从这个意义上来说,要设计一个hash算法,对相似的内容产生的签名也相近,是更为艰难的任务,因为它的签名值除了提供原始内容是否相等的信息外,还能额外提供不相等的原始内容的差异程度的信息.

海量数据相似度计算之simhash短文本查找

- - ITeye博客
在前一篇文章 《 海量数据相似度计算之simhash和海明距离》 介绍了simhash的原理,大家应该感觉到了算法的魅力. 但是随着业务的增长 simhash的数据也会暴增,如果一天100w,10天就1000w了. 我们如果插入一条数据就要去比较1000w次的simhash,计算量还是蛮大,普通PC 比较1000w次海明距离需要 300ms ,和5000w数据比较需要1.8 s.

海量数据相似度计算之simhash和海明距离

- - CSDN博客架构设计推荐文章
通过  采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析. 分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法. 常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等. 这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重.

文本相似度计算-google的simHash汉明距离

- - 行业应用 - ITeye博客
       针对文本相似性计算,很多开发朋友首先想到的应该是使用向量空间模型VSM(Vector Space Model). 使用VSM计算相似度,先对文本进行分词,然后建立文本向量,把相似度的计算转换成某种特征向量距离的计算,比如余弦角、欧式距离、Jaccard相似系数等. 这种方法存在很大一个问题:需要对文本两两进行相似度比较,无法扩展到海量文本的处理.

[转][转] 文本相似性算法Simhash原理及实践

- - heiyeluren的blog(黑夜路人的开源世界)
simhash(局部敏感哈希)的原理. simhash广泛的用于搜索领域中,也许在面试时你会经常遇到这样的问题,如果对抓取的网页进行排重,如何对搜索结果进行排重等等. jaccard相似度也是一种相似 算法,它的计算方式比较直观,就是sim(x,y)= (x∩y) / (x∪y),例如:.      若  S={a, d}, T={a, c, d} .