GADDAG or DAWG

[nisaa15]

Hi,

Im looking for a data structure that will allow for me to store a dictionary of words. The data structure should allow for the dictionary to be rapidly searched later on, since it shall be used as part of a scrabble move generation program. I have read two articles and they talk about a DAWG and GADDAG how would i go about programming these (in java) , and what data structure should be used???

Cheers for any help!

[RoboTact]

What kinds of search requests do you need?

[nisaa15]

What kinds of search requests do you need?

Sorry, but I dont fully understand your question. The computer should be able to rapidly search through the dictionary and find all relevant words that can be made on the scarbble board (taking into accound the boards constraints). I need the searching process to be very quick therefore the use of a GADDAG/ 2 way DAWG is needed. But how would i program such a thing in java?

[mehdi62b]

I really didn't know DAWG structure but for dictionary program a binary alphabetical search tree could be suitable(or every knid of it like B-Tree)it depends on the dictinary you wanna to bulid,this link has some info
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK3/NODE129.HTM

[mehdi62b]

I have read two articles and they talk about a DAWG and GADDAGwhich articles?where are there?

[nisaa15]

they are called the worlds fastest scrabble program by appel and jacobson and the other one is called
A faster move generation algorithm.

[mehdi62b]

well,yes it depends on your search method if you need to find the prefixes the best structure is a Trie it would give you a word or all the words which have a sepcific prefix in O(1) (or O(c),c is the maximim lenght of the trie),while trees would take O(logn)

I'm not sure about DAWG and its implementation,take a look here (http://www.wutka.com/dawg.html) it has some explanation on making a DAWG.

[nisaa15]

well,yes it depends on your search method if you need to find the prefixes the best structure is a Trie it would give you a word or all the words which have a sepcific prefix in O(1) (or O(c),c is the maximim lenght of the trie),while trees would take O(logn)

I'm not sure about DAWG and its implementation,take a look here (http://www.wutka.com/dawg.html) it has some explanation on making a DAWG.

Hey thanks for the earlier stuff, do you know of the GADDAG structure, thats theone i wish to use but do not know how to impemnt such a thing.

[sgordonphd@gmail.com]

My GADDAG article can be viewed at http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue2/spe880.pdf

The DAWG algorithm is simpler and therefore easier to implement. The advantage of the GADDAG algorithm is that it is 2 times faster. The disadvantage is that it takes up 5 times as much memory. On a modern computer, the memory issue is minor, and both algorithms are much faster than a human opponent.

The main motivation for the development of the GADDAG algorithm was to double the speed of simulating the likely outcomes of candidate moves in order to select which move is best. Doubling the speed allows one to simulate twice as many scenarios using the GADDAG algorithm in the same period of time. If your program is going to simply pick the highest scoring play or apply a static heuristic to decide which move to make, then the DAWG algorithm is probably a better choice.

If you have any specific questions, I will be happy to answer them. A good resource for information and working code examples is http://www.gtoal.com/wordgames/

Steven Gordon