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?

  • Can't you use the dictionary built in to Android? – Nick Johnson Feb 16 '10 at 22:52
  • I thought about this but you really need to use e.g. the official scrabble dictionary or the word game nuts go crazy. – BobbyJim Feb 16 '10 at 23:26

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.

  • Wow, cool idea. I will look into this. I wonder what the memory difference is between this and e.g. a trie. I've found lots of free well tested trie implementations I could use but this idea seems more specialized I imagine. I suppose all I need to do is write the "convert string to long" function and use a basic collections class, which shouldn't be too error prone really. To store the dictionary, all I need to do is store the file of longs and then insert them into the search tree on load. I could save and load the actual tree, but then the file will be bigger. – BobbyJim Feb 16 '10 at 22:37
  • You don't need to insert anything in a search tree... you just load the array in memory, and do the binary search in the array. No tree. Only one array. No collection class. No ANYTHING but the array of longs!!! – Antti Huima Feb 16 '10 at 22:41
  • BTW if you use tries you end up allocation lots of heap objects, which then strains the Java garbage collector. The single array of longs is only 1 object for the garbage collector and it doesn't contain pointers so the stress to the collector is minimal. – Antti Huima Feb 16 '10 at 22:43
  • 1
    @BobbyJim, you WILL need unit tests for your dictionary code. Try using Test Driven Design for this - just write the unit tests first and after each test write enough library code to make the tests pass - you will most likely find then that when you are done you do not need a library as the code will be simple enough to not warrant one. – Thorbjørn Ravn Andersen Feb 17 '10 at 6:15
  • 1
    @BobbyJim: JDK has java.util.Arrays.sort() and java.util.Arrays.binarySearch() methods that'll be helpful. – Juha Syrjälä Feb 17 '10 at 6:27

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.

  • Looks interesting. It's a word game though, so I need 100% sure positive answers for if the word is in the dictionary or the user is going to get annoyed! – BobbyJim Feb 16 '10 at 22:24
  • Bloom filter may give false positives. Is it a problem if your game sometimes accepts a word that is not in dictionary? – Juha Syrjälä Feb 16 '10 at 22:36
  • Ah, it's "False positives are possible, but false negatives are not". I suppose 95% of the time, the user is going to submit actual words. It depends on how often a false word gets through though as you don't want to make that into part of the gameplay strategy (could be a funny game though where you try to sneak by non-words that look like real words)! – BobbyJim Feb 16 '10 at 22:39
  • You can adjust the false positive rate by changing size of bloom filter's bit array. Larger bit arrays have smaller false negative probability. – Juha Syrjälä Feb 16 '10 at 22:44
  • 1
    I was reading some more and the false positives probability is in the order of magnitude of 1 in 1 000 000 and usually higher for typical bloom filters. In other words, massively unlikely to be a problem. Thanks. – BobbyJim Feb 16 '10 at 22:51

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

Here are some links:


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


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

  • My post original had a comment about tries taking a lot of memory but I deleted it because I wasn't so sure. I'm still not sure after reading your links. From the wiki: "A trie is optimized for speed at the expense of size." and "Ternary search trees are usually rejected in modern practice in favor of hash tables. Also, there are other ways to construct a trie. For example, a radix tree trie in which each node stores a bit string, and has two children for the possible next bits, may be more compact than a ternary search tree without being slow." – BobbyJim Feb 16 '10 at 22:15
  • I found an interesting looking apache license trie implementation for Java: code.google.com/p/patricia-trie/wiki/Examples – BobbyJim Feb 16 '10 at 22:23
  • Yes, I'm not sure if they will necessarily be much better space-wise, but there are ways to reduce this such as collapsing nodes that have only one descendant. You might also want to check out HAT-tries – Justin Peel Feb 16 '10 at 22:30
  • Most trie implementations I know of do the collapsing for you. I'll just have to benchmark some I suppose. Thanks, will look into HAT trees. – BobbyJim Feb 16 '10 at 22:40

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

  • What will that let me do that Java cannot though? – BobbyJim Feb 17 '10 at 3:15
  • C/C++ is faster than Java. – Macarse Feb 17 '10 at 9:47
  • Any source for this statement or maybe sample on how to make it faster using c/c++ (including JNI call overhead)? – n3o59hf Jun 26 '13 at 17:25

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.


Very cool idea as suggested by "Antti Huima" trying to Store dictionary words using long. and then search using binary search.

Your Answer

