1. 概要

私たちの多くは警告メッセージを見たに違いありません–ユーザー名または電子メールはすでに使用されています。 注意深く気付くと、警告メッセージが数秒以内に表示されます。 すべてのWebサイトは、サインアッププロセス中にこの検証を実行します。

Webサイトが数百万のレコードを数秒で検証する方法を考えたことはありますか？ 解決策の1つは、 ブルームフィルター 。 

このチュートリアルでは、ブルームフィルターとは、サポートされている操作、使用法、および制限について説明します。

2. ブルームフィルターとは何ですか？

ブルームフィルターは確率的なデータ構造です。 要素がセットのメンバーであるかどうかをテストするために使用されます 。 もちろん、他のデータ構造を使用しても同じ結果を得ることができます。 ただし、ブルームフィルターは、これを空間的かつ時間効率の良い方法で実行します。

ブルームフィルターがどのように実装されているかを理解しましょう。 内部的には、ブルームフィルターはビットの配列であり、最初はすべてのビットがゼロに設定されています。 次の図は、サイズ19のブルームフィルターを示しています。

3. ブルームフィルターの操作

ブルームフィルターは、挿入とルックアップの2つの操作のみをサポートします。 例でそれらを理解しましょう：

3.1. 入れる

一定の空間と時間の複雑さで挿入操作を実行できます。  ブルームフィルターは、挿入操作に対して以下の手順を実行します。

  1. 入力値をハッシュします
  2. 配列の長さで結果を変更します
  3. 対応するビットを1に設定します

JohnDoeとJaneDoe の2つの文字列をブルームフィルターに挿入して、これを説明しましょう。 これら2つの文字列のハッシュ値がそれぞれ1355と8337であると仮定します。 次に、モジュロ演算を実行して、ビット配列の範囲内のインデックスを取得しましょう：1355％19 = 6および8337％19=15。

値を挿入すると、ブルームフィルターは次のようになります。

3.2. 調べる

一定の時間計算量でルックアップ操作を実行できます。 ブルームフィルターは、ルックアップ操作の一部として以下の手順を実行します。

  1. 入力値をハッシュします
  2. 配列の長さで結果を変更します
  3. 対応するビットが0または1かどうかを確認します

ビットが0の場合、その入力は間違いなくセットのメンバーではありません。 ただし、ビットが1の場合、その入力はセットのメンバーである可能性があります 。 それでは、文字列Johnがブルームフィルターに存在するかどうかを確認しましょう。

この例では、10 th インデックスのビットは0です。これは、指定された文字列がブルームフィルターに存在しないことを示します。

4. 誤検知分析

ブルームフィルターは、スペースと時間の効率的なデータ構造です。 ただし、その効率のトレードオフは、本質的に確率的であるということです。 。 存在しない要素を検索すると、間違った答えが返される可能性があることを意味します。 このセクションでは、 false-positive シナリオと、その頻度を減らすための可能な解決策について説明します。

文字列JamesBondがブルームフィルターに存在するかどうかを確認しましょう。 入力文字列のハッシュ値が1355であると仮定します。これは、 JohnDoeと同じです。

この例では、ルックアップ操作はtrueの結果を返します。 ただし、文字列 JamesBondをブルームフィルターに挿入したことはありません。

偽陽性シナリオは、ハッシュ衝突が原因で発生します。 複数のハッシュ関数を使用して、ハッシュの衝突頻度を減らすことができます。 したがって、1ビットだけを設定する代わりに、1つの入力に対して複数のビットが設定されます。

5. ブルームフィルターの用途

ブルームフィルターは、その効率のために多くの一般的なアプリケーションで使用されています。 それらのユースケースのいくつかについて説明しましょう。

  • スペルチェッカー：初期には、スペルチェッカーはブルームフィルターを使用して実装されていました
  • データベース：多くの一般的なデータベースは、ブルームフィルターを使用して、存在しない行または列のコストのかかるディスクルックアップを削減します。 この手法は、 PostgreSQL 、 Apache Cassandra 、 CloudBigtableなどで使用されています。
  • 検索エンジン：BitFunnelは検索エンジンのインデックス作成アルゴリズムです。 検索インデックスにブルームフィルターを使用します
  • セキュリティ：ブルームフィルターは、脆弱なパスワード、悪意のあるURLなどを検出するために使用されます

6. ブルームフィルターの制限

ブルームフィルターはスペースと時間の効率的なデータ構造ですが、いくつかの制限があります。

  • ブルームフィルターの単純な実装は、削除操作をサポートしていません
  • 偽陽性率は下げることができますが、ゼロに下げることはできません

7. 結論

この記事では、ブルームフィルターとは何かとそのサポートされている操作について説明しました。 次に、ブルームフィルターの false-positive の性質と、エラーが発生しにくいようにするための可能な解決策を確認しました。 また、人気のあるソフトウェアのいくつかがブルームフィルターを活用して効率を向上させる方法についても説明しました。 最後に、ブルームフィルターの制限について説明しました。