Trie Data Structure in Actionscript 3

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.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stairs
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers