From: Brian Candler <B.Candler@...>
Date: 2003-05-27T17:20:40+09:00
Subject: Re: Binary Tree vs. Hash

On Tue, May 27, 2003 at 12:16:04PM +0900, Dave Thomas wrote:
> 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.

That's not very good though; I mean, just encoding each letter using 5 bits,
I reckon a 90,000 word dictionary might take under 600K [*]. And then you
have none of that "dangerous messing around with improbabilities" (as I
think Douglas Adams wrote). Admittedly it wouldn't be quick to search though.

Regards,

Brian.

[*]
$ wc /usr/share/dict/words 
  235881  235881 2493066 /usr/share/dict/words

So I'm guessing a 90,000 word dictionary would have
  90000/235881 * 2493066 bytes
Encoding each character and newline as a 5-bit pattern gives 5/8ths of that,
or 594516 bytes, or about 580K.