Last week I shared Mochi’s Word Play competition. Since then I’ve made a great deal of progress on a prototype I hope to share with you soon. In the meantime I thought I’d share some of the stuff I’ve been working with as it may be useful for you, especially if you’re planning on entering the contest with me. After the fold I’ll introduce you to the Trie data structure and an implementation in Actionscript 3.
For my game I needed to determine whether a word existed in a set of letters. For instance, what valid words are present in the string “grateddy”? The naive way to approach this problem would be to construct a dictionary or hash table from the valid words and then traverse it looking for each possible substring. You could speed this up by using binary search or a hash look up to quickly reduce the search space. Still you would need to perform a lot of look ups in order to find the words “grate”, “grated”, “rate”, “ate”, and “teddy”. Another shortcoming to this approach is its memory usage. Storing each word in a dictionary fails to take advantage of the redundancy found in the English language. For instance, the words “grate” and “grated” have the first five letters in common. If we take advantage of that we can reduce the total amount of memory used in our dictionary significantly.
Enter the Trie data structure, a Trie is a special type of tree. Each node has a letter, a flag indicating whether it’s a valid word, and a list of 26 pointers to child nodes (one for each letter in the alphabet). Whenever you add a word to the tree you start with the first letter and find the tree associated with it. You then move to the next letter and find its associated child node, and so on. Finally, when you reach the end of the word you mark the node as a valid word. Later when you want to find whether a word is valid or not you simply traverse the tree letter by letter and check the flag at the end. Anyway, enough talk, check out the code below or the gist itself for more.
Hello, my name is Alex Schearer. I grew up in New York and currently live in Seattle.
2 Comments
Really interesintg post.
I would like to publish it on my blog.
Of course you and your site will be fully credited
Let me know
Emanuele
NICE. I love tries… Hope your project is going well!