Google用来处理海量文本去重的simhash算法原理及实现

simhash是Google用来处理海量文本去重的算法。 Google出品,你懂的。 simhash最牛逼的一点就是将一个文档,最后转换成一个64位的字节,暂且称之为特征字,然后判断重复只需要判断他们的特征字的距离是不是<n(根据经验这个n一般取值为3),就可以判断两个文档是否相似。

原理

simhash值的生成图解如下

大概花三分钟看懂这个图就差不多怎么实现这个simhash算法了。特别简单。谷歌出品嘛,简单实用。

算法过程大概如下:

1、将Doc进行关键词抽取(其中包括分词和计算权重),抽取出n个(关键词,权重)对, 即图中的(feature, weight)们。 记为 feature_weight_pairs = [fw1, fw2 … fwn],其中 fwn = (feature_n,weight_n`)。

2、hash_weight_pairs = [ (hash(feature), weight) for feature, weight infeature_weight_pairs ] 生成图中的(hash,weight)们, 此时假设hash生成的位数bits_count = 6(如图);

3、然后对 hash_weight_pairs 进行位的纵向累加,如果该位是1,则+weight,如果是0,则-weight,最后生成bits_count个数字,如图所示是[13, 108, -22, -5, -32, 55], 这里产生的值和hash函数所用的算法相关。

4、[13,108,-22,-5,-32,55] -> 110001这个就很简单啦,正1负0。

到此,如何从一个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 的评论分享:

感谢您做的simhash库,感觉会很方便。 有关求二进制中1的个数,其实有各种O(1)的实现。可以参考这个地方:http://stackoverflow.com/a/14682688

simhash 实现的工程项目

  • C++ 版本 simhash
  • Golang 版本 gosimhash

主要是针对中文文档,也就是此项目进行simhash之前同时还进行了分词和关键词的抽取。

对比其他算法

『百度的去重算法』

百度的去重算法最简单,就是直接找出此文章的最长的n句话,做一遍hash签名。n一般取3。 工程实现巨简单,据说准确率和召回率都能到达80%以上。

『shingle算法』

shingle原理略复杂,不细说。 shingle算法我认为过于学院派,对于工程实现不够友好,速度太慢,基本上无法处理海量数据。

原文发布于微信公众号 - 交互设计前端开发与后端程序设计(interaction_Designer)

原文发表时间:2016-11-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数说工作室

机器学习/深度学习代码速查:6大工具库 &27种神经网络图览

Kailash Ahirwar,Mate Lab 联合创始人,Github的一位资深作者,也是一位活雷锋,近日在其Github个人主页上发表了一个机器学习/深度...

5135
来自专栏ATYUN订阅号

数据清理的简要介绍

清理数据应该是数据科学(DS)或者机器学习(ML)工作流程的第一步。如果数据没有清理干净,你将很难在探索中的看到实际重要的部分。一旦你去训练你的ML模型,他们也...

1463
来自专栏逍遥剑客的游戏开发

快速LightMap烘焙

1093
来自专栏小樱的经验随笔

【机器学习笔记之一】深入浅出学习K-Means算法

摘要:在数据挖掘中,K-Means算法是一种 cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。 ...

3039
来自专栏js编程在工科课程中的简单应用

4.1 数值积分、高等函数绘制

is defined informally as the signed area of the region in the xy-plane that is ...

930
来自专栏PPV课数据科学社区

【大数据问答】SPSS是如何做到发现数据质量问题,例如,如何发现缺失值?

SPSS是如何做到发现数据质量问题,例如,如何发现缺失值? (1)系统缺失值、空白值 每一个变量均有可能出现系统缺失或者空白,当数据量巨大时我们根本无法用眼睛...

4224
来自专栏数据派THU

手把手教你深度学习强大算法进行序列学习(附Python代码)

本文共3200字,建议阅读10分钟。 本文将教你使用做紧致预测树的算法来进行序列学习。

1924
来自专栏机器之心

EMNLP 2018 | 结合通用和专用NMT的优势,CMU为NMT引入「语境参数生成器」

神经机器翻译(NMT)无需单独训练或调整系统的任何部分就可以直接建模源语言到目标语言的映射。这使得 NMT 快速发展,并在许多大规模环境中成功应用 (Wu et...

1381
来自专栏AI研习社

从原理到实战 英伟达教你用PyTorch搭建RNN(上)

从 Siri 到谷歌翻译,深度神经网络大步推动了机器对自然语言的理解。 迄今为止,大多数模型把语言看作是字词的平面序列(flat sequence),使用时间递...

45411
来自专栏微信模式识别中心技术分享

“变形金刚”为何强大:从模型到代码全面解析Google Tensor2Tensor系统

      Tensor2Tensor(T2T)是Google Brain Team在Github上开源出来的一套基于TensorFlow的深度学习系统。该系统...

2.9K9

扫码关注云+社区

领取腾讯云代金券