Triejs

Customizable Trie Data Structure in Javascript

Or fork this project on GitHub and make revisions and pull requests now.

Triejs on GitHub »

Example Usage

To create a simple dictionary lookup for words, just create a new trie with default options. Add words and get words by prefix through a simple interface

  var Triejs = require('triejs')
    , trie = new Triejs();
  trie.add("Alaska");
  trie.find("Al");
    

If you need a custom data structure to store data you can extend the trie with optional parameters. These parameters allow you to add the ability to insert, sort, and prune data as you need

  var trie = new Triejs({
    // customize the sorting algorithm to sort
    // by population parameter in data object
    sort: function() {
      this.sort(function(a, b) {
        return b.population - a.population;
      }
    }
  });
  trie.add("Phoenix", {
    city: "Phoenix"
    , state: "Arizona"
    , population: 1476331
  });
  trie.find("Ph");
    

Technical Details

This trie implementation is modeled after John Resig's post on performant trie structures. It builds a hash of chars at each node level, with each char containing a hash of a words containing all previous char nodes. At the completion of a word it stores the data in a data property $d. Thus the storage of the word "ant" would look something like this:

  var root = {
    a: {
      n: {
        t: {
          $d: 'ant'
  } } } }
  

However, there is also a level of compression built in such that suffixes that are unique are squashed into a suffix property $s at the point of uniqueness. Thus in the previous example, "ant" would actually compress to the following:

  var root = {
    a: {
      $d: 'ant'
      , $s: 'nt'
  } }
  

You can also see how two similar words would start with combined nodes and then end with suffixes at the point of uniqueness. Here is what the two words "antman" and "anteater" would look like when added into the trie:

  var root = {
    a: {
      n: {
        t: {
          e: {
            $d: 'anteater'
            , suffix: 'ater'
          }
          , m: {
            $d: 'antman'
            , $s: 'an'
  } } } } }
  

Performance

Performance will vary depending on environment and data types, but in general this is what you should get out of the numbers: Fetches might be slightly longer due to tree traversal, but memory usage is about as compact as you can get for prefix searching. Also, in the long term, inserts are faster due to hash index rebuilding when growing too big. Check out the examples and performance page to run performance tests in your own environment.