DAWG data structure in Word Judge

I’m the first to admit that the Word Judge is booooring application. Checking if the word can be used in a word game? Meh. From a programmer perspective however, there is one very interesting problem to solve – how to compress a large dictionary to reduce the size of the application package and at the same time be able to query this dictionary without using excessive amount of memory and CPU power?

First, let’s settle on what is a “large dictionary”. One of the languages supported by Word Judge is Polish, for which the valid word list has over 2 million entries and takes about 36MB after unpacking. Do we need to compress this data at all? Probably not. If you consider the average hardware spec and modern network speed, the 36MB is not much, but we can do so much better. Besides, it’s fun!

Source: http://porcupineprogrammer.blogspot.com.br/2012/03/dawg-data-structure-in-word-judge.html
 

raony