目录
前言:
代码:
说明:
总结:
首页 后端开发 php教程 在爬虫的过程中如何使用Redis的Bloomfilter去重

在爬虫的过程中如何使用Redis的Bloomfilter去重

Sep 15, 2018 am 11:21 AM

本篇文章给大家带来的内容是关于如何使用Redis的Bloomfilter去重,既用上了Bloomfilter的海量去重能力,又用上了Redis的可持久化能力,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

前言:

“去重”是日常工作中会经常用到的一项技能,在爬虫领域更是常用,并且规模一般都比较大。去重需要考虑两个点:去重的数据量、去重速度。为了保持较快的去重速度,一般选择在内存中进行去重。

  • 数据量不大时,可以直接放在内存里面进行去重,例如python可以使用set()进行去重。

  • 当去重数据需要持久化时可以使用redis的set数据结构。

  • 当数据量再大一点时,可以用不同的加密算法先将长字符串压缩成 16/32/40 个字符,再使用上面两种方法去重;

  • 当数据量达到亿(甚至十亿、百亿)数量级时,内存有限,必须用“位”来去重,才能够满足需求。Bloomfilter就是将去重对象映射到几个内存“位”,通过几个位的 0/1值来判断一个对象是否已经存在。

  • 然而Bloomfilter运行在一台机器的内存上,不方便持久化(机器down掉就什么都没啦),也不方便分布式爬虫的统一去重。如果可以在Redis上申请内存进行Bloomfilter,以上两个问题就都能解决了。

代码:

# encoding=utf-8import redisfrom hashlib import md5class SimpleHash(object):
    def __init__(self, cap, seed):
        self.cap = cap
        self.seed = seed    def hash(self, value):
        ret = 0
        for i in range(len(value)):
            ret += self.seed * ret + ord(value[i])        return (self.cap - 1) & retclass BloomFilter(object):
    def __init__(self, host='localhost', port=6379, db=0, blockNum=1, key='bloomfilter'):
        """
        :param host: the host of Redis
        :param port: the port of Redis
        :param db: witch db in Redis
        :param blockNum: one blockNum for about 90,000,000; if you have more strings for filtering, increase it.
        :param key: the key's name in Redis
        """
        self.server = redis.Redis(host=host, port=port, db=db)
        self.bit_size = 1 << 31  # Redis的String类型最大容量为512M,现使用256M
        self.seeds = [5, 7, 11, 13, 31, 37, 61]
        self.key = key
        self.blockNum = blockNum
        self.hashfunc = []        for seed in self.seeds:
            self.hashfunc.append(SimpleHash(self.bit_size, seed))    def isContains(self, str_input):
        if not str_input:            return False
        m5 = md5()
        m5.update(str_input)
        str_input = m5.hexdigest()
        ret = True
        name = self.key + str(int(str_input[0:2], 16) % self.blockNum)        for f in self.hashfunc:
            loc = f.hash(str_input)
            ret = ret & self.server.getbit(name, loc)        return ret    def insert(self, str_input):
        m5 = md5()
        m5.update(str_input)
        str_input = m5.hexdigest()
        name = self.key + str(int(str_input[0:2], 16) % self.blockNum)        for f in self.hashfunc:
            loc = f.hash(str_input)
            self.server.setbit(name, loc, 1)if __name__ == &#39;__main__&#39;:""" 第一次运行时会显示 not exists!,之后再运行会显示 exists! """
    bf = BloomFilter()    if bf.isContains(&#39;http://www.baidu.com&#39;):   # 判断字符串是否存在
        print &#39;exists!&#39;
    else:        print &#39;not exists!&#39;
        bf.insert(&#39;http://www.baidu.com&#39;)
登录后复制

说明:

  1. Bloomfilter算法如何使用位去重,这个百度上有很多解释。简单点说就是有几个seeds,现在申请一段内存空间,一个seed可以和字符串哈希映射到这段内存上的一个位,几个位都为1即表示该字符串已经存在。插入的时候也是,将映射出的几个位都置为1。

  2. 需要提醒一下的是Bloomfilter算法会有漏失概率,即不存在的字符串有一定概率被误判为已经存在。这个概率的大小与seeds的数量、申请的内存大小、去重对象的数量有关。下面有一张表,m表示内存大小(多少个位),n表示去重对象的数量,k表示seed的个数。例如我代码中申请了256M,即1<<31(m=2^31,约21.5亿),seed设置了7个。看k=7那一列,当漏失率为8.56e-05时,m/n值为23。所以n = 21.5/23 = 0.93(亿),表示漏失概率为8.56e-05时,256M内存可满足0.93亿条字符串的去重。同理当漏失率为0.000112时,256M内存可满足0.98亿条字符串的去重。
    20161110104702907.png

  3. 基于Redis的Bloomfilter去重,其实就是利用了Redis的String数据结构,但Redis一个String最大只能512M,所以如果去重的数据量大,需要申请多个去重块(代码中blockNum即表示去重块的数量)。

  4. 代码中使用了MD5加密压缩,将字符串压缩到了32个字符(也可用hashlib.sha1()压缩成40个字符)。它有两个作用,一是Bloomfilter对一个很长的字符串哈希映射的时候会出错,经常误判为已存在,压缩后就不再有这个问题;二是压缩后的字符为 0~f 共16中可能,我截取了前两个字符,再根据blockNum将字符串指定到不同的去重块进行去重。

总结:

基于Redis的Bloomfilter去重,既用上了Bloomfilter的海量去重能力,又用上了Redis的可持久化能力,基于Redis也方便分布式机器的去重。在使用的过程中,要预算好待去重的数据量,则根据上面的表,适当地调整seed的数量和blockNum数量(seed越少肯定去重速度越快,但漏失率越大)。

以上是在爬虫的过程中如何使用Redis的Bloomfilter去重的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
1 个月前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

CakePHP 项目配置 CakePHP 项目配置 Sep 10, 2024 pm 05:25 PM

在本章中,我们将了解CakePHP中的环境变量、常规配置、数据库配置和电子邮件配置。

适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 Dec 24, 2024 pm 04:42 PM

PHP 8.4 带来了多项新功能、安全性改进和性能改进,同时弃用和删除了大量功能。 本指南介绍了如何在 Ubuntu、Debian 或其衍生版本上安装 PHP 8.4 或升级到 PHP 8.4

CakePHP 日期和时间 CakePHP 日期和时间 Sep 10, 2024 pm 05:27 PM

为了在 cakephp4 中处理日期和时间,我们将使用可用的 FrozenTime 类。

CakePHP 文件上传 CakePHP 文件上传 Sep 10, 2024 pm 05:27 PM

为了进行文件上传,我们将使用表单助手。这是文件上传的示例。

CakePHP 路由 CakePHP 路由 Sep 10, 2024 pm 05:25 PM

在本章中,我们将学习以下与路由相关的主题?

讨论 CakePHP 讨论 CakePHP Sep 10, 2024 pm 05:28 PM

CakePHP 是 PHP 的开源框架。它的目的是使应用程序的开发、部署和维护变得更加容易。 CakePHP 基于类似 MVC 的架构,功能强大且易于掌握。模型、视图和控制器 gu

如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 Dec 20, 2024 am 11:31 AM

Visual Studio Code,也称为 VS Code,是一个免费的源代码编辑器 - 或集成开发环境 (IDE) - 可用于所有主要操作系统。 VS Code 拥有针对多种编程语言的大量扩展,可以轻松编写

CakePHP 创建验证器 CakePHP 创建验证器 Sep 10, 2024 pm 05:26 PM

可以通过在控制器中添加以下两行来创建验证器。

See all articles