Simhash的巧妙
- - 丕子Simhash是locality sensitive hash(局部敏感哈希)的一种,最早由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出. Google就是基于此算法实现网页文件查重的《Detecting near-duplicates for web crawling》.
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距离的概念 |
亡灵序曲配姚明 |
麦蒂:我没和阿帅吵架,我这周复出 |
无觅 |