谷歌如何实现网页去重?

简介: 谷歌如何实现网页去重?

你好,我是Giant。


我们每天都在使用谷歌、百度、必应等搜索引擎,高效率地查找资源信息。互联网让全世界的网民实现了内容共享。


谷歌内部的一篇文章报道,早在2008年,谷歌浏览器索引的网页数量已经达到了1万亿,每天依然在源源不断地增加。




如此海量的网页,为了避免重复检索收录,谷歌是如何对抓取的网页做去重呢?

这个问题也是一道大厂算法面试题,掌握了进大厂的概率都会增加不少哦。


一种朴素的做法是,用词向量或预训练语言模型将网页文档直接编码为固定长度的embedding,然后对于每一个新爬取的页面,和已有网页计算是否存在雷同的特征向量,或看作K=1的K近邻问题。


虽然KNN有Annoy、HNSW等高效的实现算法,但网页中往往存在大量冗余信息,如何有效将文档编码为特征向量,存在很大的难点。


刚好最近关注了局部敏感哈希算法,我发现其中的simhash非常适用于网页去重。

下面我以simhash为例,简单分享一下谷歌实现网页自动去重的原理。


网页去重的基本框架大致包含三个步骤:特征词提取、生成文档指纹、相似性计算。


特征词提取



我们可以将网页视作一篇文档。首先,从文档中提取一组能表征该文档的特征词,并计算权重,得到<特征词,权重>组成的pair二元组。


其中特征词和权重,可以通过TF-IDF等算法排序获得。TF-IDF的主要思想是,一个单词在一篇文章中出现的频率越高,且在其他文章中出现的频率越低,则该单词对当前文本的重要程度就越高,TF-IDF值就越大。


生成文档指纹



利用开源的hash函数,将每个特征词映射成为固定长度(例如64位)的二进制数,即哈希值,得到新的二元组<哈希值,权重>


随后,利用权重对产生的二进制序列进行改写,即把权重信息融入二进制序列中,变成一个实数向量。假设刚刚得到的<哈希值,权重>是<100110, 0.57>(这里哈希值是6位),那么经过改写变成了实数向量(0.57,-0.57, -0.57, 0.57, 0.57, -0.57)。


每个特征词都做了上述的改写后,对一篇文档中的所有特征词的实数向量进行累加(即对应位置相加),即可获得一个代表整个文档的实数向量。假设最后得到的实数向量是(13, 108, -22, -5, -32, 55)。


最后将上面得到的实数向量规范化,即将实数向量转换为二进制序列,转换规则为正数变为1,负数变为0。即(13, 108, -22, -5, -32, 55) --> 110001。最终得到的这个二进制序列就是本文档的文档指纹。


下图演示了文档指纹的生成过程。



文档相似性计算



计算得到每一篇文档的指纹后,需要对文档集合中的所有文档进行相似性计算,把雷同的文档过滤掉。那么,如何进行文档相似性计算呢?


对于文档A,B,其内容的相似性可以通过A,B对应的文档指纹的相似程度来体现。内容越相似,二进制序列对应位置相同的位数就越多。


两个长度相同的二进制序列之间的差异被称为“海明距离”,海明距离越小,表示两篇文档越相似。一般认为,当海明距离<=3时,两篇文档就被视为雷同。至此,问题就变成了如何求海明距离?


我们还是通过例子来说明。


假设文档A的文档指纹是100110,文档B的文档指纹是100011,显然,有两个位置上的数不一样,即海明距离为2。那么,文档A,B的海明距离具体该如何计算呢?


实际上,求海明距离,是先对两个二进制序列进行异或运算(假设运算结果是ret),再对二进制序列ret求其1的个数。所以,问题又转移至:如何求二进制序列中"1"的个数?

这又是一个经典巧妙的基础算法题!


在具体分析前,我们先来看看把一个数减1会发生什么神奇的事情?


如果一个整数不等于0,那么该整数的二进制表示中至少有一位是1。


