Bloom Filter徹底解説！Pythonでの簡単実装

Posted at 2025-02-08

Leapcell: Python Webホスティングの最高のサーバレスプラットフォーム

Bloom Filter: 原理、用途、利点、欠点及びPython実装

I. 用途と適用シナリオ

Bloom Filterは、要素がセットに属するかどうかを判断するために使用される、非常に省スペースな確率的なデータ構造です。多くの分野で幅広く応用されています：

文書処理ソフトウェアにおけるスペルチェック：文書処理ソフトウェアでは、英単語のスペルが正しいかどうかを迅速にチェックできます。例えば、ユーザーが単語を入力すると、Bloom Filterはその単語が正しい単語のセットに含まれる可能性があるかどうかを迅速に判断できます。含まれていない場合は、スペルエラーを表示します。
FBIの容疑者リスト照会：FBIのような機関では、容疑者の名前が既に容疑者リストに載っているかどうかを迅速に判断するために使用できます。新しい容疑者情報が入手できたとき、最初に迅速にスクリーニングでき、効率を向上させます。
ウェブクローラのURLアクセス判断：ウェブクローラでは、URLが既に訪問されたかどうかを効率的に判断できます。これにより、同じURLへの重複アクセスを回避し、リソースを節約します。
メールスパムフィルタリング：YahooやGmailなどのメールサービスのメールスパムフィルタリング機能は、Bloom Filterを使用してメールがスパムかどうかを判断できます。まず、いくつかの特徴を使ってメールがスパムの可能性があるかどうかを判断します。可能性がある場合は、さらに処理を行います。
キャッシュペネトレーションの防止：キャッシュシステムでは、Bloom Filterがキャッシュペネトレーション問題を防止できます。大量の要求が同時にキャッシュに存在しないデータにアクセスすると、データベースに過大な負荷がかかる可能性があります。Bloom Filterはまず、データが存在する可能性があるかどうかを判断できます。存在しない可能性がある場合は、直接返し、無効なデータベースクエリを回避します。

II. アルゴリズムの利点と欠点

(I) 利点

小さなデータスペース：Bloom Filterはデータ自体を保存する必要がありません。代わりに、ビット配列とハッシュ関数を使用してデータの存在をマークし、大幅に記憶容量を節約します。すべての要素を保存する従来の方法と比較して、大量のデータを保存する場合に明らかな利点があります。

(II) 欠点

誤判定の存在：マッチングに失敗した場合は、要素が「確実にセットに含まれていない」と判断できますが、マッチングに成功しても、値が確実にセットに含まれていることを保証するものではありません。一定の偽陽性率が存在します。これは、異なる要素がハッシュ関数によってマッピングされた後、ビット配列の同じビット位置を占める可能性があるためです。
要素の削除ができない：要素をセットに追加すると、削除することができません。特定の要素を削除すると、他の要素の判断結果に影響を与える可能性があります。Bloom Filterを再構築する場合を除きます。
容量に応じた偽陽性率の変化：セットがほぼいっぱいになったとき、つまり推定最大容量に近づいたとき、偽陽性の確率が増加します。これは、ビット配列で1に設定されるビットの数が増えるため、誤判定が起こりやすくなるからです。
スペース占有の拡大：一般的に、1％の偽陽性率の場合、各要素は10ビット未満のスペースを必要とし、これはセット内の要素のサイズや数には依存しません。比較的省スペースですが、大規模なデータの場合、全体で占有するスペースは依然として大きくなります。
クエリ処理が遅い：複数のハッシュ関数を使用するため、各マッチングプロセスでは、存在を確認するために複数のビット（ハッシュの数）をチェックする必要があり、クエリ処理が遅くなります。

III. 原理の紹介

(I) アルゴリズム原理

Bloom Filterは、セットに特定の要素が含まれるかどうかを判断するアルゴリズムです。データ自体を保存する必要はなく、非常に大きなビット配列といくつかのハッシュ関数を通じて実装されます。

ビット配列の長さを(m)、ハッシュ関数の数を(k)とします。まず、ビット配列を初期化し、各ビットを0に設定します。

要素をセットに追加するとき、入力文字列はハッシュ関数を通じてビット配列の添字にマッピングされ、その後、添字に対応する値が1に設定されます。例えば、ある文字列を(k)個のハッシュ関数で計算すると、(k)個の添字位置が得られ、これらの(k)個の位置のビットはすべて1に設定されます。同じ文字列を2回目に計算すると、ハッシュ関数によって同じ添字位置にマッピングされます。

要素が存在するかどうかを照会するとき、要素は同じ(k)個のハッシュ関数を通じてビット配列上の(k)個の点にマッピングされます。これらの(k)個の点のうち1つが1でない場合は、要素がセットに確実に存在しないと判断できます。逆に、(k)個の点すべてが1の場合は、要素がセットに存在する可能性があります。ここでは、要素が必ずセットに存在すると判断することはできず、一定の偽陽性率があります。

例えば、セットに3つの要素({x, y, z})があり、ハッシュ関数の数が3であると仮定します。セット内の各要素について、要素は順次3つのハッシュ関数を通じてマッピングされます。各マッピングでは、ハッシュ値が生成され、これはビット配列上の1点に対応し、その後、ビット配列の対応する位置が1にマークされます。要素(W)がセットに存在するかどうかを照会するとき、(W)は同じ方法を通じてビット配列上の3点にマッピングされます。3点のうち1点が1でない場合は、要素がセットに確実に存在しないと判断できます。逆に、3点すべてが1の場合は、要素がセットに存在する可能性があります。図から分かるように、ある要素がマッピングによって添字4、5、6にマッピングされると仮定します。これら3点はすべて1ですが、明らかにこれら3点は異なる要素がハッシュ化によって得られた位置です。したがって、この状況は、要素がセットに存在しないにもかかわらず、対応するビットがすべて1になる可能性があることを示しており、これが偽陽性率が存在する理由です。

(II) 簡単なPython実装

以下は、BloomFilterのPythonコード実装例です。本当のBloomFilterの実装では、初期化されたビット配列の長さに応じてハッシュ関数の数を決定する必要があり、また複雑なハッシュ化プロセスも必要です。

#_*_coding:utf_8_
import BitVector
import os
import sys


class SimpleHash():
    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])
        # ビット演算により最終的な値が0からself.capの間になるようにする
        return (self.cap - 1) & ret


class BloomFilter():
    def __init__(self, BIT_SIZE=1 << 25):
        self.BIT_SIZE = 1 << 25
        self.seeds = [5, 7, 11, 13, 31, 37, 61]
        self.bitset = BitVector.BitVector(size=self.BIT_SIZE)
        self.hashFunc = []

        for i in range(len(self.seeds)):
            self.hashFunc.append(SimpleHash(self.BIT_SIZE, self.seeds[i]))
        print(self.hashFunc)

    def insert(self, value):
        for f in self.hashFunc:
            loc = f.hash(value)
            self.bitset[loc] = 1
        print(self.bitset)

    def is_contaions(self, value):
        if value == None:
            return False
        ret = True
        for f in self.hashFunc:
            loc = f.hash(value)
            ret = ret & self.bitset[loc]
        return ret

上記のコードでは、SimpleHashクラスが単純なハッシュ関数を実装し、BloomFilterクラスはビット配列と複数のハッシュ関数を初期化し、要素の挿入と存在判断の機能を実現しています。insertメソッドは要素をBloom Filterに挿入するために使用され、is_contaionsメソッドは要素がBloom Filterに存在するかどうかを判断するために使用されます。