欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python中的布隆過濾器用法及原理詳解

 更新時間：2023年07月26日 09:07:44   作者：IT之一小佬  
這篇文章主要介紹了python中的布隆過濾器用法及原理詳解,布隆過濾器是一種概率空間高效的數(shù)據(jù)結(jié)構(gòu),它與hashmap非常相似，用于檢索一個元素是否在一個集合中。它在檢索元素是否存在時，能很好地取舍空間使用率與誤報比例,需要的朋友可以參考下

1、布隆過濾器的介紹

布隆過濾器（Bloom Filter），是1970年，由一個叫布隆的小伙子提出的。 它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)，二進制大家應(yīng)該都清楚，存儲的數(shù)據(jù)不是0就是1，默認是0。

主要用于判斷一個元素是否在一個集合中，0代表不存在某個數(shù)據(jù)，1代表存在某個數(shù)據(jù)。

布隆過濾器是一種概率空間高效的數(shù)據(jù)結(jié)構(gòu)，特點是高效地插入和查詢，用來告訴你 “某樣?xùn)|西一定不存在或者可能存在”。

相比于傳統(tǒng)的 List、Set、Map 等數(shù)據(jù)結(jié)構(gòu)，它更高效、占用空間更少，但是缺點是其返回的結(jié)果是概率性的，而不是確切的。

2、布隆過濾器的用途

  • 解決Redis緩存穿透。
  • 在爬蟲時，對爬蟲網(wǎng)址進行過濾，已經(jīng)存在布隆中的網(wǎng)址，不在爬取。
  • 垃圾郵件過濾，對每一個發(fā)送郵件的地址進行判斷是否在布隆的黑名單中，如果在就判斷為垃圾郵件。
  • 大量數(shù)據(jù)時，判斷給定的數(shù)據(jù)是否在其中。
  • 黑名單過濾

3、布隆過濾器的原理

3.1 存入過程

就是將數(shù)據(jù)以某種方式以二進制形式存入結(jié)合中。

過程如下：

  1. 通過K個哈希函數(shù)計算該數(shù)據(jù)，返回K個計算出的hash值
  2. 這些K個hash值映射到對應(yīng)的K個二進制的數(shù)組下標
  3. 將K個下標對應(yīng)的二進制數(shù)據(jù)改成1。

例如，第一個哈希函數(shù)返回x，第二個第三個哈希函數(shù)返回y與z，那么： X、Y、Z對應(yīng)的二進制改成1。

3.2 查詢過程

布隆過濾器主要作用就是：查詢一個數(shù)據(jù)在不在這個二進制的集合中。

查詢過程如下：

  1. 通過K個哈希函數(shù)計算該數(shù)據(jù)，對應(yīng)計算出的K個hash值
  2. 通過hash值找到對應(yīng)的二進制的數(shù)組下標
  3. 判斷：如果存在一處位置的二進制數(shù)據(jù)是0，那么該數(shù)據(jù)不存在。如果都是1，該數(shù)據(jù)存在集合中。（這種判斷存在一定的誤判率）

3.3 刪除過程

一般是不能刪除布隆過濾器的，這也是其一個缺點。

4、布隆過濾器的優(yōu)缺點

4.1 優(yōu)點

  1. 由于存儲的是二進制數(shù)據(jù)，所以占用的空間很小
  2. 它的插入和查詢速度是非?？斓?，時間復(fù)雜度是O（K），可以聯(lián)想一下HashMap的過程
  3. 保密性很好，因為本身不存儲任何原始數(shù)據(jù)，只有二進制數(shù)據(jù)

4.2 缺點

添加數(shù)據(jù)是通過計算數(shù)據(jù)的hash值，那么很有可能存在這種情況：兩個不同的數(shù)據(jù)計算得到相同的hash值。

例如圖中的“你好”和“hello”，假如最終算出hash值相同，那么他們會將同一個下標的二進制數(shù)據(jù)改為1。 這個時候，你就不知道下標為2的二進制，到底是代表“你好”還是“hello”。

1.存在誤判率

假如上面的圖沒有存"hello"，只存了"你好"，那么用"hello"來查詢的時候，會判斷"hello"存在集合中。 因為“你好”和“hello”的hash值是相同的，通過相同的hash值，找到的二進制數(shù)據(jù)也是一樣的，都是1。

2.刪除困難

還是用上面的舉例，因為“你好”和“hello”的hash值相同，對應(yīng)的數(shù)組下標也是一樣的。 這時候想去刪除“你好”，將下標為2里的二進制數(shù)據(jù)，由1改成了0。 那么我們是不是連“hello”都一起刪了呀。（0代表有這個數(shù)據(jù)，1代表沒有這個數(shù)據(jù)）

