Kata Five - Bloom Filters

There are many circumstances where we need to find out if something is a member of a set, and many algorithms for doing it. If the set is small, you can use bitmaps. When they get larger, hashes are a useful technique. But when the sets get big, we start bumping in to limitations. Holding 250,000 words in memory for a spell checker might be too big an overhead if your target environment is a PDA or cell phone. Keeping a list of web-pages visited might be extravagant when you get up to tens of millions of pages. Fortunately, there’s a technique that can help.

Bloom filters are a 30-year-old statistical way of testing for membership in a set. They greatly reduce the amount of storage you need to represent the set, but at a price: they’ll sometimes report that something is in the set when it isn’t (but it’ll never do the opposite; if the filter says that the set doesn’t contain your object, you know that it doesn’t). And the nice thing is you can control the accuracy; the more memory you’re prepared to give the algorithm, the fewer false positives you get. I once wrote a spell checker for a PDP-11 which stored a dictionary of 80,000 words in 16kbytes, and I very rarely saw it let though an incorrect word. (Update: I must have mis-remembered these figures, because they are not in line with the theory. Unfortunately, I can no longer read the 8" floppies holding the source, so I can’t get the correct numbers. Let’s just say that I got a decent sized dictionary, along with the spell checker, all in under 64k.)

Bloom filters are very simple. Take a big array of bits, initially all zero. Then take the things you want to look up (in our case we’ll use a dictionary of words). Produce ‘n’ independent hash values for each word. Each hash is a number which is used to set the corresponding bit in the array of bits. Sometimes there’ll be clashes, where the bit will already be set from some other word. This doesn’t matter.

To check to see of a new word is already in the dictionary, perform the same hashes on it that you used to load the bitmap. Then check to see if each of the bits corresponding to these hash values is set. If any bit is not set, then you never loaded that word in, and you can reject it.

The Bloom filter reports a false positive when a set of hashes for a word all end up corresponding to bits that were set previously by other words. In practice this doesn’t happen too often as long as the bitmap isn’t too heavily loaded with one-bits (clearly if every bit is one, then it’ll give a false positive on every lookup). There’s a discussion of the math in Bloom filters at www.cs.wisc.edu/~cao/papers/summary-cache/node8.html.

So, this kata is fairly straightforward. Implement a Bloom filter based spell checker. You’ll need some kind of bitmap, some hash functions, and a simple way of reading in the dictionary and then the words to check. For the hash function, remember that you can always use something that generates a fairly long hash (such as MD5) and then take your smaller hash values by extracting sequences of bits from the result. On a Unix box you can find a list of words in /usr/dict/words (or possibly in /usr/share/dict/words). For others, I’ve put a word list up at pragprog.com/katadata/wordlist.txt.

Play with using different numbers of hashes, and with different bitmap sizes.

Part two of the exercise is optional. Try generating random 5-character words and feeding them in to your spell checker. For each word that it says it OK, look it up in the original dictionary. See how many false positives you get.

Comments

[szeryf]

And the number of bits in the comment above is the number of bits per hash function, so the length of bit vector was 2^(number of bits) and it needed 2^(number of bits - 3) bytes. So for the 19 bits it needs 64kB of memory.

[szeryf]

Here's my solution in Java: http://gist.github.com/557075

What I noticed (and thought it was strange at first) that the number of bits must be at least a couple of time bigger than the number of words in the dictionary. Otherwise the Bloom Filter's bit vector will be almost completely filled and there will be many false positives. There is also no point in increasing the hash functions number for small bit vector as this will also make it even more filled.

My results for 3 hash functions:

16 bits - 88% filled - 56% of false positives
17 bits - 65% filled - 20% of false positives
18 bits - 40% filled - 4% of false positives
19 bits - 23% filled - 1% of false positives

And the best hash functions I found is fragments of MD5 hash for the string.

[travesti]

This was an interesting puzzle for me, as I've not heard of Bloom filters before - it's an interesting technique to have up your sleeve. Keep up the good work!

[Joshua Hollander]

Here is my Scala solution: http://the-real-jho.blogspot.com/2010/06/code-kata-5.html

[Jerome Baum]

@Matt: That wouldn't work. Since there are an infinite amount of such words, you'll end up with a full bitmap (of 1s) which will report every word as "not in the dictionary" -- then you'll have the positive filter reporting "it's in there" and the negative one reporting "it's not."

[Stephen Doyle]

Here is my solution in Ruby ... http://softwareramblings.com/2009/11/codekata-kata-five-solution.html

[Matt Powell]

See, this is fantastic! All you have to do is generate a bitset for all the words that *aren't* in the target language, and your spell-checker is perfect!

[Edward S. Marshall]

The new URL for the word list appears to be archive.org, since it looks like the list is no longer online:

http://web.archive.org/web/20070704025714/http://pragmaticprogrammer.com/katadata/wordlist.txt

[Michael Davies]

Sorry, that should have read (1-e^(-kn/m))^k of course.

[Michael Davies]

There's a small error in the linked summary - the probability of a false positive should be approximated to (1-e^(-kn/m)) rather than (1-e^(kn/m)) as it states.

This was an interesting puzzle for me, as I've not heard of Bloom filters before - it's an interesting technique to have up your sleeve. Keep up the good work!

[Matthew Ueckerman]

Word list URL should read http://pragmaticprogrammer.com/katadata/wordlist.txt