44位图:如何实现网页爬虫中的URL去重功能

首先,该文章来自于极客时间网站,王争的专栏——《数据结构与算法之美》,我这里只是做简单的解释、记录并添加自己的见解,只是作为个人笔记,若侵权,马上删除。最后建议直接去该网站上购买该课程看原作者的讲解,一来是支持作者,二来是作者写的确实不错。

搜索引擎中爬虫的工作原理是——解析已经爬取页面中的网页链接,然后再爬取这些链接对应的网页。那同一个网页链接可能包含在多个页面中,导致爬虫的过程中,重复抓取相同的页面。那如何避免这些重复的爬取呢?最简单的方法是记录爬取的网页链接(URL),每次爬取一个网页之前,在记录中进行查询。

不过,应该如何记录已经爬取的网页链接呢?需要用什么样的数据结构呢?

算法解析

这个问题要处理的对象是网页链接,也就是URL。数据结构需要满足如下几个条件:

  • 支持添加一个URL和查询一个URL,并且执行效率要尽可能高
  • 因为URL很多,所以在存储效率上,要尽可能高效

前面学过的散列表、红黑树、跳表动态数据结构,都能支持快速地插入、查找数据。接着以散列表为例分析内存消耗。

假设要爬取10亿个网页,每个URL平均长度为64个字节,全部存储需要 60GB 的内存空间。而一方面,散列表必须维持较小的装载因子,才能保证不会出现过多的散列冲突,导致操作的性能下降。另一方面,用链表法解决冲突的散列表,还会存储链表指针。所以如果将这 10 亿个 URL 构建成散列表,那需要的内存空间会远大于 60GB,有可能会超过 100GB。这时可以采取分治的思想,用多台机器来存储这 10 亿网页链接。

不过,我们还应该考虑在添加、查询数据的效率以及内存消耗方面,是否还有进一步的优化空间呢?

散列表中添加、查找数据的时间复杂度已经是$O(1)$了。但是时间复杂度并不能完全代表代码的执行时间。大 O 时间复杂度表示法,会忽略掉常数、系数和低阶,并且统计的对象是语句的频度。不同的语句,执行时间也是不同的。时间复杂度只是表示执行时间随数据规模的变化趋势,并不能度量在特定的数据规模下,代码执行时间的多少。

若时间复杂度原来的系数是10,通过优化可以将系数降为1,那在时间复杂度没变化情况下,执行效率提高了10倍。对于这个问题,若用基于链表的方法解决冲突问题,散列表中存储的是URL,每次查询使用哈希函数定位到某个链表时,要依次比对每个链表中的 URL。这比较耗时:

  • 链表中的结点在内存中是不连续存储的,所以不能一下子加载到CPU 缓存中,没法很好的利用到CPU的高速缓存,所以数据访问性能方面会打折扣
  • 链表中的每个数据都是 URL,而 URL 不是简单的数字,是平均长度为 64 字节的字符串。这需要用到字符串匹配操作,比单纯的数字比对,要慢得多

对于内存消耗方面,除了刚刚这种基于散列表的解决方案,貌似没有更好的法子了。但是换一种存储结构——布隆过滤器(Bloom Filter),就可以在内存方面更加节省。这种数据结构本身是基于另一种数据结构——位图(BitMap)而言的,是对位图的一种改进。

首先思考一个跟开篇问题相似,但是稍微简单的问题——有 1 千万个整数,整数的范围在 1 到 1 亿之间。如何快速查找某个整数是否在这 1 千万个整数中呢?

这个问题仍然可以用散列表解决,不过可以用一个特殊的散列表——位图。申请一个大小为1亿,数据类型为bool类型的数组。将已知的一千万整数作为数组下标,相应的数组值设置为true。当查询某个整数 K 是否在这1千万个整数时,只需要将对应的数组值 array[K]取出来,看是否等于 true 即可。

不过,很多语言提供的bool类型大小为一个字节,并不是一个二进制位(bit),并不能节省太多空间。那如何通过编程语言,来表示一个二进制位呢?可以借助编程语言中提供的数据类型,比如 int、long、char 等类型,通过位运算,用其中的某个位表示某个数字。对应代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 将数字 A 的第 k 位设置为1:A = A | (1 << (k - 1))
// 将数字 A 的第 k 位设置为0:A = A & ~(1 << (k - 1))
// 检测数字 A 的第 k 位:A & (1 << (k - 1)) != 0
// 可以参考 https://mp.weixin.qq.com/s/xxauNrJY9HlVNvLrL5j2hg
public class BitMap { // Java中char类型占16bit,也即是2个字节
private char[] bytes;
private int nbits;

public BitMap(int nbits) {
this.nbits = nbits;
this.bytes = new char[nbits/16+1];
}

public void set(int k) {
if (k > nbits) return;
int byteIndex = k / 16;
int bitIndex = k % 16;
bytes[byteIndex] |= (1 << bitIndex);
}

public boolean get(int k) {
if (k > nbits) return false;
int byteIndex = k / 16;
int bitIndex = k % 16;
return (bytes[byteIndex] & (1 << bitIndex)) != 0;
}
}

