simhash(局部敏感哈希)的原理simhash的背景 simhash广泛的用于搜索领域中,也许在面试时你会经常遇到这样的问题,如果对抓取的网页进行排重,如何对搜索结果进行排重等等。随着信息膨胀时代的来临,算法也在不断的精进,相似算法同样在不断的发展,接触过lucene的同学想必都会了解相似夹角的概念,那就是一种相似算法,通过计算两个向量的余弦值来判断两个向量的相似性,但这种方式需要两两进行计算向量的余弦夹角,计算量比较大,不能用于实时计算或是大数据量的运算,比如在做搜索结果的相似性排重时,需要对上千条结果进行相似性排重,如果两两比对的话,最少也需要进行上千次的向量余弦值计算,其中涉及到分词,特征提取,余弦值计算等,很难满足性能的需要。jaccard相似度也是一种相似算法,它的计算方式比较直观,就是sim(x,y)= (x∩y) / (x∪y),例如: 若 S={a, d},T={a, c, d} 则 Jaccard_Sim(S, T) = |{a, d}|/|{a, c, d}| = 2/3也是一种需要实时生成特征向量并且进行计算的算法。那么什么是simhash呢?Simhash 是一种用单个哈希函数得到文档最小哈希签名的方法,过程为:将一个 f 维的向量 V 初始化为0;f 位的二进制数 S 初始化为0;对每一个特征:用传统的 hash 算法对该特征产生一个
...
继续阅读
(14)