この記事はJava Advent Calendar 2013 18日目の記事です。昨日はHiroyuki OhnakaさんのSingletonをモックするでした。
BloomFilterとは？
BloomFilterとはデータ構造の一種で、Setみたいなもので集合を扱います。
BloomFilterはSetのように、対象のデータが集合に含まれるかどうかを検証できますが、検証結果は
- たぶん集合に含まれる
- 絶対に集合に含まれない
の2パターンです。「たぶん集合に含まれる」という結果がでても、たまに誤ります。これを偽陽性(False Postive)と言います。
一見、 えっと思うかもしれませんが、この偽陽性を持つことにより、空間効率が飛躍的に向上します。つまり、データ集合を表現するために必要なメモリがSetに比べて大幅に少ないのです。
原理を説明しようとおもったけど、このSlideshareが分かりやすかったので、埋め込んでおきます。
詳しい話はWikipediaとか見てください。
JavaでBloomFilterを使う
次にBloomFilterをJavaから使ってみましょう。アルゴリズム自体はそんなにむずかしくないので、自分で実装してみるのも勉強になりますが、ここではGoogle Guavaに含まれているcom.google.common.hash.BloomFilterクラスを使います。
使い方は
int expectedInsertions = 100;
BloomFilter<String> bloomFilter = BloomFilter.create(new Funnel<String>() {
@Override
public void funnel(String from, PrimitiveSink into) {
into.putString(from, StandardCharsets.UTF_8);
}
}, expectedInsertions);
といった感じです。BloomFilter.createの第一引数にはcom.google.common.hash.Funnel実装を渡します。Funnelは対象のデータをPrimitiveSinkに流します。PrimitiveSinkはハッシュ値を計算するために使用され、データのプリミティブな値を受けます(StringもOK）。最後に補足しますが、このFunnelの書き方は良くないです。
Funnel(漏斗)でデータをSink(流し台)に流し込むイメージです。この例では単純にStringを溜めこむので、Stringをそのままシンクに流します。
第二引数にはデータサイズを予想値を指定します。扱う集合のサイズにできるだけ近い値が望ましいです。第三引数で「たぶん集合に含まれる」の結果が間違える確率を指定できます。デフォルトでは0.03が指定されており、97%の確率で対象のデータが「たぶん集合に含まれ」ることになります。このサイズの予想値(n)と誤認識の確率(p)でBloomFilterが持つビットセットのサイズ(m)が決まります。計算式はwikipediaに載っていますが、javadocに式展開まで書かれています。
/*
* Cheat sheet:
*
* m: total bits
* n: expected insertions
* b: m/n, bits per insertion
* p: expected false positive probability
*
* 1) Optimal k = b * ln2
* 2) p = (1 - e ^ (-kn/m))^k
* 3) For optimal k: p = 2 ^ (-k) ~= 0.6185^b
* 4) For optimal k: m = -nlnp / ((ln2) ^ 2)
*/
実際に使ってみるコード例を挙げます。
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnel;
import com.google.common.hash.PrimitiveSink;
import java.nio.charset.StandardCharsets;
public class Main {
public static void main(String[] args) {
int number = 1000;
BloomFilter<String> bloomFilter = BloomFilter.create(new Funnel<String>() {
@Override
public void funnel(String from, PrimitiveSink into) {
into.putString(from, StandardCharsets.UTF_8);
}
}, number);
for (int i = 0; i < number; i++) {
bloomFilter.put(String.format("%09d", i));
}
int loopCount = 2000;
int misCount = 0;
for (int i = 0; i < loopCount; i++) {
String s = String.format("%09d", i);
if (bloomFilter.mightContain(s) && (i >= number)) {
misCount++;
}
}
System.out.println("mis = " + misCount + " (" + (misCount * 100.0 / (loopCount - number)) + "%)");
}
}
100件データをputメソッドで投入して、「たぶん集合に含まれる」ことをmightContainメソッドで確認します。そして誤認確率を表示します。
実行結果
mis = 26 (2.6%)
でした。含まれていないデータを1000個ためして、26回誤認識しました。約3%と計算通りです。
確率を変えてみましょう。
BloomFilter<String> bloomFilter = BloomFilter.create(new Funnel<String>() {
@Override
public void funnel(String from, PrimitiveSink into) {
into.putString(from, StandardCharsets.UTF_8);
}
}, number, 0.005);
今度は誤認識率を0.5%にして実行します。
mis = 2 (0.2%)
分母が小さいので少しぶれていますが、約0.5%に減りました。確率をコントロールできることがわかりますね。
HashSetとデータサイズを比較する
単純ですが、Stringを500万件投入した後のデータサイズを比較してみます。
HashSet版
以下のコードを実行します。
import com.google.common.base.Stopwatch;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnel;
import com.google.common.hash.PrimitiveSink;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.nio.charset.StandardCharsets;
import java.text.MessageFormat;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.TimeUnit;
public class MainWithHashSet {
public static void main(String[] args) {
execute();
}
private static void execute() {
int number = 5000000;
Set<String> set = new HashSet<>(number);
Stopwatch stopwatch = Stopwatch.createStarted();
for (int i = 0; i < number; i++) {
set.add(String.format("%09d", i));
}
System.out.println(stopwatch.elapsed(TimeUnit.SECONDS) + " sec");
System.out.println(MessageFormat.format("{0} byte", calcObjectSize(set)));
}
private static long calcObjectSize(Object object) {
try (ByteArrayOutputStream baos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(baos);
) {
oos.writeObject(object);
return baos.toByteArray().length;
} catch (IOException e) {
e.printStackTrace();
}
return 0;
}
}
出力結果
20 sec
60,000,053 byte
mis = 0 (-0.0%)
約60MB消費しています。
BloomFilter版
import com.google.common.base.Stopwatch;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnel;
import com.google.common.hash.PrimitiveSink;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.nio.charset.StandardCharsets;
import java.text.MessageFormat;
import java.util.concurrent.TimeUnit;
public class MainWithBloomFilter {
public static void main(String[] args) {
execute();
}
private static void execute() {
int number = 1000;
BloomFilter<String> bloomFilter = BloomFilter.create(new Funnel<String>() {
@Override
public void funnel(String from, PrimitiveSink into) {
into.putString(from, StandardCharsets.UTF_8);
}
}, number, 0.005);
Stopwatch stopwatch = Stopwatch.createStarted();
for (int i = 0; i < number; i++) {
bloomFilter.put(String.format("%09d", i));
}
System.out.println(stopwatch.elapsed(TimeUnit.SECONDS) + " sec");
System.out.println(MessageFormat.format("{0} byte", calcObjectSize(bloomFilter)));
int loopCount = 2000;
int misCount = 0;
for (int i = 0; i < loopCount; i++) {
String s = String.format("%09d", i);
if (bloomFilter.mightContain(s) && (i >= number)) {
misCount++;
}
}
System.out.println("mis = " + misCount + " (" + (misCount * 100.0 / (loopCount - number)) + "%)");
}
private static long calcObjectSize(Object object) {
try (ByteArrayOutputStream baos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(baos);
) {
oos.writeObject(object);
return baos.toByteArray().length;
} catch (IOException e) {
e.printStackTrace();
}
return 0;
}
}
出力結果
11 sec
4,561,902 byte
mis = 149390 (2.9878%)
約3%の誤認識を許すことで、データサイズが4MBになりました。
確率を変えてみます。
p=0.001
12 sec
8,986,374 byte
mis = 5006 (0.10012%)
p=0.0001
14 sec
11,981,702 byte
mis = 485 (0.0097%)
p=0.0001
14 sec
14,977,030 byte
mis = 42 (8.4E-4%)
計算上、ビットセットのサイズ(m)を増やすと誤認識率は指数関数的に下がります。
この辺は用途次第での調整になるでしょう。
次にp=0.03のまま、集合データ数を変えてみます。HashSetはGCの影響で遅すぎたので計測していません。誤認識率のチェックも省略します。
n=10000000
24 sec
9,123,430 byte
n=100000000
250 sec
91,230,886 byte
計算式見てもわかりますが、pが固定であればmはnに比例しますね。
3%の誤認識を許せば日本人全員分のStringは100MBくらいで格納できそうですね。
どこで使う？
以下の用途が考えられます
- 大量のデータの中に対象が含まれているか確認したいけど、間違っていても問題ない(他の方法で確認できる)
- 大量のデータの中に対象が含まれていないことだけを確認したい
具体的には以下で実際に使用されています(Wikipedia調べ)。
- Squidのキャッシュ判定
- BigTableやCassandraのキーの検出
- Chromeの悪意のあるURLのチェック
話題のBitcoinでも使用されていますね。
この「Bloom filter の気持ち」を読むとありがたみもわかってきます。
業務処理ばっかり書いていると、こういう用途でも愚直にHashSetに溜め込み、OutOfMemoryを招いたりします。データ構造やアルゴリズムをちゃんと勉強して、より良い選択肢を用意しておくことはプログラマとしてとても重要ですね。
(補足) Funnelの作り方
上記の例では説明を単純化するため、Stringを扱い、また匿名クラスでFunnelを作成しました。
実際のところはJavaBeanが対象になるでしょうし、FunnelはSerializableなSingletonにすべきです。BloomFilterはaddAllで混合することが可能ですが、Funnnelオブジェクトが等価である必要があります。
Javadocでは以下のようにEnumを使ったSingletonパターンを推奨しています。Effective Javaの項目3にありましたね。
public enum BookFunnel implements Funnel<Book> {
//This is the single enum value
FUNNEL;
public void funnel(Book from, PrimitiveSink into) {
into.putString(from.getIsbn(), StandardCharsets.UTF_8)
.putDouble(from.getPrice());
}
}
こう使いましょう。
BloomFilter<Book> bloomFilter = BloomFilter.create(BookFunnel.FUNNEL, 5000000);