From: Dave Thomas <dave@...>
Date: 2003-05-27T12:16:04+09:00
Subject: Re: Binary Tree vs. Hash

Clifford Heath wrote:
> 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.

Actually, it's worse that that. According to 
http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html, for an m/n 
ratio of 6, the filter words best with 4 hashes, which gives an error 
rate of about 1/18, which is clearly silly. Next time I'll actually use 
the tables rather than try to wing it in my head :)

> 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.

Interestingly, the same tables suggest that for a 200k hash, m/n will be 
roughly 18, so k optimizes out at 12 or 13 hashes, for an error rate of 
0.000176, or 1/5681, which probably still isn't good enough for 
real-world use. It looks like about 300k is probably a good starting 
point. I'm off to try generate some real statistics just to confirm all 
this.


Cheers


Dave