A lightweight auto-complete ActionScript example with a trie

This article was originally written in English. Text in other languages was provided by machine translation.


Auto-complete functionality is used widely over the internet and mobile apps. A lot of websites and apps try to complete your input as soon as you start typing.  In this post, I would like to introduce a simple ActionScript auto-complete solution by using trie data structure.

A trie is an ordered tree data structure that is used to store an associative array. 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. Starting from the root node, you can check if a word exists in the trie easily by following pointers corresponding to the letters in the target word. Trie is a well-known data structure in computer science; you can find the detailed information about trie through Wikipedia.

Here is a simple trie implementation in ActionScript:

/**
* An simple data structure to store and look up words.
* @see http://en.wikipedia.org/wiki/Trie for additional details.
*/

public class Trie {
private var _rootKeys:Array;
public function Trie():void {
_rootKeys=[];
}

/**
* Return a list of words which have the given prefix.
*/

public function get(prefix:String):Array {
var results:Array=[];
var letter:String=prefix.substr(0,1);
var root:TrieNode=_rootKeys[letter];
if (root) {
getWordList(prefix, 1, root, results);
}
return 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:TrieNode=_rootKeys[letter];


if (!root) {
root=createNode(letter);
_rootKeys[letter]=root;
}
insertWord(word, 1, root);
}


private function traverse(root:TrieNode, results:Array, prefix:String):void {
if(root.children) {
for each( var c:TrieNode in root.children ) {
var node:TrieNode = c as TrieNode;
if( node.word ) {
results.push( prefix + node.value);
}
traverse(node, results, prefix+node.value );
}
}
}


private function getWordList(prefix:String,
position:uint,
root:TrieNode,
results:Array):void {
var letter:String=prefix.substr(position,1);
var child:TrieNode=root.children[letter];
if (!letter || !child) {
return;
}


if ( position<(prefix.length-1) ) {
getWordList(prefix, ++position, child, results);
}else {
if (!child.word) {
traverse( child, results, prefix);
}
}

}


private function insertWord(word:String,
position:uint,
root:TrieNode):void {
var letter:String=word.substr(position,1);
if (position==word.length || !letter) {
return;
}


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


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


private function createNode(letter:String):TrieNode {
return new TrieNode(letter,false);
}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>