ブルームフィルタ入門
ブルーム・フィルターはハッシュ・ベースの確率的データ構造で、実際には非常に長いバイナリ・ベクトルです。スペース効率が良いという利点がありますが、ある種の偽陽性（要素は集合に含まれないが、ブルーム・フィルターはそれが集合に含まれることを示す）があります。
ブルームフィルタの原理
ブルーム・フィルターは長さmビットのビット配列で、初期状態では各ビットは0であり、k個のハッシュ関数が付加されています。
ブルームフィルター 要素の追加
要素を追加する場合、まずk個のハッシュ関数を使用してk個のハッシュ値を取得し、k個のハッシュ値をビット配列の長さでモジュロしてk個の位置を取得し、これらのk個の位置に対応するビットを1に設定します。
ブルームを加えた後、フィルターを加えます。
ブルームフィルタのクエリ要素
ブルーム・フィルターの要素を照会るのは比較的簡単で、まずk個のハッシュ値を得るためにk個のハッシュ関数を使い、次にk個のハッシュ値のモジュラスとビット配列の長さを取ってk個の位置を求め、このk個の位置のビットが1かどうかをチェックします。
ブルームフィルタの偽陽性
クエリ要素では、k個のハッシュ値がすべて1に設定されている可能性がありますが、これは他の要素の操作であり、実際にはその要素はブルームフィルターに入っていないため、偽陽性となります。 次の例で、bloom,filterを追加し、catがブルームフィルターに入っているかどうかを確認した後を見てください。
実際、catはブルーム・フィルターの中にはありません。つまり、ブルームフィルタは真を返し、その要素は必ずしもその中にあるとは限りません。
ブルームフィルターの偽陽性計算
3つの重要なパラメータによる偽陽性計算。
- mはビット配列の長さを表します。
- kはハッシュ関数の数を表します。
- nは挿入された要素の数
ブルーム・フィルターにおいて、ある要素が0ビットで挿入される確率は
(1-1/m)^k
n個の要素を挿入した後、あるビットが0になる確率は
(1-1/m)^(nk)
偽陽性の確率は
(1 ^nk)^k
必要なのはk個の異なるビットが1にセットされることだけなので、確率は約
(1 ^(-kn/m))^k
これは偽陽性の確率です。
Golangコードの実装
で実装されています。このGolang実装は、並行処理やバイト配列、文字列、数値などのバッチ結合をサポートしています。
bit配列のサイズは
コードでは、ビット配列は[]byte配列として表現されています。後続の[]byte内のハッシュの位置決めには剰余演算が必要なため、%演算はより低速な演算となり、配列の長さが2のn乗であれば、%は & に最適化できます。したがって、New() 関数の初期化では、[]byte 配列の長さを 2^n に伸ばして計算を高速化します。
type Filter struct {
lock *sync.RWMutex
concurrent bool
m uint64 // bit array of m bits, m will be ceiling to power of 2
n uint64 // number of inserted elements
log2m uint64 // log_2 of m
k uint64 // the number of hash function
keys []byte // byte array to store hash value
}
func New(size uint64, k uint64, race bool) *Filter {
log2 := uint64(math.Ceil(math.Log2(float64(size))))
filter := &Filter{
m: 1 << log2,
log2m: log2,
k: k,
keys: make([]byte, 1<<log2),
concurrent: race,
}
if filter.concurrent {
filter.lock = &sync.RWMutex{}
}
return filter
}
// location returns the bit position in byte array
// & (f.m - 1) is the quick way for mod operation
func (f *Filter) location(h uint64) (uint64, uint64) {
slot := (h / bitPerByte) & (f.m - 1)
mod := h & mod7
return slot, mod
}
hash関数の選択
高速に動作させる必要があるため、md5,shaや他の時間のかかるハッシュ操作を選択しないでください。結果、私はmurmur3のハッシュアルゴリズムを使用してキーをハッシュすることを選択しました。
// baseHash returns the murmur3 128-bit hash
func baseHash(data []byte) []uint64 {
a1 := []byte{1} // to grab another bit of data
hasher := murmur3.New128()
hasher.Write(data) // #nosec
v1, v2 := hasher.Sum128()
hasher.Write(a1) // #nosec
v3, v4 := hasher.Sum128()
return []uint64{
v1, v2, v3, v4,
}
}
要素のバイト配列を入力し、そのハッシュ値を返し、この要素の位置を計算します。
詳しくは、コード実装をご覧ください。