總結(jié)：

  • 隨著數(shù)據(jù)的增加，誤判率隨之增加；
  • 無法做到刪除數(shù)據(jù)；只能判斷數(shù)據(jù)是否一定不存在，而無法判斷數(shù)據(jù)是否一定存在。
  • 無法返回元素本身
  • 無法刪除某個元素

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)

運行結(jié)果：

6、redis中使用布隆過濾器

詳細的文檔可以參考官方文檔：Quick start | Redis

這個模塊不僅僅實現(xiàn)了布隆過濾器，還實現(xiàn)了 CuckooFilter（布谷鳥過濾器），以及 TopK功能。CuckooFilter是在 BloomFilter的基礎(chǔ)上主要解決了BloomFilter不能刪除的缺點。

傳統(tǒng)的redis服務(wù)器安裝 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í)行之前要確保服務(wù)器安裝了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'))

運行結(jié)果：

示例代碼：

import math
import redis
import time
import mmh3
class BloomFilter(object):
    # 內(nèi)置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: 預(yù)先估計要去重的數(shù)量
        :param error_rate: 表示錯誤率
        :param conn: 表示redis的連接客戶端
        :param key: 表示在redis中的鍵的名字前綴
        """
        # 需要的總bit位數(shù)
        self.m = math.ceil(capacity*math.log2(math.e)*math.log2(1/error_rate))
        # 需要最少的hash次數(shù)
        self.k = math.ceil(math.log1p(2)*self.m/capacity)
        # 需要的多少M內(nèi)存
        self.mem = math.ceil(self.m/8/1024/1024)
        # 需要多少個512M的內(nèi)存塊,value的第一個字符必須是ascii碼，所有最多有256個內(nèi)存塊
        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))

運行結(jié)果：

到此這篇關(guān)于python中的布隆過濾器用法及原理詳解的文章就介紹到這了,更多相關(guān)python的布隆過濾器內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • Python如何獲取對象大小和文件大小

    Python如何獲取對象大小和文件大小

    這篇文章主要介紹了Python如何獲取對象大小和文件大小問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-01-01
  • Python入門教程(三十二)Python的命令行輸入

    Python入門教程(三十二)Python的命令行輸入

    這篇文章主要介紹了Python入門教程(三十二)Python的命令行輸入,Python是一門非常強大好用的語言,也有著易上手的特性,本文為入門教程,需要的朋友可以參考下
    2023-05-05
  • 9行Python3代碼實現(xiàn)批量提取PDF文件的指定內(nèi)容

    9行Python3代碼實現(xiàn)批量提取PDF文件的指定內(nèi)容

    這篇文章主要為大家詳細介紹了如何通過9行Python3代碼實現(xiàn)批量提取PDF文件的指定內(nèi)容，文中的示例代碼講解詳細，感興趣的小伙伴可以嘗試一下
    2022-12-12
  • python 在右鍵菜單中加入復(fù)制目標文件的有效存放路徑(單斜杠或者雙反斜杠)

    python 在右鍵菜單中加入復(fù)制目標文件的有效存放路徑(單斜杠或者雙反斜杠)

    這篇文章主要介紹了python 在右鍵菜單中加入復(fù)制目標文件的有效存放路徑（單斜杠或者雙反斜杠），本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-04-04
  • Python PyCharm如何進行斷點調(diào)試

    Python PyCharm如何進行斷點調(diào)試

    這篇文章主要介紹了Python PyCharm如何進行斷點調(diào)試,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-07-07
  • python中如何寫類

    python中如何寫類

    在本篇文章里小編給大家分享的是一篇關(guān)于python中寫類的方法和技巧，需要的朋友們可以學(xué)習(xí)下。
    2020-06-06
  • pytorch中[..., 0]的用法說明

    pytorch中[..., 0]的用法說明

    這篇文章主要介紹了pytorch中[..., 0]的用法說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
    2021-05-05
  • Python的iOS自動化打包實例代碼

    Python的iOS自動化打包實例代碼

    這篇文章主要給大家介紹了關(guān)于Python的iOS自動化打包的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2018-11-11
  • 使用go和python遞歸刪除.ds store文件的方法

    使用go和python遞歸刪除.ds store文件的方法

    使用python和go遞歸刪除.DS_Store文件，.DS_Store (英文全稱 Desktop Services Store)是一種由蘋果公司的Mac OS X操作系統(tǒng)所創(chuàng)造的隱藏文件，目的在于存貯文件夾的自定義屬性
    2014-01-01
  • Pytorch?Mac?GPU?訓(xùn)練與測評實例

    Pytorch?Mac?GPU?訓(xùn)練與測評實例

    這篇文章主要為大家介紹了Pytorch?Mac?GPU?訓(xùn)練與測評實例詳解,有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
    2023-01-01

最新評論