Js Suffix Trie

Js Suffix Trie is a suffix trie implementation that is originally written in CoffeeScript, but a JavaScript compilation is also available.

You can install Node.js to compile CoffeeScript, use the CoffeeScript core compiler or try the Js2coffee online converter.

About suffix tries

• A suffix trie (not to be confused with a suffix tree) stores unique string values in a tree-like way.
• It provides fast lookup
• It saves memory when handling larger amounts of strings
• It does not keep order or indices

For more information about suffix tries:

• http://www.heppenstall.ca/academics/doc/242/F2001Archives/Ch11_3_tries.pdf

Possible applications

• whitelists or blacklists
• large arrays of string (e.g. email adresses)
• autocomplete (e.g. tagging)
• dictionary (e.g. Wordfeud)

Documentation

###Constructor

####JsSuffixTrie()

Creates an empty instance

###Methods

####add(string)

Adds the specified string to the trie. Returns true if the string is not already in the trie, otherwise false

####remove(string)

Removes the specified string from the trie. Returns true if the string was found, otherwise false.

####contains(string)

Returns true if the specified string is in the trie, otherwise false.

####subTrie(prefix)

Returns a new trie representing all strings of the original trie that match the prefix

example:

var trie = new JsSuffixTrie;
trie.add("foo");
trie.add("foobar");
trie.add("barber");
trie.subTrie("foo").toArray();  // returns ["foo", "foobar"]
trie.size();                    // returns 2

####find(prefix)

Returns an array containing all the strings in the trie that match the prefix

example:

var trie = new JsSuffixTrie;
trie.add("foo");
trie.add("foobar");
trie.add("barber");
trie.find("foo");   // returns ["foo", "foobar"]

####each(callback)

Calls the specified callback for each item in the trie. Returns the size of the trie.

example:

var trie = new JsSuffixTrie;
...
trie.each(function (index, item) {
    console.log("#" + index + ": " + items);
});

####size()

Returns the number of items in the trie

####toArray()

Creates a new array containing all item from the trie.

####toJSON()

Creates a JSON serialization of the internal structure of the trie. The trie can be recreated with JsSuffixTrie.fromJSON()

####JsSuffixTrie.fromArray(array)

Creates an instance an adds each item in the array to the trie.

example:

var array = ['one', 'two', 'three'];
var trie = JsSuffixTrie.fromArray(array);

####JsSuffixTrie.fromJSON(json)

Recreates a JsSuffixTrie that has been serialized to JSON.

example:

var trie = new JsSuffixTrie;
trie.add("foobar");
...
var json = trie.toJSON();
...
var originalTrie = JsSuffixTrie.fromJSON(json);

Benchmarks

I benchmarked the JavaScript version on Ubuntu 11.04 x64

Planned

• Internet Explorer benchmarks
• More detailed benchmarks
• rewriting #each without recursion