ブルームフィルタ

お花フィルタ？ではなく、ブルームという人が発明したアルゴリズムらしい。

ブルームフィルタ（bloom filter）とは

  • ある要素が集合に含まれているかどうか高速に判定できる
  • 空間効率がいい

ただし

  • 要素そのものを保持してるわけではないので、要素は別に保存する必要あり
  • 偽陽性（ないのにあると誤判定）が発生する
    • ただし偽陰性（あるのにないと誤判定）は発生しない。つまり、ないと判定されたものは確実にない

というもの。

例えば、あるネトゲにキリトという名前のユーザがいるかどうか調べたいという場合、あらかじめブルームフィルタに全ユーザ名を突っ込んでおけば、高速に判定できるってワケ。

ただ、偽陽性が発生するので既にキリトという名前のユーザが他にいなければ登録可能とする、みたいな用途に使えない。本当はキリトいないのにいると誤判定されて、登録できなくなる可能性があるためだ。

では、どういう時に使うかというと、検索回数を減らしたい場合。アスナがいると判定された時だけアスナのデータをDBから取得する、みたいに使ってクエリを減らすのだ。偽陽性の場合、問い合わせの結果が空になるが、いないと判定された時の処理を実行すれば良いだけなので問題ない。

ただこのケースではインデックスが使えるので負荷や速度はあまり問題にはならない。負荷よりも実行回数で課金されるAPIの無駄撃ちを減らしてお金を節約したいという意図で用いられる事が多いようだ。

それでは実装してみる。アルゴリズムの詳細はWikipediaでも見てください。本気で使うなら何か良い感じのライブラリを探しましょう。

用意するもの

コードはNode.jsです。

  • 長さmのビット配列
    • タダの配列で代用
  • k個のハッシュ関数（生成されるハッシュ値は0以上、m未満の整数になるようにする）
    • md5の先頭から1バイトずつ取り出し、複数のハッシュ関数の結果とみなす
    • なので今回はmは256未満、kは16以下という制限付き
// bloomfilter.js
'use strict';
const crypto = require('crypto');

class BloomFilter {
    constructor(k, m) {
        this.k = k;
        this.m = m;
        this.bits = new Array(m).fill(0);
    }

    hash(data) {
        const buf = Buffer.from(data, 'utf8');
        const hash = crypto.createHash('md5').update(buf).digest();
        return Array.from(hash.slice(0, this.k)).map(e => e % this.m);
    }

    add(data) {
        this.hash(data).forEach((e) => this.bits[e] = 1);
    }

    has(data) {
        return this.hash(data).every((e) => this.bits[e] === 1);
    }
}

exports.BloomFilter = BloomFilter;

// index.js
'use strict';
const k = 4;
const m = 256;

const bf = new (require('./bloomfilter').BloomFilter)(k, m);
const st = new Set();

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin
});

rl.on('line', (line) => {
    line.replace(/[^a-zA-Z0-9 ]/g, '').split(' ').map(word => word.trim()).forEach((word) => {
        bf.add(word);
        st.add(word);
    });
});

const tests = process.argv.slice(2);
rl.on('close', () => {
    for (const test of tests) {
        if (bf.has(test)) {
            console.log(`${test} ある`, !st.has(test) ? '(偽陽性)': '');
        } else {
            console.log(`${test} ない`);
        }
    }
});

ブルームフィルタに突っ込む単語をファイルに保存。Wikipedia英語版のBloomFilterの1段落目です

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not –in other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with a "counting" filter); the more elements that are added to the set, the larger the probability of false positives.'

実行。標準入力がブルームフィルタに登録する単語、引数が存在チェックする単語

$ <words.txt node index.js hoge fuga data nyan this true false right left
hoge ない
fuga ない
data ある
nyan ない
this ある
true ない
false ある
right ある (偽陽性)
left ない

rightなんて単語は含まれていないのにあると判定された。これが偽陽性というヤツですな。