分布式爬虫应用中布隆过滤器的讨论随着网络技术的持续进展,互联网范围内存储的信息总量呈几何倍数的增长。互联网上所储存的海量复杂的网络信息给人们提供更多消息来源的同时也增大了人们在海量数据中检索有用信息时的负担,以分布式为核心的云计算技术就是在这一背景下迅速进展起来的。而如何有效的消除检索过程中出现的重复信息提高检索效率,一直是互联网讨论的一个重点。目前,在所有的消重检索算法中,布隆过滤器是较为优秀的一种,其实现原理是利用多个哈希函数对相应源数据进行空间映射压缩,并利用位数组简洁地存储与表示一个集合。在查询过程中,仅通过一次 Hash 映射过程即可推断一个元素是否属于这个集合,具有较少的空间占用率和较高的数据查询效率,其在多个领域都有很好地应用效果。本文讨论的目的是降低布隆过滤器在分布式网络爬虫 URL 去重过滤中的误判率,以及当猎取的网页 URL 链接数据量超过布隆过滤器设计的位数组所能容纳的元素上限时,算法本身能够对过载数据具有一定的容忍能力。因此,本文首先从布隆过滤器工作原理出发,找出布隆过滤器在分布式网络爬虫 URL 去重应用中存在的缺陷,并分析缺陷产生的原因。其次,通过借鉴布隆过滤器一些改进算法对其改进思路的启发,提出一种更适合于分布式网络爬虫URL 消重模块的改进型布隆过滤器算法-K 分多映射布隆过滤器算法。最后,通过实现一个简单的基于 Hadoop 的分布式网络爬虫工具,验证改进型布隆过滤器算法在实际的分布式网络爬虫 URL 消重应用中的效果,通过对其实际执行效果分析得出结论,为进一步改进布隆过滤器在分布式网络爬虫 URL 去重中的应用提供参考。
