Imagine a spell checker that must decide, thousands of times a second, whether a word is in a huge dictionary. Keeping the dictionary in memory takes a lot of space. Looking each word up on disk is slow. Burton Bloom's 1970 paper offers a middle path: a tiny structure that answers "definitely not here" or "probably here" in a fraction of the space.
His own example is automatic hyphenation. Simple rules can hyphenate about 90 percent of English words. The remaining words need a dictionary on disk. If you could quickly rule out most words that are not in the exception list, you would rarely touch the disk. The structure he describes is now called a Bloom filter.
A Bloom filter is a row of bits plus a few hash functions. It can say a thing is definitely not in a set, or probably in it. It never forgets something you added, but it sometimes claims to have seen something it has not. In exchange it uses very little memory.
Adding and checking
Start with m bits, all zero. Pick k different hash functions. To add a word, run it through each hash function. Each gives a position, and you set those k bits to 1. That is all. The word is not stored.
To check a word, compute its k positions the same way and look at those bits.
- If any bit is 0, the word was never added. Had it been, that bit would be 1. This answer is always right.
- If all bits are 1, the word was probably added. But other words may have set those same bits by coincidence. That is a false positive.
