Emanuele Feronato

Talking about Actionscript 3, Flash, Game development and Users contributions.

This post is guest-blogged by Alex Schearer from anotherearlymorning.com, and it’s very interesting for anyone looking to enter the Word Play contest.

It explains the use of Trie Data Structure

In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree shows what key it is associated with. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest (source: Wikipedia).

« 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 »

package com.aem.utils{
	/**
	     * An efficient data structure to store and look up words.
	     *
	     * @see http://en.wikipedia.org/wiki/Trie for additional details.
	     * @author Alexander Schearer 
	     */
	public class Trie {
		private var letters:Array;

		public function Trie():void {
			letters=[];
		}

		/**
		         * Return a list of words which are prefixes for the given string.
		         *
		         * e.g. programming => program, programming
		         */
		public function get(jumble:String):Array {
			var results:Array=[];
			var root=letters[jumble.substr(0,1)];
			if (! root) {
				return results;
			}

			getRecursively(jumble, 1, root, results);
			return results;
		}

		private function getRecursively(jumble:String, 
		                position:uint, 
		                root, 
		                results:Array):void {
			var letter:String=jumble.substr(position,1);

			var child=root.children[letter];
			if (! child) {
				return;
			}

			if (child.word) {
				results.push(jumble.substr(0, position + 1));
			}

			getRecursively(jumble, ++position, child, results);
		}

		/**
		         * Add a word to the object which can be matched as a prefix.
		         */
		public function add(word:String):void {
			var letter:String=word.substr(0,1);
			var root=letters[letter];

			if (! root) {
				root=createNode(letter);
				letters[letter]=root;
			}

			addRecursively(word, 1, root);
		}

		private function addRecursively(word:String, 
		                position:uint, 
		                root):void {
			if (position==word.length) {
				return;
			}

			var letter:String=word.substr(position,1);
			if (! letter) {
				return;
			}

			var child=root.children[letter];
			if (! child) {
				child=createNode(letter);
				root.children[letter]=child;
			}

			if (position==word.length-1) {
				child.word=true;
			} else {
				addRecursively(word, ++position, child);
			}
		}

		private function createNode(letter:String) {
			return { value: letter, word: false, children: [] };
		}
	}
}

I am playing with this library and I’ll be able to show you some stuff in a couple of days.