- 在VisualStudio中部署GDAL库的C++版本(包括SQLite、PROJ等依赖)
- Android开机流程介绍
- STM32CubeMX教程31USB_DEVICE-HID外设_模拟键盘或鼠标
- 深入浅出Java多线程(五):线程间通信
布隆过滤器,听过也学过,实际中没怎么用到,时间长了再接触这个概念就陌生了,说到底还是没有彻底掌握。为了真正理解一项技术或一个概念,最好还是从问题出发,所以布隆过滤器到底解决了什么问题呢?
布隆过滤器可以用来检测一个元素是否属于某个集合.
上面的定义比较抽象,下面有些具体的例子(参考这篇文章的内容:https://zhuanlan.zhihu.com/p/94433082):
从以上例子看,布隆过滤器确实很厉害,用处很多。不过如果我还没有这些项目的开发经验,怎么能用更通俗的方式理解布隆过滤器能解决什么问题呢? 最近悬疑剧看的多,我想到了破案这个场景.
警察破案,在寻找嫌疑人的时候,一般都会根据以下几种特征去筛查:
通常犯罪分子在犯罪之后都会潜逃到其他地方,警察需要一个个地方,甚至一个个城市去筛查,这个时候怎么样快速破案就成了一个关键问题。如果拿着嫌疑人的照片一个个去比对,显然太慢了,那么快速的方式是什么呢?假设我们有个“法外狂徒”张三,具备以下的特征:
特征 | 例子 | 0或1 |
---|---|---|
性别 | 男 | 1 |
性别 | 女 | 0 |
年龄 | 35 | 1 |
身高 | 175厘米 | 1 |
体重 | 70公斤 | 1 |
体型 | 偏瘦 | 1 |
肤色 | 黄色 | 1 |
发型 | 短发 | 1 |
眼睛颜色 | 黑色 | 1 |
脸型 | 方形 | 1 |
纹身 | 无 | 1 |
疤痕 | 左眼角有一道 | 1 |
习惯 | 喜欢喝咖啡 | 1 |
特点 | 话少 | 1 |
嗜好 | 喝酒 | 1 |
警察到了一个新的地方,会快速收集以上信息(通过公安系统或走访群众),判断一个区域内有没有人同时具备以上特征,如果没有,那犯罪嫌疑人肯定不在这个区域了,就可以继续排查下一个地方。如果发现该地区有人符合上述全部特征呢?那也并不代表一定就找到了嫌疑人,但是可以大大缩小排查的范围.
警察寻找嫌疑人的过程,不就是布隆过滤器的工作原理吗?
首先,警察寻找嫌疑人和上面列举的互联网产品中需要解决的问题都是一类问题:
例子 | 元素 | 集合 |
---|---|---|
警察寻找嫌疑人 | 嫌疑人 | 一个地区内的所有人 |
网页爬虫URL去重 | 一个URL | 是否在已经爬取的URL列表内 |
反垃圾邮件 | 一个邮箱地址 | 垃圾邮箱地址库 |
避免推荐给用户已经读过的文章 | 一篇文章 | 已经推荐给用户的文章集合 |
意查询请求带来的缓存穿透 | 请求所查询的商品 | 是否是商品库中真实存在的商品 |
警察会给嫌疑人列举一系列的特征,然后去看一个地区内是否有人具备所有这些特征。而布隆过滤器的原理是用哈希函数生成一个很长的0/1串,实际上我们可以把值为1的位置看作该元素具有这个位置的特征。接下来我们要去跟待筛选的集合进行比对,这个过程我们不需要一一比对,只需要去查看集合内是否有元素具备这个特征。这里我们需要维护两个向量:
内容 | 特征向量 | 例子 |
---|---|---|
元素 | 长度为N的向量,每个位置是0或1:1代表该元素具有该特征 | 嫌疑人一系列特征,1代表具有 |
集合 | 长度为N的向量,每个位置是0或1:1代表集合中存在一个元素具备这个特征 | 一个地区内人口的综合统计信息 |
接下来要做的就是比对这两个向量即可,而不是将元素和集合中的每个元素一一对比.
布隆过滤器的优点是查询速度快,缺点是不保证百分百准确。就好比说:即使我们在一个地方找到了符合所有犯罪嫌疑人特征的人,也有可能找错.
通过寻找犯罪嫌疑人的例子来理解布隆过滤器,可能更容易记住吧.
如果你喜欢我的文章,欢迎到我的个人网站关注我,非常感谢! 。
最后此篇关于布隆过滤器和寻找嫌疑人的文章就讲到这里了,如果你想了解更多关于布隆过滤器和寻找嫌疑人的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我有一个对象数组,我想在键传入“filter”过滤器时提取值。下面是我尝试过的 Controller 代码片段,但我得到的响应类型未定义。请帮我找出哪里出错了。 var states = [{"HI
如果任何 J2EE 应用程序直接访问 servlet,然后 servlet 将相同的请求转发到某个 .jsp 页面。 request.getRequestDispatcher("Login.jsp")
我有一个带有图像缩略图的表单,可以通过复选框进行选择以进行下载。我想要一个包含 jQuery 中图像的数组,用于 Ajax 调用。 2个问题: - 表格顶部有一个复选框,用于切换我想要从映射中排除的所
我必须从服务器转储数据库,将 .sql 传输到另一台服务器,然后运行以下脚本以使用此语法删除某些行: DELETE wp_posts FROM wp_posts INNER JOIN wp_postm
我想从目录中过滤掉特定类型的文件,但收到错误“ token 语法错误,删除这些 token ”: File dir = new File("c:/etc/etc"); File[] f
几乎所有的 Web 应用程序都依赖外部的输入。这些数据通常来自用户或其他应用程序(比如 web 服务)。通过使用过滤器,您能够确保应用程序获得正确的输入类型。 您应该始终对外部数据进行过滤! 输
我正在开发一个由 OData 服务提供支持的搜索功能。它将返回一个或一列标题对象作为结果。我们需要搜索的许多字段不在标题对象中。它们仅在子对象(导航属性)中。能够针对子字段执行 OData 搜索并仍然
假设我有以下模型,它有一个方法 variants(): class Example(models.Model): text = models.CharField(max_length=255)
我有一个默认的列表列表,但我基本上想这样做: myDefaultDict = filter(lambda k: len(k)>1, myDefaultDict) 除了它似乎只适用于列表。我能做什么?
我正在使用 django-filter 来输出我的模型的过滤结果。那里没有问题。下一步是添加一个分页器……尽管现在已经苦苦挣扎了好几天。 views.py: def funds_overview(re
我正在做一个概念证明,我正在试验一种奇怪的行为。 我有一个按日期字段按范围分区的表,如果我设置固定日期或由 SYSDATE 创建的日期,查询的成本会发生很大变化。 这些是解释计划: SQL> SELE
如果一个或另一个值匹配,是否可以制作一个过滤器,例如一个中性的 PropertyFilter(并传递给链中的下一个过滤器)?就像是: value1 val
我是 VBA 初学者,正在尝试根据单元格值过滤数据,经过一番谷歌搜索后,我编写了一个有效的代码 Sub FilterDepartment_Sales() Sheet6.Activate
假设我在 excel 数据透视表中有两个过滤器。 两者最初都会显示筛选列的选定范围内的所有值。 当我仅在过滤器 1 中选择几个值时,过滤器 2 仍会继续显示基础数据中所选范围内特定过滤器列中的所有值。
是否可以定义自定义 build-ins (名称不再适合)在 ftl? 由于语义前提,我不想让它成为一个函数,而是一个内置的。 最佳答案 这是不可能的,?语法是为内置函数保留的。 (顺便说一句,这意味着
我试图在 Edit | 之外添加一个链接通过插件删除wordpress管理员>用户>所有用户列表中的链接..这是我第一次尝试通过查看其他插件或搜索google来制作wordpress插件.. 我添加了
我正在尝试按照以下教程使用 django 过滤器进行分页,但该教程似乎缺少某些内容,而且我无法使用基于函数的 View 方法显示分页。 https://simpleisbetterthancomple
由于我是 Powershell 新手,因此寻求最佳实践方面的帮助, 我有一个 csv 文件,我想过滤掉 csv 中的每一行,除了包含“未安装”的行 然后,我想根据包含计算机列表的单独 csv 文件过滤
我正在尝试创建一个搜索查询,它会告诉我我作为审阅者添加到其中的打开更改,但我还没有提交最新补丁集的代码审查。这应该包括其他人已经评论过的更改,但我没有。 我能找到的最接近的是 is:reviewer
在我的 Web 应用程序中,我有 3 个主要部分 1. 客户 2. 供应商 3. 管理员 我正在使用 java session 过滤器来检查用户 session 并允许访问网站的特定部分。 因此客户只
我是一名优秀的程序员,十分优秀!