Bloom Filter: 原理、使用法、利点、欠点、Python実装

I. 使用法と応用事例

Bloom Filterは、要素が集合に属するかどうかを判断するために使用される、非常にスペース効率の高い確率的データ構造です。多くの分野で幅広い応用があります。

ワードプロセッシングソフトウェアでのスペルチェック: ワードプロセッシングソフトウェアでは、英語の単語のスペルが正しいかどうかを迅速にチェックできます。たとえば、ユーザーが単語を入力すると、Bloom Filterは、その単語が正しい単語の集合に存在する可能性が高いかどうかを迅速に判断できます。そうでない場合は、スペルエラーを促します。
FBI容疑者リストのクエリ: FBIのような機関では、容疑者の名前がすでに容疑者リストに載っているかどうかを迅速に判断するために使用できます。新しい容疑者の情報が入手可能になると、最初にスクリーニングして迅速に処理できるため、効率が向上します。
WebクローラのURLアクセス判断: Webクローラでは、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でない場合、要素が集合に絶対に存在しないと判断できます。逆に、(k) 個のポイントがすべて1の場合、要素が集合に存在する可能性があります。ここでは、要素が集合に必ず存在すると判断できないことに注意してください。特定の誤検知率があります。

たとえば、集合に3つの要素 ({x, y, z}) があり、ハッシュ関数の数が3であると仮定します。集合内の各要素について、要素は3つのハッシュ関数を介して連続してマッピングされます。各マッピングはハッシュ値を生成し、これはビット配列上のポイントに対応し、次にビット配列の対応する位置が1としてマークされます。要素 (W) が集合に存在するかどうかをクエリする場合、(W) は同じ方法でビット配列上の3つのポイントにマッピングされます。3つのポイントのいずれかが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)):
            # weighted sum
            ret += self.seed * ret + ord(value[i])
        # bit operation to ensure the final value is between 0 and 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に要素が存在するかどうかを判断するために使用されます。