gram@uctcs.uucp (Graham Wheeler) (06/03/91)
Hi all I am looking for a good PD scrabble game program. Alternatively I may write my own. In the latter case, I want to construct a DAWG for the lexicon (see the article `The World's Fastest Scrabble Program' in CACM May 1988 (I think!)) I would be interested if there is a way to construct a DAWG efficiently (space-efficient is more important than time), particularly when using a segmented architecture like 80x86. My ideas at present include: - an array of 20 000 far pointers to nodes (assuming no more than 20 000 nodes` would be needed) - each node contains a variable size set of numbers pointing back to the array. I would analyse the lexicon and find all possible 2 letter sequences. Let's say that `k' is sometimes followed by 'e', `i', 'l' or 'o` but no other letters. Then every `k' node would have four indexes, one for each of these possibilities. The most-significatnt byte of the pointer value stored in the array could be used to indicate whether the node is terminal or not. The problem with this is that my algorithm requires both forward and *backward* pointers during construction time. Does anyone know of a better way to do this? Even better, does anyone have a good PD scrabble? Please E-mail replies, thanks. Graham Wheeler <gram@cs.uct.ac.za> | "That which is weak conquers the strong, Data Network Architectures Lab | that which is soft conquers the hard. Dept. of Computer Science | All men know this; none practise it" University of Cape Town | Lao Tzu - Tao Te Ching Ch.78