|
simhash是google用来处理赏罚海量文本去重的算法。 google出品，你懂的。 simhash最牛逼的一点就是将一个文档，最后转换成一个64位的字节，临时称之为特性字，然后判定一再只必要判定他们的特性字的间隔是不是<n（按照履历这个n一样平常取值为3），就可以判定两个文档是否相似。
道理
simhash值的天生图解如下
或许花三分钟看懂这个图就差不多怎么实现这个simhash算法了。出格简朴。谷歌出品嘛，简质朴用。
算法进程或许如下：
- 将Doc举办要害词抽取(个中包罗分词和计较权重)，抽取出n个(要害词，权重)对， 即图中的
(feature,weight)们。 记为?feature_weight_pairs?= [fw1,fw2 … fwn]，个中 fwn = (feature_n,weight_n`)。
-
hash_weight_pairs?= [ (hash(feature),weight) for feature,weight infeature_weight_pairs?] 天生图中的(hash,weight)们,此时假设hash天生的位数bits_count = 6（如图）;
- 然后对?
hash_weight_pairs?举办位的纵向累加，假如该位是1，则+weight,假如是0，则-weight，最后天生bits_count个数字，如图所示是[13,108,-22,-5,-32,55],这里发生的值和hash函数所用的算法相干。
-
到此，怎样从一个doc到一个simhash值的进程已经讲大白了。 可是尚有一个重要的部门没讲，
『simhash值的海明间隔计较』
二进制串A 和 二进制串B 的海明间隔 就是?A xor B?后二进制中1的个数。
举譬喻下：
A = 100111;
B = 101010;
hamming_distance(A,B) = count_1(A xor B) = count_1(001101) = 3;
当我们算出全部doc的simhash值之后，必要计较doc A和doc B之间是否相似的前提是：
A和B的海明间隔是否小于便是n，这个n值按照履历一样平常取值为3,
simhash本质上是局部敏感性的hash，和md5之类的纷歧样。 正由于它的局部敏感性，以是我们可以行使海明间隔来权衡simhash值的相似度。
『高效计较二进制序列中1的个数』
/* src/Simhasher.hpp */
bool isEqual(uint64_t lhs, uint64_t rhs, unsigned short n = 3)
{
unsigned short cnt = 0;
lhs ^= rhs;
while(lhs && cnt <= n)
{
lhs &= lhs - 1;
cnt++;
}
if(cnt <= n)
{
return true;
}
return false;
}
由上式这个函数来计较的话，时刻伟大度是 O(n); 这里的n默认取值为3。由此可见照旧蛮高效的。
『计较二进制序列中1的个数之O(1)算法实现』
感激?@SCatWang?的评述分享：
（编辑：湖南网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
