Way to store a large dictionary with low memory footprint + fast lookups (on Android)

Question

I'm developing an android word game app that needs a large (~250,000 word dictionary) available. I need:

• reasonably fast look ups e.g. constant time preferable, need to do maybe 200 lookups a second on occasion to solve a word puzzle and maybe 20 lookups within 0.2 second more often to check words the user just spelled.

EDIT: Lookups are typically asking "Is in the dictionary?". I'd like to support up to two wildcards in the word as well, but this is easy enough by just generating all possible letters the wildcards could have been and checking the generated words (i.e. 26 * 26 lookups for a word with two wildcards).

• as it's a mobile app, using as little memory as possible and requiring only a small initial download for the dictionary data is top priority.

My first naive attempts used Java's HashMap class, which caused an out of memory exception. I've looked into using the SQL lite databases available on android, but this seems like overkill.

What's a good way to do what I need?

Answer 1

You'll be wanting some sort of trie. Perhaps a ternary search trie would be good I think. They give very fast look-up and low memory usage. This paper gives some more info about TSTs. It also talks about sorting so not all of it will apply. This article might be a little more applicable. As the article says, TSTs

combine the time efficiency of digital tries with the space efficiency of binary search trees.

As this table shows, the look-up times are very comparable to using a hash table.

Answer 2

First of all, you need to figure out WHAT questions you need to ask your data structure. Is it a "is this spelling correct, yes/no?" or "which words COULD this incorrect word have been if the user typed it correctly?"

The second structure will require much more than the first, either in term of memory or cpu.

Answer 3

I am assuming that you want to check if given word belongs to dictionary.

Have a look at bloom filter.

The bloom filter can do "does X belong to predefined set" type of queries with very small storage requirements. If the answer to query is yes, it has small (and adjustable) probability to be wrong, if the answer to query is no, then the answer guaranteed to be correct.

According the Wikipedia article you could need less than 4 MB space for your dictionary of 250 000 words with 1% error probability.

The bloom filter will correctly answer "is in dictionary" if the word actually is contained in dictionary. If dictionary does not have the word, the bloom filter may falsely give answer "is in dictionary" with some small probability.

Answer 4

You can achieve your goals with more lowly approaches also... if it's a word game then I suspect you are handling 27 letters alphabet. So suppose an alphabet of not more than 32 letters, i.e. 5 bits per letter. You can cram then 12 letters (12 x 5 = 60 bits) into a single Java long by using 5 bits/letter trivial encoding.

This means that actually if you don't have longer words than 12 letters / word you can just represent your dictionary as a set of Java longs. If you have 250,000 words a trivial presentation of this set as a single, sorted array of longs should take 250,000 words x 8 bytes / word = 2,000,000 ~ 2MB memory. Lookup is then by binary search, which should be very fast given the small size of the data set (less than 20 comparisons as 2^20 takes you to above one million).

IF you have longer words than 12 letters, then I would store the >12 letters words in another array where 1 word would be represented by 2 concatenated Java longs in an obvious manner.

NOTE: the reason why this works and is likely more space-efficient than a trie and at least very simple to implement is that the dictionary is constant... search trees are good if you need to modify the data set, but if the data set is constant, you can often run a way with simple binary search.

Answer 5

You could also use the Android NDK and do the structure in C or C++.

Answer 6

A very efficient way to store a directory is a Directed Acyclic Word Graph (DAWG).

Here are some links:

• Directed Acyclic Word Graph or DAWG description with sourcecode
• Construction of the CDAWG for a Trie
• Implementation of directed acyclic word graph

Answer 7

The devices that I worked basically worked from a binary compressed file, with a topology that resembled the structure of a binary tree. At the leafs, you would have the Huffmann compressed text. Finding a node would involve having to skip to various locations of the file, and then only load the portion of the data really needed.