情况1:假设这个数的二进制表示的最右边一位是1,那么经过减1操作后,最后一位变成了0而其他位不变,也就是最后一位相当于做了取反操作,由1变成0;

比如,一个二进制数1001,减1后,得到1000。


情况2:假设这个数的二进制表示的最后一位是0,而它的最右边的‘1’ 位于第m位,那么经过减1操作后,第m位由1变成0,而第m位之后的位取反,第m位之前的位保持不变。比如,一个二进制数1100,减1后,得到1011。


在这两种情况中,我们发现,把一个整数减去1,都是把它二进制数最右边的1变成0(假设最右边的 ‘1’ 位于第m位),而第m位右边若还有0,把0都变成1,第m位左边保持不变。接下来,我们把一个整数和它减去1的结果做与运算,例如:


a = 1100a-1 = 1011ret = a & (a-1) = 1000

可见,把一个整数a减去1,再和原整数a做与运算,会把该整数a最右边的1变成0,那么,一个整数的二进制序列中有多少个1就可以通过这种方式算出来(不借助 bin 等内部函数的前提下)!


以下是Python代码:


def count_of_1(num):
    cnt = 0
    while num:
        cnt += 1
        num &= num - 1
    return cnt


Simhash算法到这儿就全部介绍完了。

当然谷歌的页面去重算法还做了很多性能优化,感兴趣的同学可以看相关论文资料做深入了解哦。

目录
打赏
0
0
0
0
2
分享
相关文章
赞!优雅的Python多环境管理神器!易上手易操作!
赞!优雅的Python多环境管理神器!易上手易操作!
394 0
mysql合并查询(多张表) union 和 union all
简介 小序 :今天写首页动态业务的时候,用到了两张表,还需要分页查询,刚开始以为需要关联查询,后来发现关联的话不会放到一个实体,然后我就上网找方法,然后发现了一个我没学过的sql语句union,union all,卧槽 还是得好好学习啊,前端我想学,mysql我想学,真的时间不够用啊,还得给学弟学妹拍趣味编程课看的视频,真的是烦啊! 如果我们需要将两个select语句的结果作为一个整体显示出来,我们就需要用到union或者union all关键字。union(或称为联合)的作用是将多个结果合并在一起显示出来。 UNION 操作符用于合并两个或多个 SELECT 语句的结果集。
1216 0
mysql合并查询(多张表) union 和 union all
MySql 别犯糊涂了! LEFT JOIN 的 ON 后接上筛选条件,多个条件会出事!
MySql 别犯糊涂了! LEFT JOIN 的 ON 后接上筛选条件,多个条件会出事!
2851 0
MySql 别犯糊涂了! LEFT JOIN 的 ON 后接上筛选条件,多个条件会出事!
在DVWA靶机上从渗透到控制(weevely和中国蚁剑)
本文介绍如何使用Weevely工具对Ubuntu系统上的DVWA进行渗透测试,通过上传Webshell获取远程服务器控制权。实验环境为靶机IP 192.168.1.37(DVWA低安全等级)和攻击机Kali Linux IP 10.211.55.29。详细步骤包括Weevely安装、Webshell生成与上传、命令执行及提权尝试,并结合中国蚁剑进一步操作。文中强调合法授权和隐蔽性的重要性。
301 0
在DVWA靶机上从渗透到控制(weevely和中国蚁剑)
掌握Prompt写作技巧:写出完美Prompt的秘籍
这篇文章的核心宗旨就是教你如何写出优秀的Prompt。我们将从Prompt的定义、运行过程,以及优秀Prompt应具备的各个要素入手,逐步展开详细的解析和实用示例,让你在短时间内掌握写作高效Prompt的技巧和策略。
Linux报错:mkdir:无法创建目录“/opt/apps/xxx/logs“: Permission denied
Linux报错:mkdir:无法创建目录“/opt/apps/xxx/logs“: Permission denied
771 0
轻声低语,藏在光芒下的语音转文字模型Whisper
轻声低语,藏在光芒下的语音转文字模型Whisper
1552 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问