It was pretty interesting to implement and sped up the real-time dictionary searches exponentially (from my original solution, which was a basic SQL LIKE match).
Additionally, Hexiled uses a number of languages, including with accented characters and this didn't have any negative impact on things.
DAWGs are really cool. GADDAGs are faster than DAWGs only for the special purpose of finding a word given a prefix (applicable to Scrabble move-finding). Otherwise they are the same speed if you're just anagramming; since a GADDAG is at least 5 times bigger than a DAWG on average (given an English dictionary corpus), the GADDAG may even be slower because it wouldn't fit in cache memory.
The best known Scrabble AI (Quackle) uses both data structures, although only the DAWG is strictly necessary.
I wrote a GADDAG maker in Go a while ago with the intent of turning it into a Scrabble move finder, but haven't found the time to work on it in a while. I would like to optimize it further too...
Often when people talk about trees as data structure what they actually want are DAGs (e.g. filesystems usually are used as DAGs not trees, because they can have links (although on linux you can actually create cycles in practice people try to avoid it)). Nice to see a good example.
Hm, so testing for membership in a DAWG is like testing for one in a trie, which involves a lot of pointer chasing?
Couldn't you get the small space requirements with a more cache-friendly structure? What about this solution:
1) Train a huffman code on the dictionary
2) Compress all words with this code
3) Store them concatenated and sorted.
4) On lookup, compress the key and do a binary search
Well I guess he says that a 36 MB dictionary goes down to 1.5 MB. That's pretty good. I'd guess that with a good huffman encoder you could probably get it down to 3.6 MB (10%), so maybe they are still doing better in terms of size.
I guess for some applications like games you don't really care too much about lookup speed.
You can store a Trie or a DAFSA in a single chunk of memory and still have blazingly fast lookups - see double-array tries. The disadvantage is that inserting/removing values is more costly, but DAFSA doesn't support it anyways.
"On lookup, compress the key and do a binary search"
That binary search will be hampered a bit by the fact that your keys have variable length. So, you either need to use a separator and search for the word start in each iteration, or you have to pad your words to equal lengths.
Also, space-efficient designs will not chase pointers. The dawg will store relative offsets (20 bits will often be more than enough there) not pointers.
Also, i expect that a N-ary trie (with N=26 or even larger) will be more cache-friendly than a binary search because its depth is smaller by a factor 4 to 5.
I doubt this will beat a dawg, space-wise, either. The big advantage of a dawg is that it collapses the tails of words with similar variants into one. All those nouns ending in "tion", with plural "tions", and adverbial form "tional" will share their tail nodes.
14 comments
[ 2.5 ms ] story [ 23.2 ms ] threadIt was pretty interesting to implement and sped up the real-time dictionary searches exponentially (from my original solution, which was a basic SQL LIKE match).
Additionally, Hexiled uses a number of languages, including with accented characters and this didn't have any negative impact on things.
[1] http://hexiledgame.com
Also, if anyone wonders, DAWG means: Directed Acyclic Word Graph
The best known Scrabble AI (Quackle) uses both data structures, although only the DAWG is strictly necessary.
I wrote a GADDAG maker in Go a while ago with the intent of turning it into a Scrabble move finder, but haven't found the time to work on it in a while. I would like to optimize it further too...
https://github.com/domino14/macondo/tree/master/gaddag
The resulting file size is slightly larger (1.6MB instead of 1.5MB), but that's likely because I converted data from cp1250 to utf8 before encoding.
Couldn't you get the small space requirements with a more cache-friendly structure? What about this solution:
1) Train a huffman code on the dictionary 2) Compress all words with this code 3) Store them concatenated and sorted. 4) On lookup, compress the key and do a binary search
Well I guess he says that a 36 MB dictionary goes down to 1.5 MB. That's pretty good. I'd guess that with a good huffman encoder you could probably get it down to 3.6 MB (10%), so maybe they are still doing better in terms of size.
I guess for some applications like games you don't really care too much about lookup speed.
https://code.google.com/p/dawgdic/ library works this way; I'm not sure, but it seems https://github.com/chalup/dawggenerator also works this way.
For mutable tries there are HAT-Tries which are designed to be cache-friendly; see e.g. an implementation at https://github.com/dcjones/hat-trie and a Python wrapper at https://github.com/kmike/hat-trie.
That binary search will be hampered a bit by the fact that your keys have variable length. So, you either need to use a separator and search for the word start in each iteration, or you have to pad your words to equal lengths.
Also, space-efficient designs will not chase pointers. The dawg will store relative offsets (20 bits will often be more than enough there) not pointers.
Also, i expect that a N-ary trie (with N=26 or even larger) will be more cache-friendly than a binary search because its depth is smaller by a factor 4 to 5.
I doubt this will beat a dawg, space-wise, either. The big advantage of a dawg is that it collapses the tails of words with similar variants into one. All those nouns ending in "tion", with plural "tions", and adverbial form "tional" will share their tail nodes.