Java
BloomFilter
ブルームフィルタ
偽陽性

BloomFilterの説明と実装サンプル(JAVA)

1. BloomFilterの説明と例

1-1. 前提のユースケース

ちょっと小難しいので例をあげる。
適切なユースケースでもないし現実味もないが。

  1. スマホで相手の口座番号を入力して送金できるアプリを作る
  2. 存在しない口座番号には送金できない

このケースだと

  1. 相手の口座番号をサーバのデータベースに問い合わせる
  2. 存在しなければエラーを返し、存在すればそこに入金処理を行う

となる。

ここで、以下のように
その口座番号が存在するかしないかの一覧をアプリが持っていれば
わざわざネットワークを介してデータベースに口座番号の存在を問い合わせる必要はなくなる。

口座番号
111-111-111
222-222-222
333-333-333
.........

ただし、口座番号が膨大である場合、スマホアプリでそれだけの情報を保持するのは難しい。
そういう時にBloomFilterを用いると、口座番号の存在有無が「ほぼ」分かる情報を非常にコンパクトに持てる。

1-2. 仕組み

くわしい説明はWikiで。

  1. 0と1のビット情報を持てるような一定長のレコードを用意する
  2. 口座番号にハッシュ関数をかけ、結果のハッシュをレコード長の01のビット列に変換する
  3. レコードの該当する位置にビットを立てる

この際、1が立つ位置は複数あるイメージになる。

0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0

これを全ての口座番号分繰り返すと1が立つ位置は増えていく。

上記のアプリで口座番号を入力した場合にこのレコードさえあれば
全く同じハッシュ⇒01ビット列変換を掛けて、1が立っている部分をレコードと突合し
全て1が立っていれば、その口座番号が存在している確率が極めて高いことが分かる。

  • 上段:全ての口座番号の情報を持つレコード
  • 下段:口座番号「111-111-111」をハッシュ⇒01変換した結果
0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0

⇒ 対象の位置すべてに1が立っているため、そのレコードは存在する可能性が極めて高い。

「極めて高い」というのは絶対ではないからだ。
なぜなら1が立つ位置は他の口座番号と衝突するので
他の口座番号情報のビット列によってその位置に1を立てられている可能性がある。

  • 1行目:以下の口座番号の情報を持つレコード
  • 2行目:存在する口座番号「111-111-111」のビット情報
  • 3行目:存在する口座番号「222-222-222」のビット情報
0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0

ここで、存在しない口座番号「999-999-999」を
ハッシュ⇒01ビット変換かけた結果が以下のようになったら、誤ってデータは存在すると判定される。

  • 1行目:以下の口座番号の情報を持つレコード(前と同じ)
  • 2行目:存在しない口座番号「999-999-999」の変換結果
0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 1 0
0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0

1が立つ位置に一つでも0があればデータがないと100%確定的に断定できるが
全ての1が立つ位置に1があっても、データがあるとは100%確定できない。
このような特徴を偽陰性はないが、偽陽性はある、と言う。

レコード長を十分長く取ることで偽陽性は低下するが、
あまりに長いレコードに取ると容量が圧迫されてしまう。

もっとも、100万件の口座番号(何桁でもいい)に対し
概ね 1.2MB程度の領域さえあれば偽陽性は1%程度に収束する。
仮に、1.8MB程度の領域が用意できれば、偽陽性は0.1%程度にまで収束する。

なので、上記のようなアプリでは僅かなレコードを保持するだけで
大幅にネットワークアクセス、データベースアクセスを抑制できることになる。

なお、この場合だと新規に口座が追加されるたびに
更新されたレコードをダウンロードするのかというツッコミどころはある。

複数のストレージやセグメントにデータが格納されている場合に
データの格納場所を効率的に探したりということにも使えるのだがそれだと伝わりづらいし
他に簡単に説明できる良いユースケースが直ぐ思い浮かばなかったので勘弁いただきたい。

2. BloomFilterの実装サンプル

Javaでの実装そのまま載せます。

MyBloomFilter.java
import java.io.Serializable;
import java.nio.charset.Charset;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;

/**
 * BloomFilterの最も基本的な機能のみを備える
 * @author owl
 * @param <E>
 */
