From: Clifford Heath <cjh_nospam@...>
Date: 2003-05-27T09:43:28+09:00
Subject: Re: Binary Tree vs. Hash

Dave Thomas wrote:
> ...you should look at using a Bloom filter. You could pack a 90,000
> word dictionary into 64kb.

As long as you don't mind missing 1 in 64-ish spelling errors.

A Bloom filter reaches optimal performance when there an equal
number of odd and even bits set (each probe into the bitmap
therefore yields maximum selectivity) 64Kb is 524288 bits,
which means you must use around six hash values from each word
in your 90,000 word dictionary. That yields false hit
performance of 1:64, which IMO is insufficient for a useful
spell checker.

I mentioned this not to criticise, but to show folk how to
choose the best number of hash probes for a Bloom filter of
a given size, and how to predict the false hit rate.

I learnt this stuff by experiment while building a spell-checker.
I used 16-18 probes for each word, yielding a false hit rate of
1 in 65000+. For that performance, your 90,000 word dictionary
needs a filter of 200Kb+, not 64Kb.

Clifford.