I've done quite a bit of work with dictionaries going as far back as 8-bit machines with tight memory constraints. Bear with me here as it will get interesting

I've done quite a bit of work with dictionaries going as far back as 8-bit machines with tight memory constraints. Bear with me here as it will get interesting. A Bloom filter is a great data structure but probably not the best choice for this problem. It's not as memory efficient as you think. Here's why: Think of a Bloom filter as a collection of hash values where each individual hash value is expanded by 44%. The cost of maintaining the same false positive rate of an explicit log2(n) hash is to use 1.44log2(n) bits (see http://en.wikipedia.org/wiki/Bloom_filter http://en.wikipedia.org/wiki/Bloom_filter for more detail.) So, if you want a false positive rate of 1 in 64k you could store a 16-bit hash in an array or a 23-bit hash in a Bloom filter. That's a significant tax to pay when memory is tight. In this case it's better to keep a bit array of explicit hashes than to use a Bloom filter. An array of hashes gives you some options to make it smaller: 1. Sort the array by hash value and store only the differences using a delta coding scheme. The downside is you have to search the entire array (or maintain some indexes into it) to look up a single word. 2. Break the array up into sub-arrays where each sub-array is chosen so the first N bits of the hash are the same (and discarded.) Each sub-array uses a smaller hash value and can still be binary searched. Of course, strip prefixes and suffixes from the words so the number of hashes that must be stored is reduced. 1.5 bytes per word is easy and with some work you can approach one byte per word with a low error rate. If you're allowed to do off-line preprocessing on the word list you can do better. Look up the history of Doug McIlroy's Unix spell checker. He got 75,000 words to fit in about 52k (going from memory here and my copy of Bentley's "Programming Pearls" is at home.) McIlroy traded away random access and had a fairly high error rate to get that much compression. Essentially, what he did was to create a large 1-bit Bloom filter and delta-encoded the differences between set bits (similar to option #1 above.) If you want to maintain fast random access for individual words you can do this with a Directed Acyclic Word Graph (DAWG). A simple DAWG with fixed node sizes and no stemming of any kind will get two bytes per word on English. Add variable node sizes, stemming and a few other tricks and you can have fast lookup with a near-zero error rate at a cost of about one byte per word.