Posted on April 11, 2009 at 9:07 am

Tries and Ternary Search Trees in Python and Javascript

There are a couple of places in which Tagz, where I needed efficient prefix matching. The most obvious way to do this is to use a Trie or a Ternary Search Tree. So, I ended up implementing both in Python. I’ve had this stuff lying around in my mercurial repo for Tagz for quite some time now. I just thought of releasing it today.

Interestingly, some crude benchmarks indicate that the trie implementation is more efficient than the ternary search tree implementation in terms of both speed and space (Look for test.py in the repo), I also ported the trie module to javascript, and its included in the repo.

Here are two GraphViz graphs visualizing both the structures, generated using the excellent GvGen library.

In the Ternary Search Tree graph, Blue vertices = left, Green vertices = middle, Red vertices = right.

The code can be found here.

Tags:, ,

4 Responses to “Tries and Ternary Search Trees in Python and Javascript”

  1. Counting bloom filters in python and javascript | Jeethu's Blog on April 21st, 2009 at 7:13 PM says:

    […] the theme of implementing simple datastructures in python and javascript, here’s a simple […]

  2. a.in.the.k on May 18th, 2009 at 11:10 AM says:

    Trie.js – nice clean implementation however:
    a) if used for prefix matching it is only slightly faster than performing linear array search and indexOf (results visible on dictionarties about 100000 words)
    b) if used for “compression”, this implementation is the “extravagant variant” from memory (serialization) point of view. However JavaScript associative Arrays halp a lot.
    I’m awaiting Double-Array implementation ;-)) and some clever serialization to make this usable ;-)))

  3. andrei on October 26th, 2009 at 6:39 PM says:

    Trie.js – IE7 and bellow can’t access strings via text[i]. user text.charAt(i) instead.
    other than that, great work!

    andrei

  4. Jeethu on November 10th, 2009 at 11:29 AM says:

    @andrei, Thanks for the tip. Just checked in an updated version.

Leave a Reply