首页 > 其他分享 >使用布隆过滤器求两个大文件交集

使用布隆过滤器求两个大文件交集

时间:2023-08-14 18:38:48浏览次数:40  
标签:文件 遍历 交集 元素 布隆 url 过滤器

随着互联网的发展,大数据应用越来越多。如何在内存有限的条件下,对超大规模数据进行效率处理,是一个值得探讨的问题。本文将以求两个文件共同元素为例,探讨一种基于布隆过滤器的高效算法。

问题描述

假设有文件A和文件B,各包含50亿个url,每个url 64字节,内存限制为4G。要求找出A和B中的共同url。

常规方法及不足

最简单的方法是将A和B分别载入内存,然后逐一比对找出交集。但每个文件达到320GB,远超过4G内存限制,无法操作。

一种改进是分批载入A和B的一部分数据,每次在内存中求交集,最后合并结果。这种方法可以控制每次内存使用,但需要对两个文件多轮遍历。当数据规模极大时,读写IO成本非常高。

再一种方法是使用外部排序算法。先分别对A和B进行排序,然后归并式地求交集。此方法需要多轮磁盘IO,在数据规模巨大时同样低效。

布隆过滤器解法

基于上述分析,需要一种能够快速判断元素是否在集合中的数据结构。布隆过滤器(Bloom Filter)可以提供这种能力。

布隆过滤器是一个空间效率很高的随机数据结构,对一个元素集合建立索引。它的特点是:

  • 可以快速判断一个元素是否在过滤器表示的集合中import bloomFilter.*; // 引入布隆过滤器包 public class UrlIntersector{ public static void intersect(File A, File B){ BloomFilter filterA = new BloomFilter(A.size(), 0.01); // 初始化布隆过滤器 for(String url : A){ // 遍历文件A,加载到过滤器 filterA.add(url); } BloomFilter filterB = new BloomFilter(B.size(), 0.01); // 初始化过滤器B for(String url : B){ // 遍历文件B,加载到过滤器 filterB.add(url); } for(String url : B){ // 遍历文件B if(filterA.contains(url)){ // 判断每个url是否在过滤器A中 print(url); // 如果存在,则输出 } } } }这个示例先初始化了两个布隆过滤器,然后分别加载两个文件的url,最后判断文件B中的url是否在过滤器A中,从而找出交集。总结本文以求两个大文件交集为例,展示了如何利用布隆过滤器这个高效的数据结构解决大数据场景下的复杂问题。主要优点是:
  1. 只需要两轮遍历,降低了IO和计算复杂度;
  2. 内存占用可控,可以处理超大规模数据;
  3. 效率高,可实现间隔判断,不需要存储和比较全部元素。 当然布隆过滤器也存在误判率问题,需要对参数k和m进行调优,控制在可接受的范围内。 随着大数据的发展,这类空间效率高的随机算法及数据结构还有很多,比如HyperLogLog用于统计基数,Reservoir Sampling用于抽样等。这些技术可以单独使用,也可以组合应用,解决更为复杂的大数据处理问题。
  • 判断不存在的元素时,可能会产生少量的误判 布隆过滤器的原理是,使用多个随机映射函数将元素映射到一个位向量中,判断元素是否在集合中时,检查它在位向量中的位置是否都为1。 具体实现上,使用m比特长度的位向量v初始化为0。还需要k个随机映射函数h1~hk,作用是将元素映射到0~m-1的整数索引上。添加元素时,将元素分别通过k个函数映射到位向量的k个位置,并将这些位置设为1。判断元素是否存在时,检查它通过k个函数映射的位置是否都是1,如果都是则判断元素存在,否则判断不存在。 优点是空间和查找效率都很高,不需要存储元素本身。缺点是有一定的误判率,但可以通过参数调整将误判控制在可接受范围。算法实现基于布隆过滤器,可以设计一个求两个文件交集的算法:
  • 根据文件A的数据规模和可接受的误判率,初始化布隆过滤器A;
  • 遍历文件A,将每个url输入到过滤器A中;
  • 同样初始化过滤器B,遍历文件B将元素输入过滤器B;
  • 遍历文件B,对每个url,判断它是否在过滤器A中,如果是,则输出这个url。 这个算法只需要两轮遍历,时间复杂度为O(n),并可以控制每次处理的数据量,保证内存不超限。相比之前的算法,效率有很大提升。 下面是Java示例代码:

