Sometimes they just need to check the spelling of a word, and other times players want to find a way to improve their language skills. Sooner or later, every Scrabble enthusiast reaches out for outside assistance. If I do eventually post that I'll update this question.Scrabble Word Finder – Top Online Tool That Helps Scrabble Players Worldwide I've got an implementation of a functional-style persistent trie that I've been meaning to blog about for a while but never got around to it. I sketched out the search algorithm in your previous question. If you haven't got any "A"s on the rack, there is no need to go down any "A" node. To search the trie for matching a rack, the idea is to explore every part of the trie, but to prune out the areas where the rack cannot possibly match. If you do want to store the trie in some format that is more like a trie, it shouldn't be hard to come up with a serialization format. It shouldn't take more than 30 seconds or so, and then you can re-use the trie in memory. To store your trie on disk - frankly, I would just store the word list as a plain text file and rebuild the trie when you need to. Of course, rather than writing "root.Children." you'll write a loop that searches the trie to see if the node you want exists, and if not, create it. We already have a node for "A", so add to it the "B$" node: (new trieNode('B', true, new List()) Now add a node for the second letter: (new trieNode('A', true, new List())) Ī$ - we notate the end of word flag with $ How do you add the word "AA", the first word in the Scrabble dictionary? Well, first make a node for the first letter: ('A', false, new List()) That is, this is the "root" trie node that represents the beginning of a word. You can start with an empty trie: TrieNode root = new TrieNode('^', false, new List()) My advice is to get it working first, and then measure its performance, and if it is unacceptable, then experiment with making changes to improve its performance. Also, maybe a flat list is not the best data structure maybe some sort of dictionary is better. This of course is just a sketch you'd probably want to make these have proper property accessors and constructors and whatnot. So let's sketch the data structure: class TrieNode (As opposed to going with a b-tree sort of solution where you keep most of the tree on disk because it is too big to fit in memory all at once.)Ī trie is basically nothing more than a 26-ary tree (assuming you're using the Roman alphabet) where every node has a letter and one additional bit on each node that says whether it is the end of the word. With a word list of about 400K words of reasonable length you should be able to keep the trie in memory. the word list will be about 400K words, and so is probably about one to ten megs of string data when uncompressed.Ī trie is the classic data structure used to solve this problem because it combines both memory efficiency with search efficiency. That is, given a "rack" of n letters, what are all the n-or-fewer-letter words in the word list that can be made from that rack. You want to store a word list for a game in a data structure that efficiently supports the "anagram" problem.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |