Sunday, December 28, 2008

JavaScript Trie Implementation

I've been laying around the house this weekend hacking away at little side projects. Here is one of my tangents. Perhaps someone out there will give this little guy a nice home, maybe a Bag implementation or a drop down list for an auto suggest enabled form field.

The Test (and how to use it)

function testThoughtWorks() { 
var trie = new byrne.TrieNode(/* root */);
trie.add('thought');

assertEquals(1, trie.getWordCount('thought'));
assertEquals(0, trie.getPrefixCount('thought'));

trie.add('thoughtworks');

assertEquals(1, trie.getWordCount('thought'));
assertEquals(1, trie.getPrefixCount('thought'));
assertEquals(1, trie.getWordCount('thoughtworks'));
assertEquals(0, trie.getPrefixCount('thoughtworks'));
assertEquals(0, trie.getWordCount('foo'));
assertEquals(0, trie.getPrefixCount('foo'));
}

The Implementation

byrne = {}; // create the namespace

/**
* @see http://en.wikipedia.org/wiki/Trie
* @author Dennis Byrne
* @constructor
*/
byrne.TrieNode = function(){
this.wordCount = 0;
this.prefixCount = 0;
this.children = [];
};

byrne.TrieNode.prototype.add = function(word) {
if(word){
this.prefixCount++;
var k = word.charAt(0);
(this.children[k] || (this.children[k] = new byrne.TrieNode()))
.add(word.substring(1));
}else
this.wordCount++;
};

/**
* Retrieve the prefix count of the applied argument w/ recursion.
*/
byrne.TrieNode.prototype.getPrefixCount = function(word){
return word ?
this.getCount(word, arguments.callee) : this.prefixCount;
};

/**
* Retrieve the word count of the applied argument w/ recursion.
*/
byrne.TrieNode.prototype.getWordCount = function(word){
return word ?
this.getCount(word, arguments.callee) : this.wordCount;
};

/**
* @private
*/
byrne.TrieNode.prototype.getCount = function(word, method){
var k = word.charAt(0);
return this.children[k] ?
method.call(this.children[k], word.substring(1)) : 0;
};

3 comments:

Jalada said...

Completely forgot to post this here, but we've been using this at http://twitterfall.com to power the exclusions filter. I wrote a blog post about it: http://jalada.co.uk/2009/08/01/javascript-aho-corasick-string-search-algorithm.html

raga said...

Can any one tell how to write a plugin for mozila?
i went through various sites..was'nt helpful though

Mikedeboer.nl said...

I created an implementation of a Trie in JS here: http://github.com/mikedeboer/trie.
Your blog post is duly noted there as inspiration, because you were truly the only one I could find that implemented it in the most correct manner.
Thank you for posting your findings and work over here, I hope to contribute back with my implementation.

Cheers,

Mike de Boer.