Guavaを使用したJavaブルームフィルター

すべての良い一日。



データ処理のさまざまな構造とアルゴリズムの知識を向上させ、さまざまな言語の代数的問題と動的プログラミング問題を解決するために設計された新しいコース「開発者向けアルゴリズム」を開始しました。 そこで、本日、Javaでのブルームフィルターの操作に関する小さなメモを共有します。



はじめに



この記事では、グアバライブラリのブルームフィルターの構造を見ていきます。 ブルームフィルターは、効率的なメモリ使用量を備えた確率的データ構造であり、「この要素はセットに含まれていますか？」という質問に答えるために使用できます。



ブルームフィルターには偽陰性がないため、falseを返した場合、この要素がセットに含まれていないことを100％確信できます。



ただし、ブルームフィルターはfalse positiveを返す可能性があるため、trueが返されると、要素が実際にセット内にある確率は高くなりますが、確率は100％ではありません。



ブルームフィルターの操作の詳細については、 このガイドをご覧ください。







メイベン中毒



ブルームフィルターのGuava実装を使用するため、Guava依存関係を追加します

最新バージョンはMaven Centralにあります。

<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>22.0</version> </dependency>
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ブルームフィルターを使用する理由



ブルームフィルターは、 経済的で高速になるように設計されています。 それを使用するとき、 受け入れる準備ができている偽陽性の回答の確率を指定することができ 、設定に従って、ブルームフィルターはできるだけ少ないメモリを占有します。



ブルームフィルターは、その経済性により、多数の要素が含まれている場合でもメモリに簡単に収まります。 CassandraやOracleなどの一部のデータベースは、特定のIDのリクエストを受信した場合など、ディスクまたはキャッシュにアクセスする前の初期チェックにこのフィルターを使用します。



IDがないことをフィルターが示している場合、データベースは要求の処理を停止し、クライアントに戻ることがあります。 それ以外の場合、クエリはディスクに移動し、見つかったアイテムを返します。



ブルームフィルターの作成



500個以下の整数に対してブルームフィルターを作成し、1パーセント（0.01）の誤検出確率で3倍にしたいとします。



これを行うには、GuavaライブラリのBloomFilter



クラスを使用できます。 フィルタに報告された要素の数と、誤検知の望ましい確率を転送する必要があります。

 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 500, 0.01);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、フィルターにいくつかの数値を追加します。

 filter.put(1); filter.put(2); filter.put(3);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

3つの要素のみを追加し、挿入の最大数である500を決定したため、ブルームフィルターはかなり正確な結果を提供するはずです。 mightContain()



メソッドでテストします：

 assertThat(filter.mightContain(1)).isTrue(); assertThat(filter.mightContain(2)).isTrue(); assertThat(filter.mightContain(3)).isTrue(); assertThat(filter.mightContain(100)).isFalse();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

名前が示すように、メソッドがtrueを返した場合、この要素が実際にフィルター内にあることを100％確信することはできません。



私たちのケースでは、 mightContain()



がtrueを返す場合、要素がフィルター内にあることを99％、1％の場合、結果は偽陽性です。 フィルターがfalseを返す場合、要素が欠落していることを100％確信できます。



過飽和ブルームフィルター



ブルームフィルターを設計する場合、予想される要素数に対して十分に正確な値を提供することが重要です。 それ以外の場合、フィルターは必要以上に頻繁に誤検知を返します。 例を考えてみましょう。



1％に等しい誤検知の望ましい確率と5に等しい要素の予想数でフィルターを作成するとしますが、100,000個の要素を挿入します。

 BloomFilter<Integer> filter = BloomFilter.create( Funnels.integerFunnel(), 5, 0.01); IntStream.range(0, 100_000).forEach(filter::put);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

要素が非常に少ないことを期待して、フィルターは非常に少ないメモリを占有します。

ただし、はるかに多くの要素を追加すると、フィルターは過飽和状態になり、望ましい1％よりも偽陽性の結果を生成する可能性が高くなります。



mightContatin()



メソッドは、以前にフィルターに挿入しなかった値に対してもtrueを返すことに注意してください。



おわりに



このクイックチュートリアルでは、Guava実装を使用して、ブルームフィルターデータ構造の確率的性質を調べました。



これらすべての例とコードスニペットの実装は、 GitHubプロジェクトにあります。



これはMavenプロジェクトなので、インポートと起動は難しくありません。



終わり



コメントと質問を待っています。いつものように、ここに残して、コースティーチャーのミハイルゴルシコフに 公開の日に行くことができます。