位图通过数组下标来定位数据,所以访问效率非常高。另外,每个数字用一个二进制位表示,数组范围不大时,所需内存空间非常节省。

比如刚才例子,用散列表存储这1千万数据,数据为32位整数(占用4个字节的存储空间),那总共至少需要 40MB存储空间。而若用位图,数字范围在1到1亿之间,只需要1亿个二进制位,占用12MB左右存储空间。

但是,若数字范围很大为从1到10亿,那位图大小就是10亿个二进制位,也就是120MB大小,消耗的内存更大了。这时需要布隆过滤器了。

假设数据个数是1千万,数据范围是从1到10亿,布隆过滤器仍然使用一个1亿个二进制大小的位图,然后通过哈希函数,将数据映射到1到1亿范围内。比如哈希函数设计为 f(x) = x%n。其中,x表示数字,n 表示位图的大小(1 亿)。但是这样肯定是存在哈希冲突问题的。如一亿零一和1两个数字经过哈希函数后,结果都是1。也就无法判断位图存储的是 1 还是一亿零一了。

对于这个问题,可以设计一个复杂点、随机点的哈希算法。布隆过滤器换了另外一种解决思路:一个哈希函数可能会存在冲突,那用多个哈希函数一块儿定位一个数据,是否能降低冲突的概率呢?

具体而言,使用K个哈希函数,对同一个数字求哈希值,得到K个不同的哈希值。分别记作 $X_1,X_2,X_3,…,X_K$。把这 K 个数字作为位图中的下标,将对应的 $BitMap[X_1],BitMap[X_2],BitMap[X_3],…,BitMap[X_K]$都设置成 true。也就是用 K 个二进制位表示一个数字的存在。

当要查询某个数字是否存在时,用相同的K个哈希函数,对这个数字求哈希值,分别得到 $Y_1,Y_2,Y_3,…,Y_K$。看这 K 个哈希值,对应位图中的数值是否都为 true,如果都是 true,则说明,这个数字存在,如果有其中任意一个不为 true,那就说明这个数字不存在。

img

对于两个不同的数字,经过一个哈希函数处理之后,可能会产生相同的哈希值。但是经过 K 个哈希函数之后,K个哈希值都相同的概率非常低。但这又带来了一个问题——容易误判

img

布隆过滤器误判有一个特点——只对存在的情况有误判。如果某个数字经过布隆过滤器判断不存在,那说明这个数字真的不存在,不会发生误判;如果某个数字经过布隆过滤器判断存在,这个时候才会有可能误判,有可能并不存在。不过,只要调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例,那就可以将这种误判的概率降到非常低。

尽管布隆过滤器存在误判,但很多场景对误判有一定的容忍度,所以并不影响它发挥大作用。比如今天爬虫判重问题,即便一个没有被爬取过的网页,被误判为已经被爬取,这是可以容忍的。

接下来说下网页去重的思路:用布隆过滤器来记录已经爬取过的网页链接,假设需要判重的网页有 10 亿,可以用一个 10 倍大小的位图来存储,也就是 100 亿个二进制位,大约 1.2GB。之前用散列表判重,需要至少 100GB 的空间。相比来讲,布隆过滤器在存储空间的消耗上,降低了非常多。

相比于散列表,使用布隆过滤器在执行效率上:布隆过滤器用多个哈希函数对同一个网页链接进行处理,CPU 只需要将网页链接从内存中读取一次,进行多次哈希计算,理论上讲这组操作是 CPU 密集型的。而在散列表的处理方式中,需要读取散列冲突拉链的多个网页链接,分别跟待判重的网页链接,进行字符串匹配。这个操作涉及很多内存数据的读取,所以是内存密集型的。我们知道 CPU 计算可能是要比内存访问更快速的,所以,理论上讲,布隆过滤器的判重方式,更加快速。

总结引申

本节讲的布隆过滤器非常适合这种不需要 100% 准确的、允许存在小概率误判的大规模判重场景。除了网页去重,它还可以用来统计一个大型网站的每天UV数(每天有多少用户访问了网站),对重复访问的用户去重。

布隆过滤器的误判率,主要跟哈希函数的个数、位图的大小有关。当往布隆过滤器中不停地加入数据之后,位图中不是 true 的位置就越来越少了,误判率就越来越高了。所以,对于无法事先知道要判重的数据个数的情况,需要支持自动扩容的功能。

当布隆过滤器中,数据个数与位图大小的比例超过某个阈值的时候,就重新申请一个新的位图。后面来的新数据,会被放置到新的位图中。但是,如果要判断某个数据是否在布隆过滤器中已经存在,就需要查看多个位图,相应的执行效率就降低了一些。

课后思考

  1. 假设我们有 1 亿个整数,数据范围是从 1 到 10 亿,如何快速并且省内存地给这 1 亿个数据从小到大排序?

    答:传统做法:1亿个整数,存储需要400M空间,排序时间复杂度最优 N×log(N)。使用位图:数字范围是1到10亿,用位图存储125M就够了,然后将1亿个数字依次添加到位图中,然后再将位图按下标从小到大输出值为1的下标,排序就完成了,时间复杂度为 N。

------ 本文结束------
坚持原创技术分享,您的支持将鼓励我继续创作!

欢迎关注我的其它发布渠道