I've never seen a Javascript Bloom filter implementation so I had to write one, and then had to port it to Perl and Ruby. You'll understand why soon if you don't already.

Quick aside: more than half of "my" bloomfilter.js is somebody else's BSD-licensed Javascript MD5 library but you could pretty easily replace it with some other hash library if you felt the compulsion.

I don't think this one would be practical for really large input sets (like a spell check dictionary built from /usr/dict/words), but I'm sure you'll think of something if you work at it. Get moving on that.

To get your brain in gear, here's a small demonstration.

First, I put the text of a really excellent Wire song (I won't say which), one word per line (minus punctuation) in a file. Then using the Ruby version I ran the file through this:

require 'bloomfilter'

bf = BloomFilter.new({ 'bits' => 0xff, 'salts' => %w(z A) })

STDIN.each_line { |l| l.chomp!; bf.add(l.downcase) }

print(b.to_json)

Or maybe I used the Perl one and ran it through this:

require 'bloomfilter.pl'; # what is this, 1994?

my $bf = BloomFilter->new({ bits => 0xff, salts => [qw(z A)] });

while(<>) { chomp; $bf->add(lc $_); }
print $bf->as_JSON();

Doesn't matter. Both give the same output (though I changed the formatting to make it a little easier to read):

{
 "buckets":[1509645767,990260715,1062483727,150062916,551224088,354022058,1818090233,1463314593,110],
 "bucketsize":31,
 "bits":255,
 "salts":["z","A"]
};

Type some Wire lyrics into the box below and smell the magic:

The filter check code runs 'onchange' for that text box. Just type (or paste in) some text, then click outside the box and you should get some feedback.

I encourage you to view the source of this page to see what's really going on but here's a quick example of the Javascript interface for the impatient:

// choose an appropriate number of bits and salts
// (don't ask me; you can figure it out)

var bf = new BloomFilter({ bits: 0xffff, salts: ['x','y','z','!'] });

bf.add('one');
bf.add('two');
bf.add('three');

bf.test('one'); // will definitely return true
bf.test('two'); // will definitely return true
bf.test('three'); // will definitely return true

bf.test('eins'); // will probably return false
bf.test('zwei'); // will probably return false
bf.test('drei'); // will probably return false

If you find bugs in this, please let me know. Also I'd really like to hear from anyone who finds other cool uses for this (aside from Wire lyric guessing games). And just to get this out of the way, I have no idea if this code can interoperate with the Bloom::Filter module on the CPAN but I should probably find out.