标签:文件,遍历,交集,元素,布隆,url,过滤器
From: https://blog.51cto.com/u_16188843/7079711

相关文章

  • 资源过滤器—MVC中使用资源过滤器实现不执行Action方法体读取缓存信息返回
    前言上两篇文章分享了过滤器实现JWT进行鉴权,分别是通过授权过滤器和操作过滤器实现,这两个过滤器也是最常用的。文章链接:授权过滤器—MVC中使用授权过滤器实现JWT权限认证,操作过滤器—MVC中使用操作过滤器实现JWT权限认证,接下来将简单的谈谈资源过滤器在MVC中如何使用,一般项目中这......
  • 操作过滤器—MVC中使用操作过滤器实现JWT权限认证
    前言上一篇文章分享了授权过滤器实现JWT进行鉴权,文章链接:授权过滤器—MVC中使用授权过滤器实现JWT权限认证,接下来将用操作过滤器实现昨天的JWT鉴权。一、什么是操作过滤器?​与授权过滤器大部分一样,只是执行的时机和继承的接口有所不同。操作过滤器是在Action执行的前和后进......
  • .net6 过滤器、管道模型
    管道处理模型1、[中间件](https://learn.microsoft.com/zh-cn/aspnet/core/fundamentals/middleware/?view=aspnetcore-7.0)可以在典型应用中了解现有中间件的顺序,以及在哪里添加自定义中间件。你可以完全控制如何重新排列现有中间件,或根据场景需要注入新的自定义中间件。......
  • Servlet过滤器
    过滤器的基本概念Servlet过滤器从字面上的字意理解为经过一层次的过滤处理才达到使用的要求,而其实Servlet过滤器就是服务器与客户端请求与响应的中间层组件,在实际项目开发中Servlet过滤器主要用于对浏览器的请求进行过滤处理,将过滤后的请求再转给下一个资源。Filter是在......
  • ?【8月摸鱼计划】物联网与AIGC的交集,并详细说明
    物联网与互联网、传感网、泛在网的区别为:层面不同、灵活性不同、沟通不同。一、层面不同1、物联网:物联网是从物的层面上对事物进行帆尘表述。2、互联网:互联网是从人的层面上对事物进行表述。3、传感网:传感网是从技术和设备的角度对岁轿则事物进行表述。4、泛在网:泛在网是从人......
  • django自定义过滤器
    https://docs.djangoproject.com/zh-hans/3.1/howto/custom-template-tags/代码布局自定义的tags和filters会保存在模块名为 templatetags 的目录内。模块文件的名字即稍候你用来加载tags的名字,所以小心不要采用一个可能与其它应用自定义的tags和filters冲突的名......
  • 授权过滤器—MVC中使用授权过滤器实现JWT权限认证
    一、什么是过滤器?过滤器定义:​过滤器与中间件很相似,过滤器(Filters)可在管道(pipeline)特定阶段(particularstage)前或后执行操作,可以将过滤器视为拦截器(interceptors)。在.NETMVC开发中,权限验证是非常重要的一部分。通过使用授权过滤器可以很方便地实现权限验证功能。这篇主要分......
  • 布隆过滤器
    布隆过滤器1.作用判断某一个值是否存在2.组成很长的二进制数组和一系列hash函数3.使用使用hash函数对该值进行hash运算,并将布隆过滤器中相应的位置设置为14.判断某一个数据在布隆过滤器中是否存在对该值使用布隆过滤器的一系列hash函数进行hash运算,然后判断对应的位置......
  • 老杜 JavaWeb 讲解(十九) ——Filter过滤器
    (十七)Filter过滤器Filter过滤器当前的OA项目存在什么缺陷?DeptServlet、EmpServlet、OrderServlet。每一个Servlet都是处理自己相关的业务。在这些Servlet执行之前都是需要判断用户是否登录了。如果用户登录了,可以继续操作,如果没有登录,需要用户登录。这段判断用户是否登录......
  • SpringBoot学习笔记--过滤器Filter
    一、普通过滤器Filter是Servlet规范中的过滤器,可以处理请求,对请求的参数、属性进行调整。常常在过滤器中处理字符编码。1、创建自定义过滤器类packagecom.cqjtu.vo;importjavax.servlet.*;importjava.io.IOException;//自定义过滤器类publicclassMyFilterimplements......