無料で読めるデータマイニングの教科書「Mining of Massive Datasets」[2011-03-31-3]を読んでて気になった Bloom Filter（ブルームフィルタ）。

西尾さんが動作確認スクリプトを Python で実装していました。
- Bloom filterのシンプルな実装 (西尾泰和のはてなダイアリー)
http://d.hatena.ne.jp/nishiohirokazu/20080213/1202912207

西尾さんによる分かりやすくて素晴らしすぎる解説を引用。

Bloom filterは指定されたものがリストに含まれるならばTrue、含まれないならばFalseを返すようなデータ構造である。もちろん、単純にリストを保持するだけでもリストに含まれるかどうかの判定は可能だが、Bloom filterのメリットはオリジナルのリストを保存しておく必要がないという点にある。そのためメモリの消費量を格段に節約することができる。しかし、そのメモリ効率の代償として多少正確性が失われる。Bloom filterは指定されたものがリストにない場合でもたまにTrueを返すのだ。しかし、間違ってTrueを返す確率はあらかじめ計算することができるので、誤差が許容できる範囲であれば問題なく使うことができる。

ということで、「Bloom Filterのシンプルな実装」を Pure Perl で書きなおしてみました。ビットアレイの扱いは Perl の方が効率的かと(ref. [2011-04-02-4])。

■コード(bf.pl)：

#!/usr/bin/perl
use strict;
use warnings;

my $size = 1987;
my $bitarray = "";

sub hashes {
    my ($str) = @_;
    my @xs = (0, 0, 0);
    for my $c (split(//, $str)) {
        my $o = ord($c);
        $xs[0] = ($xs[0] * 137 + $o) % $size;
        $xs[1] = ($xs[1] * 69 + $o) % $size;
        $xs[2] = ($xs[2] * 545 + $o) % $size;
    }
    return @xs;
}

sub add {
    my ($str) = @_;
    for my $x (hashes($str)) {
        vec($bitarray, $x, 1) = 1;
    }
}

sub query {
    my ($str) = @_;
    for my $x (hashes($str)) {
        return 0 unless vec($bitarray, $x, 1);
    }
    return 1;
}

while (<>) {
    chomp;
    my ($c, $k) = /^([aq]) (.+?)$/;
    if ($c eq "a") {
	add($k);
    } elsif ($c eq "q") {
	print query($k), "\n";
    }
}

■実行例：

% cat a.txt
a hoge
q hoge
q hoga
a foo
a bar
a baz
q hoga
q foo
% ./bf.pl a.txt
1
0
0
1