Skip to content

Latest commit

 

History

History
134 lines (84 loc) · 3.42 KB

README.markdown

File metadata and controls

134 lines (84 loc) · 3.42 KB
Raw

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:

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

Js Suffix Trie benchmark results

Planned

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