public class MyBasicBloomFilter<E> implements Serializable {

    private final BitSet bitFilter;                                             // Filter本体
    private final int bitFilterSize;                                            // Filterのサイズ
    private int numberOfAddedElements;                                          // 現在の要素数
    private final int countOfHashNumCreatePerOneElement;                        // 要素あたりのTrueビット数(ハッシュ化⇒数値変換の回数)

    static final Charset DEFAULT_CHARSET = Charset.forName("UTF-8");            

    /**
     * 偽陽性レベル
     * High: 偽陽性は高いが、フィルタサイズはコンパクトで、パフォーマンスも良好
     * Middle: 偽陽性とフィルタサイズと、パフォーマンスのバランスを取る
     * Low: フィルタサイズの増大や、処理時間の長さを招いても偽陽性を極力低く抑える
     */
    public static enum FalsePositiveProbability{ High, Middle, Low }

    /**
     * メッセージダイジェストの実行
     */
    static final MessageDigest digestFunction;
    static final String hashName = "MD5";                                       
    static {                                                                    
        MessageDigest tmp;
        try { tmp = java.security.MessageDigest.getInstance(hashName); } catch (NoSuchAlgorithmException e) { tmp = null; }
        digestFunction = tmp;
    }    

    /**
     * コンストラクタ
     * @param c 1要素あたりで利用するビット数
     * @param n (想定する最大の)要素数
     * @param k 要素あたりのTrueビット数(ハッシュ化⇒数値変換の回数)
     */
    public MyBasicBloomFilter(double c, int n, int k) {

        this.countOfHashNumCreatePerOneElement = k;

        // 要素数 * 要素あたり利用ビット数でFilterのビットサイズを決定する
        this.bitFilterSize = (int)Math.ceil(c * n);

        numberOfAddedElements = 0;
        this.bitFilter = new BitSet(bitFilterSize);

    }


    /**
     * 
     * @param expectedItemCount
     * @param fpp 
     */
    public MyBasicBloomFilter(int expectedItemCount, FalsePositiveProbability fpp) {

        switch(fpp){
            case High : {
                this.bitFilterSize = (int)Math.ceil(expectedItemCount * 4.8); 
                break;
            }
            case Low : {
                this.bitFilterSize = (int)Math.ceil(expectedItemCount * (9.6 + 4.8));
                break;
            }
            default : {
                this.bitFilterSize = (int)Math.ceil(expectedItemCount * 9.6);
            }
        }
        this.countOfHashNumCreatePerOneElement
                = (int) Math.round((this.bitFilterSize / (double)expectedItemCount) * Math.log(2.0));
        numberOfAddedElements = 0;
        this.bitFilter = new BitSet(bitFilterSize);        

    }
    public MyBasicBloomFilter(int expectedItemCount) {
        this(expectedItemCount, FalsePositiveProbability.Middle);
    }

    /**
     * ハッシュ化
     * @param data 入力データ
     * @param hashCount 回数
     * @return ハッシュ化して求められた数値(ビット立て位置)
     */
    public static int[] createHashes(byte[] data, int hashCount) {
        int[] result = new int[hashCount];

        int k = 0;
        byte seed = 0;
        while (k < hashCount) {

            // ハッシュ化
            byte[] digest;
            synchronized (digestFunction) {
                digestFunction.update(++seed);
                digest = digestFunction.digest(data);                
            }

            // 4Byte区切りでint化して配列に詰める
            for (int i = 0; i < digest.length/4 && k < hashCount; i++) {
                int h = 0;
                for (int j = (i*4); j < (i*4)+4; j++) {
                    h <<= 8;
                    h |= ((int) digest[j]) & 0xFF;
                }
                result[k] = h;
                k++;
            }
        }
        return result;
    }    

    /**
     * 要素の追加
     * @param element 
     */
    public void add(E element) {
       add(element.toString().getBytes(DEFAULT_CHARSET));
    }    

    /**
     * 要素の追加
     * @param bytes 
     */
    public void add(byte[] bytes) {
       int[] hashes = createHashes(bytes, countOfHashNumCreatePerOneElement);
       for (int hash : hashes) bitFilter.set(Math.abs(hash % bitFilterSize), true);
       numberOfAddedElements ++;
    }

