ブルームフィルタ：要素は集合に含まれているか

ブルームフィルタ（Bloom filter）は、ある要素 x が集合 M に含まれているかどうかを、ある程度の確率で答えられる確率的データ構造です。

例えば、あるシステムで、ユーザーが広告バナーをクリックした回数を測る必要があるとします。クリックのたびに HTTP GET リクエストが届き、ユーザー XYZ が広告123をクリックしたことが知らされます。ときどき、ユーザーがうっかりダブルクリックして、リクエストが2つ届くことがあります。このようなリクエストは取り除いて、データベースには1回のクリックとして記録したいところです。

そこで、クリックのメッセージの流れを読み込み、重複を取り除くアプリケーションが必要になります。どうすればよいでしょうか。どのメッセージにも ID があるので、メッセージ全体を比べる必要はなく、同じ ID のメッセージをすでに処理したかどうかを調べるだけで済みます。メッセージのストリーム（ここでは簡単のため配列）から重複を取り除く JavaScript の簡単なコードは、次のようになります。

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}]
var processedIds = {};

messages.forEach(function(message) {
    if (!processedIds[message.id]) {
        processedIds[message.id] = true;
        console.log(message);
    }
});

// 出力：{ id: "123" } { id: "456" } { id: "789" }

この方法は、メモリが足りなくなるまでは使えます。ただし、集合 processedIds は大きくなる一方なので、いつかはメモリが足りなくなります。もちろん、データの有効期限を設けることもできます。例えば、1時間より古いメッセージを毎回削除するといった方法です。

困るのは、それでも足りない場合です。集合 processedIds に少なくとも1日分のデータを入れておく必要があり、例えば1秒に1万件のメッセージを処理するとしたらどうでしょうか。最悪の場合、8億6,400万個もの ID を保存しなければなりません。uuid v4 を使うと、各 ID の長さは36文字なので、1日に少なくとも31GBを保存する必要があります。これは少し多すぎます。メモリの使用量を減らせないでしょうか。

ブルームフィルタ

ID 全体を保存する代わりに、そのハッシュ値だけを保存できます。定番の murmurhash が使えます。どの文字列に対しても32ビットの整数を返し、しかも値の分布も良好です。

var murmurhash = require("murmurhash");

var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var processedHashedIds = {};

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id);
    if (!processedHashedIds[hashedId]) {
        processedHashedIds[hashedId] = true;
        console.log(message);
    }
});

// 出力：{ id: "123" } { id: "456" } { id: "789" }

次に、ビット配列を使った工夫をします。ビット配列とは、0と1だけを保存する配列です。n ビットのハッシュ関数を使う場合、ハッシュ関数の出力としてありうるものすべてを配列の位置として指定できるように、大きさ 2ⁿ の配列が必要です。最初は、配列にはすべて0が入っています。ハッシュ関数が入力 "123" に対して47を返したら、配列の添字47の位置に1を入れるだけです。これで、値が47のハッシュ値をすでに見たという印になります。

var n = 8;
var numberOfValues = Math.pow(2, n);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];
var bitVector = new Array(numberOfValues);

messages.forEach(function(message) {
    var hashedId = murmurhash.v2(message.id) % numberOfValues;
    if (!bitVector[hashedId]) {
        bitVector[hashedId] = true;
        console.log(message);
    }
});

// 出力：{ id: "123" } { id: "456" } { id: "789" }

コード % numberOfValues は、murmurhash を切り詰めて n ビットのハッシュ関数にしているだけです。これがブルームフィルタです。ただし、かなり単純化した版です。この方法の問題は、当然ながら、必ず起こる衝突です。異なる入力値が同じハッシュ値をもつことがあります。そこで、衝突が起こる確率を下げるために、ハッシュ関数を1つだけでなく、複数使います。複数のハッシュ関数は、例えば入力値にソルトを加えることでつくれます。異なる n ビットのハッシュ関数をつくる簡単な関数は、次のようになります。

var murmurhash = require("murmurhash");

function createNBitHashFunction(n, salt) {
    var upperBound = Math.pow(2, n);
    return function(inputString) {
        return murmurhash.v2(inputString + salt) % upperBound;
    }
}

var firstHashFunction = createNBitHashFunction(8, "someSalt");
var secondHashFunction = createNBitHashFunction(8, "someOtherSalt");

console.log(firstHashFunction("123")); // 42
console.log(secondHashFunction("123")); // 174

ブルームフィルタを表すクラスは、次のように書けます。

function BloomFilter(numberOfHashFunctions, numberOfBits) {
    this.reset(numberOfHashFunctions, numberOfBits);
}

BloomFilter.prototype.reset = function(numberOfHashFunctions, numberOfBits) {
    this.bitVector = new Array(Math.pow(2, numberOfBits));
    this.hashFunctions = [];

    for (var i = 0; i < numberOfHashFunctions; i++) {
        this.hashFunctions.push(createNBitHashFunction(numberOfBits, i.toString()));
    }
}

BloomFilter.prototype.add = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        this.bitVector[checksum] = true;
    }
}

BloomFilter.prototype.contains = function(item) {
    var checksum;
    for (var i = 0; i < this.hashFunctions.length; i++) {
        checksum = this.hashFunctions[i](item);
        if (!this.bitVector[checksum]) {
            return false;
        }
    }
    return true;
}

メソッド add は、ブルームフィルタに要素を追加します。すべてのハッシュ関数でハッシュ値を計算し、対応する添字の位置に true を保存します。
メソッド contains は、与えられた要素がブルームフィルタに含まれているかどうかを調べます。

ブルームフィルタは簡単に使えます。

var bloomFilter = new BloomFilter(3, 8);
var messages = [{id: "123"}, {id:"456"}, {id:"123"}, {id: "789"}];

messages.forEach(function(message) {
    if (!bloomFilter.contains(message.id)) {
        bloomFilter.add(message.id);
        console.log(message);
    }
});

// 出力：{ id: "123" } { id: "456" } { id: "789" }

基本的なブルームフィルタのしくみはこれだけです。主な性質は次のとおりです。

メソッド contains が、要素はブルームフィルタに含まれていないと答えたら、その要素は本当に一度も追加されていません。
メソッドが、要素はブルームフィルタに含まれていると答えても、その要素が本当に追加されたとは限りません。ハッシュ関数の衝突が起こった可能性があるからです（偽陽性）。
一般に、誤った答えが出る確率を下げたいときは、ハッシュ関数の個数を増やすか、ハッシュ関数の大きさ（出力の値の大きさ）を大きくします。
使うハッシュ関数が多いほど、ブルームフィルタは遅くなります。
使うハッシュ関数が大きいほど、ブルームフィルタが使うメモリは多くなります。
一度ブルームフィルタに追加した要素は、削除できません。

« 前へ: HyperLogLog：異なる値の個数を高い精度で推定する方法

次へ: シーザー暗号 »