python中的布隆過濾器用法及原理詳解
更新時間：2023年07月26日 09:07:44 作者：IT之一小佬
這篇文章主要介紹了python中的布隆過濾器用法及原理詳解,布隆過濾器是一種概率空間高效的數據結構,它與hashmap非常相似，用于檢索一個元素是否在一個集合中。它在檢索元素是否存在時，能很好地取舍空間使用率與誤報比例,需要的朋友可以參考下
1、布隆過濾器的介紹
布隆過濾器（Bloom Filter），是1970年，由一個叫布隆的小伙子提出的。 它實際上是一個很長的二進制向量和一系列隨機映射函數，二進制大家應該都清楚，存儲的數據不是0就是1，默認是0。
主要用于判斷一個元素是否在一個集合中，0代表不存在某個數據，1代表存在某個數據。
布隆過濾器是一種概率空間高效的數據結構，特點是高效地插入和查詢，用來告訴你 “某樣東西一定不存在或者可能存在”。
相比于傳統的 List、Set、Map 等數據結構，它更高效、占用空間更少，但是缺點是其返回的結果是概率性的，而不是確切的。
2、布隆過濾器的用途
- 解決Redis緩存穿透。
- 在爬蟲時，對爬蟲網址進行過濾，已經存在布隆中的網址，不在爬取。
- 垃圾郵件過濾，對每一個發(fā)送郵件的地址進行判斷是否在布隆的黑名單中，如果在就判斷為垃圾郵件。
- 大量數據時，判斷給定的數據是否在其中。
- 黑名單過濾
3、布隆過濾器的原理
3.1 存入過程
就是將數據以某種方式以二進制形式存入結合中。
過程如下：
- 通過K個哈希函數計算該數據，返回K個計算出的hash值
- 這些K個hash值映射到對應的K個二進制的數組下標
- 將K個下標對應的二進制數據改成1。
例如，第一個哈希函數返回x，第二個第三個哈希函數返回y與z，那么： X、Y、Z對應的二進制改成1。
3.2 查詢過程
布隆過濾器主要作用就是：查詢一個數據在不在這個二進制的集合中。
查詢過程如下：
- 通過K個哈希函數計算該數據，對應計算出的K個hash值
- 通過hash值找到對應的二進制的數組下標
- 判斷：如果存在一處位置的二進制數據是0，那么該數據不存在。如果都是1，該數據存在集合中。（這種判斷存在一定的誤判率）
3.3 刪除過程
一般是不能刪除布隆過濾器的，這也是其一個缺點。
4、布隆過濾器的優(yōu)缺點
4.1 優(yōu)點
- 由于存儲的是二進制數據，所以占用的空間很小
- 它的插入和查詢速度是非?？斓?，時間復雜度是O（K），可以聯想一下HashMap的過程
- 保密性很好，因為本身不存儲任何原始數據，只有二進制數據
4.2 缺點
添加數據是通過計算數據的hash值，那么很有可能存在這種情況：兩個不同的數據計算得到相同的hash值。
例如圖中的“你好”和“hello”，假如最終算出hash值相同，那么他們會將同一個下標的二進制數據改為1。 這個時候，你就不知道下標為2的二進制，到底是代表“你好”還是“hello”。
1.存在誤判率
假如上面的圖沒有存"hello"，只存了"你好"，那么用"hello"來查詢的時候，會判斷"hello"存在集合中。 因為“你好”和“hello”的hash值是相同的，通過相同的hash值，找到的二進制數據也是一樣的，都是1。
2.刪除困難
還是用上面的舉例，因為“你好”和“hello”的hash值相同，對應的數組下標也是一樣的。 這時候想去刪除“你好”，將下標為2里的二進制數據，由1改成了0。 那么我們是不是連“hello”都一起刪了呀。（0代表有這個數據，1代表沒有這個數據）
總結：
- 隨著數據的增加，誤判率隨之增加；
- 無法做到刪除數據；只能判斷數據是否一定不存在，而無法判斷數據是否一定存在。
- 無法返回元素本身
- 無法刪除某個元素
5、python中使用布隆過濾器
使用pybloom_live進行操作。
安裝：
pip install pybloom_live
示例代碼：
from pybloom_live import ScalableBloomFilter, BloomFilter # 可自動擴容的布隆過濾器 bloom = ScalableBloomFilter(initial_capacity=100, error_rate=0.001) url1 = 'http://www.baidu.com' url2 = 'http://www.zhihu.com' bloom.add(url1) print(url1 in bloom) print(url2 in bloom) # BloomFilter 是定長的 bf = BloomFilter(capacity=1000) bf.add(url1) print(url1 in bf) print(url2 in bf)
運行結果：
6、redis中使用布隆過濾器
詳細的文檔可以參考官方文檔：Quick start | Redis
這個模塊不僅僅實現了布隆過濾器，還實現了 CuckooFilter（布谷鳥過濾器），以及 TopK功能。CuckooFilter是在 BloomFilter的基礎上主要解決了BloomFilter不能刪除的缺點。
傳統的redis服務器安裝 RedisBloom 插件
也可以使用docker進行安裝：
- docker pull redislabs/rebloom:latest
- docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
- docker exec -it redis-redisbloom /bin/bash
使用pybloom_live進行操作。
安裝：
pip install redisbloom
示例代碼： 【注意：代碼執(zhí)行之前要確保服務器安裝了redis插件：bloom-filter】
from redisbloom.client import Client
rb = Client(host='192.168.124.27', port='6379')
rb.bfAdd('urls', 'baidu')
rb.bfAdd('urls', 'google')
print(rb.bfExists('urls', 'baidu'))
print(rb.bfExists('urls', 'tencent'))
rb.bfMAdd('urls', 'a', 'b')
print(rb.bfMExists('urls', 'google', 'a', 'd'))運行結果：
示例代碼：
import math
import redis
import time
import mmh3
class BloomFilter(object):
# 內置100個隨機種子
SEEDS = [543, 460, 171, 876, 796, 607, 650, 81, 837, 545, 591, 946, 846, 521, 913, 636, 878, 735, 414, 372,
344, 324, 223, 180, 327, 891, 798, 933, 493, 293, 836, 10, 6, 544, 924, 849, 438, 41, 862, 648, 338,
465, 562, 693, 979, 52, 763, 103, 387, 374, 349, 94, 384, 680, 574, 480, 307, 580, 71, 535, 300, 53,
481, 519, 644, 219, 686, 236, 424, 326, 244, 212, 909, 202, 951, 56, 812, 901, 926, 250, 507, 739, 371,
63, 584, 154, 7, 284, 617, 332, 472, 140, 605, 262, 355, 526, 647, 923, 199, 518]
def __init__(self, capacity=1000000000, error_rate=0.00000001, conn=None, key='BloomFilter'):
"""
初始化布隆過濾器
:param capacity: 預先估計要去重的數量
:param error_rate: 表示錯誤率
:param conn: 表示redis的連接客戶端
:param key: 表示在redis中的鍵的名字前綴
"""
# 需要的總bit位數
self.m = math.ceil(capacity*math.log2(math.e)*math.log2(1/error_rate))
# 需要最少的hash次數
self.k = math.ceil(math.log1p(2)*self.m/capacity)
# 需要的多少M內存
self.mem = math.ceil(self.m/8/1024/1024)
# 需要多少個512M的內存塊,value的第一個字符必須是ascii碼，所有最多有256個內存塊
self.blocknum = math.ceil(self.mem/512)
self.seeds = self.SEEDS[0: self.k]
self.key = key
self.N = 2 ** 31 - 1
self.redis = conn
print(self.m)
print(self.k)
print(self.mem)
def add(self, value):
name = self.key + '_' + str(ord(value[0]) % self.blocknum)
hashs = self.get_hash(value)
for hash in hashs:
self.redis.setbit(name, hash, 1)
def get_hash(self, value):
hashs = list()
for seed in self.seeds:
hash = mmh3.hash(value, seed)
if hash >= 0:
hashs.append(hash)
else:
hashs.append(self.N - hash)
return hashs
def is_exist(self, value):
name = self.key + '_' + str(ord(value[0]) % self.blocknum)
hashs = self.get_hash(value)
exist = True
for hash in hashs:
exist = exist & self.redis.getbit(name, hash)
return exist
pool = redis.ConnectionPool(host='192.168.124.27', port='6379', db=0)
conn = redis.Redis(connection_pool=pool)
start = time.time()
bf = BloomFilter(conn=conn)
url1 = 'www.baidu.com'
url2 = 'www.zhihu.com'
url3 = 'www.study.com'
bf.add(url1)
bf.add(url2)
print(bf.is_exist(url2))
print(bf.is_exist(url3))運行結果：
到此這篇關于python中的布隆過濾器用法及原理詳解的文章就介紹到這了,更多相關python的布隆過濾器內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了python序列去重并保持原始順序操作，文章圍繞了python?序列去重的相關資料展開詳細介紹，需要的小伙伴可以參考一下，希望對你的有所幫助2022-03-03
這篇文章主要介紹了Python?pyecharts案例超市4年數據可視化分析，文章圍繞主題展開詳細的內容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-08-08
這篇文章主要為大家通過簡單示的示例帶大家入門了解Python TkInter框架,讓大家對Python TkInter有一個簡單的認知,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步2023-11-11
今天小編就為大家分享一篇python實現對csv文件的列的內容讀取，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
這篇文章主要為大家介紹了python深度學習tensorflow入門基礎教程示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-06-06
這篇文章主要介紹了python3獲取視頻文件播放時長的三種方法,VideoFileClip,CV2以及FFmpeg這三種方法,文章通過代碼示例給大家講解的非常詳細,需要的朋友可以參考下2024-04-04
Python用做數據處理還是相當不錯的,如果你想要做爬蟲,Python是很好的選擇,它有很多已經寫好的類包,只要調用即可完成很多復雜的功能,下面這篇文章主要給大家介紹了關于Python獲取網頁指定內容的相關資料,需要的朋友可以參考下2022-03-03
這篇文章主要為大家詳細介紹了Python辦公自動化中定時郵件提醒和音視頻文件處理的相關知識,文中的示例代碼講解詳細,需要的小伙伴可以了解下2023-12-12
這篇文章主要介紹了python中set()函數簡介及實例解析，具有一定借鑒價值,需要的朋友可以參考下2018-01-01
餅圖是數據可視化中經典的占比類圖表,核心用于展示各分類在整體中的比例關系,本文基于Matplotlib詳解餅圖的繪制方法,涵蓋基礎繪制、樣式定制、進階優(yōu)化等核心知識點,結合實戰(zhàn)案例讓你快速掌握,需要的朋友可以參考下2025-12-12