h1. Trie

This is a trie for Ruby using libdatrie. It uses a dual-array system, meaning it has best-in-class memory usage and search time.


h2. What is a trie?

I suck at explaining things.  Wikipedia doesn't.  http://wikipedia.org/wiki/Trie.

But in short a trie is a data structure that holds strings in a tree.  So if you inserted the words 'arc', 'ark', and 'ape' in a trie you could visualize it thusly:

<pre>
      p - e
    /
  a - r - c
        \
          k
</pre>

It's easy to see how this can have pretty neat implications for things like searching through lists of strings, sorting lists of strings, and things like spelling correction and autocompletion.


h2. Tutorial

Let's go through building a simple autocompleter using Trie.

<pre><code>
  Trie.new
</code></pre>

Anyway.  So we've created our blank trie.  Now, since we're creating an autocompleter, we'll need to add some words into it.  We do that simply with the add method.

<pre><code>
  words.each do |word|
    trie.add word
  end
</code></pre>

Or if you have some integer data to store along with the words, such as weights or scores of some kind, you'd do it like so...

<pre><code>
  words_and_weights do |word,weight|
    trie.add word, weight
  end
</code></pre>

Great, so we've populated our trie with some words.  (Note the limitations section below.)  Let's make sure those words are really there.

<pre><code>
  trie.has_key?('widget')  #=> true

  trie.get('widget')  #=> -1 or your value

  trie.get('not-in-the-trie')  #=> nil
</code></pre>

If you didn't enter a value to go along with the word, calling <code>get</code> with it will return -1.

Okay great, we have our populated trie, we've confirmed that the keys are in there.  Let's make an autocompleter!  For this we'll need to use the <code>children</code> method.  We'll do this as a simple Rails action, with the assumption you've initialized the trie into <code>TRIE</code>.

<pre><code>
  def autocomplete
    children = TRIE.children(params[:prefix])

    respond_to do |format|
      format.js { render(:string => JSON.dump(children)) }
      format.yaml { render(:string => YAML.dump(children)) }
    end
  end
</code></pre>

Yep, that's it.

There are, of course, some more interesting and advanced ways to use a trie.  For instance, this snippet take a string, then walks down the trie, noting each word it finds along the way.

<pre><code>
  word = 'forestry'
  node = trie.root

  word.split('').each do |char|
    break unless node.walk!(char)
    if node.terminal?
      puts "Found me a word: #{node.full_state}"
    end
  end
</code></pre>

By calling <code>root</code> on a Trie object, you get a TrieNode, pointed at the root of the trie.  You can then use this node to walk the trie and perceive things about each word.


Copyright (c) 2008 Tyler McMullen. See LICENSE for details.