    /**
     * 判定
     * @param element 要素
     * @return 
     */
    public boolean contains(E element) {
        return contains(element.toString().getBytes(DEFAULT_CHARSET));
    }

    /**
     * 判定
     * @param bytes 要素のバイト配列
     * @return 
     */
    public boolean contains(byte[] bytes) {
        int[] hashes = createHashes(bytes, countOfHashNumCreatePerOneElement);
        for (int hash : hashes) {
            if (!bitFilter.get(Math.abs(hash % bitFilterSize))) {
                return false;
            }
        }
        return true;
    }    

    /**
     * フィルタの取得
     * @return フィルタ
     */
    public BitSet getBitSet() {
        return bitFilter;
    }

    /**
     * 追加された項目数を取得
     * @return 項目数
     */
    public int getAddItemCount(){
        return this.numberOfAddedElements;
    }

    public double getFalsePositiveProbability() {
        // (1 - e^(-k * n / m)) ^ k
        return 
            Math.pow((1 - Math.exp(-countOfHashNumCreatePerOneElement * (double) this.numberOfAddedElements
                / (double) bitFilterSize)), countOfHashNumCreatePerOneElement);
    }    

}
呼び出しサンプル
import java.util.ArrayList;
import java.util.List;
import org.apache.commons.lang.RandomStringUtils;

/**
 * BloomFilterを試す
 * @author owl
 */
public class ExecBloomFilterSample {

    public static void main(String argv[]){
        MyBasicBloomFilter<String> bf = new MyBasicBloomFilter<>(1000000, MyBasicBloomFilter.FalsePositiveProbability.Low);

        List<String> addList = new ArrayList<>();           // BloomFilterに追加するデータ
        List<String> notAddList = new ArrayList<>();        // BloomFilterに追加しないデータ

        // 1万件のデータをBloomFilterに追加
        // 同時にBloomFilterに追加しない1万件の検証データも生成
        for(int i=0;i<2000000;i++){
            if(i % 2 == 0) {
                String s = RandomStringUtils.randomAlphabetic(24);
                bf.add(s);
                addList.add(s);
            } else {
                notAddList.add(RandomStringUtils.randomAlphabetic(24));
            }
        }

        // BloomFilterの状態を出力
        for(int i=0; i < bf.getBitSet().size(); i++ ){
            System.out.print(bf.getBitSet().get(i) ? "1" : "0");
            if(i>1000) break;
        }

        // BloomFilterのデータサイズと計算された偽陽性確率を出力
        System.out.println();
        System.out.println("データサイズ --> " + bf.getBitSet().size() + " | K-Byteバイト数" + (double)((double)(bf.getBitSet().size())/8/1024));
        System.out.println("偽陽性確率 --> " + String.format("%.5f", bf.getFalsePositiveProbability()));

        // BloomFilterに追加したデータが全て陽性判定されるか確認
        // (問題なければ何も表示されない)
        System.out.println();
        System.out.println("■■■■■ 追加データが全て陽性判定されるかチェックを開始 ■■■■■");
        addList
            .stream()
            .sequential()
            .filter(e -> !bf.contains(e))
            .forEach(e-> System.out.println("はずれ判定:" + e));

        // BloomFilterに追加していないデータが誤って陽性判定されたカウントを出力
        System.out.println("■■■■■ 非追加データが偽陽性判定されるかチェックを開始 ■■■■■");
        System.out.println("1000000データ中..." +
            notAddList
                .stream()
                .sequential()
                .filter(e -> bf.contains(e))
                .count() + "件の偽陽性を検出しました。");

    }

}
実行結果
000011100100001110011011100010101001100110111000100011001(省略)
データサイズ --> 14400000 | K-Byteバイト数1757.8125
偽陽性確率 --> 0.00099

■■■■■ 追加データが全て陽性判定されるかチェックを開始 ■■■■■
■■■■■ 非追加データが偽陽性判定されるかチェックを開始 ■■■■■
1000000データ中...994件の偽陽性を検出しました。