ブルームフィルタのわかりやすい解説（基本概念、確率分析、ソースコード分析）

2年 ago
優斗, 朝陽
1 minute

ブルームフィルターは、ある要素が集合に属しているかどうかを判定するために使用する確率論的データ構造です。実際の要素を保持する必要がないため、要素の検索が高速に行え、小さめの記憶域で済みます。

基本の考え方

  1. ブルームフィルタは集合を表すためにビット配列（ビットマップ）を使用し、最初にすべてのビットは0に設定されています。
  2. ハッシュ関数を通して要素を配列の異なる位置に写し、対応する位置のビットを1に設定します。
  3. ハッシュ関数で検索する要素を対応する配列の位置にマッピングし、対応するすべての位置が1であれば要素は集合中に存在する可能性があり、そうでなければ存在しない。

統計的解析

ブルームフィルタは複数のハッシュ関数を使って写像を行うため、ハッシュ衝突が発生する可能性があります。ブルームフィルタにn個の要素があり、ビット配列の長さがmで、k個のハッシュ関数を使用すると、各要素がビット配列の位置に写像される確率は1/mとなり、1ビットが0である確率は(1-1/m)^knとなります。要素を検索するとき、すべての対応するビット位置が1であれば、そのエレメントが集合内にある可能性を示します。ただし、他の要素も対応するビット位置を1にするハッシュ衝突が発生する可能性があり、誤判定率が生じる可能性があります。

コード解析：

Bloomフィルタの簡単なコード例を以下に示します。

from bitarray import bitarray
import mmh3
class BloomFilter:
def __init__(self, size, num_hashes):
self.size = size
self.num_hashes = num_hashes
self.bit_array = bitarray(size)
self.bit_array.setall(0)
def add(self, item):
for i in range(self.num_hashes):
index = mmh3.hash(item, i) % self.size
self.bit_array[index] = 1
def contains(self, item):
for i in range(self.num_hashes):
index = mmh3.hash(item, i) % self.size
if self.bit_array[index] == 0:
return False
return True
# 使用示例
bf = BloomFilter(1000000, 5)
bf.add("apple")
print(bf.contains("apple"))  # 输出True
print(bf.contains("banana")) # 输出False

このコードは、ブルームフィルタを実装するために、サードパーティのライブラリである bitarray と mmh3 を使用しています。bitarray はビット配列を表すために使用され、mmh3 はハッシュ値を計算するために使用されます。ブルームフィルタの初期化時に、ビット配列の長さとハッシュ関数の数を指定する必要があります。add メソッドは要素をブルームフィルタに追加するために使用され、contains メソッドは要素がブルームフィルタに存在するかどうかを判断するために使用されます。要素を照会する際、同じハッシュ関数を使用して計算し、対応する位置のビットが 1 かどうかを確認する必要があります。

bannerAds