The original article uses Java, which makes it harder to see how simple it can be to make and use prefix trees. For comparison, here's the Python code to create a prefix tree from a set of words:<p><pre><code> def prefix_tree(words):
d = dict()
for word in words:
root = d
for c in word:
root = root.setdefault(c, {})
root['$$'] = {} # mark end of word with '$$' token
return d
</code></pre>
For example:<p><pre><code> >>> prefix_tree('foo bar baz'.split())
{'b': {'a': {'r': {'$$': {}},
'z': {'$$': {}}}},
'f': {'o': {'o': {'$$': {}}}}}
</code></pre>
To query whether a word is present in a tree you basically compute<p><pre><code> reduce(dict.__getitem__, word, tree)
</code></pre>
and test whether the result (a forest) has an end-of-word '$$' tree.
Tries (actually pronounced "trees" or "Patricia trees") are very memory efficient compared to most alternatives, but really only shine in membership query workloads. If you actually need to return the stored element, you have to rebuild it for every query, which is probably too expensive if you have lots of queries, it would be better to store the whole object continuously somewhere in the data structure so you could return a reference to it.<p>Even then, tries only win if the distribution is suitable to give you the memory efficiency you are hoping for. If you don't have many common prefixes, you're better off with just a hashtable.
A trie is a poor data structure in practice. There is no locality of reference that can be exploited: to lookup a single key, almost the entire length of the memory blocks occupied by the trie needs to be accessed, and almost at random (depending on the insertion technique). For keys inserted later on, the number of different blocks of memory accesses needed for a single key is proportional to the length of the key.<p>A B-Tree is better due to better exploitation of locality of reference in memory.
Should mention that tries can be heavily compressed into DAWGs (Directed Acyclic Word Graphs) by eliminating common subtrees. I've used this in word games on iOS where I want a small memory footprint.<p>P.S. I love tries!
I think the article was well written. This is the standard example to use for a Trie. But I never run into any scenarios except for this that make me think, "A Trie is a good fit for this!" What are some other examples where Tries come in handy?
With a basic Trie, you always have this problem of how to keep the pointers at each node. Naively, you can:<p>1) Keep an array of size equal to the alphabet size, indexed by the characters, holding pointers to successive nodes.<p>- but this blows the memory to O(N * alphabet_size) where N is the input size<p>2) Keep a linked list of pairs (character, pointer).<p>- but this blows the lookup time to O(word_length * alphabet_size)<p>3) Keep something like an STL map<character, pointer>.<p>- still suboptimal complexity of O(word_length * log alphabet_size) + it complicates the code + it dramatically increases the constant time per operation<p>Or you research a bit more and actually learn a way to properly implement a trie, called a Ternary Search Tree:
<a href="http://en.wikipedia.org/wiki/Ternary_search_tree" rel="nofollow">http://en.wikipedia.org/wiki/Ternary_search_tree</a>
John Resig did a really cool series[1][2][3] of deep-dive posts into optimization in JS for mobile, which covered tries (among others) -- it was the first I'd heard of them. Fascinating read.<p>1. <a href="http://ejohn.org/blog/dictionary-lookups-in-javascript/" rel="nofollow">http://ejohn.org/blog/dictionary-lookups-in-javascript/</a><p>2. <a href="http://ejohn.org/blog/javascript-trie-performance-analysis/" rel="nofollow">http://ejohn.org/blog/javascript-trie-performance-analysis/</a><p>3. <a href="http://ejohn.org/blog/revised-javascript-dictionary-search/" rel="nofollow">http://ejohn.org/blog/revised-javascript-dictionary-search/</a>
If you like tries, take a look at the double-array trie: it's a pretty nifty (though somewhat complicated) way to greatly reduce the space usage of tries by interleaving nodes in the same block of memory. It also makes it easier to serialize a trie, so you can quickly load a pre-built one instead of re-doing all the inserts, which is useful for static dictionaries.<p><a href="http://linux.thai.net/~thep/datrie/" rel="nofollow">http://linux.thai.net/~thep/datrie/</a>
Tries haven't been entirely neglected. Quadtrees and octrees are their 2- and 3D analogues, and those are very common in games, renderers and other spatial simulations.
[DAWGs](<a href="http://en.wikipedia.org/wiki/Directed_acyclic_word_graph" rel="nofollow">http://en.wikipedia.org/wiki/Directed_acyclic_word_graph</a>) are a special kind of Trie where similar child trees are compressed into single parents. I extended modified DAWGs and came up with a nifty data structure called ASSDAWG (Anagram Search Sorted DAWG). The way this works is whenever a string is inserted into the DAWG, it is bucket-sorted first and then inserted and the leaf nodes hold an additional number indicating which permutations are valid if we reach that leaf node from root. This has 2 nifty advantages:<p>Since I sort the strings before insertion and since DAWGs naturally collapse similar sub trees, I get high level of compression (e.g. "eat", "ate", "tea" all become 1 path a-e-t with a list of numbers at the leaf node indicating which permutations of a-e-t are valid).
Searching for anagrams of a given string is super fast and trivial now as a path from root to leaf holds all the valid anagrams of that path at the leaf node using permutation-numbers.
I just used a Trie yesterday to implement some string matching that I needed to do in a tokenizer :) It's quite useful if you want to do string matching and you know ahead of time the exact list of strings you need to match with. My only issue with this article is that it explains them using Java, which I think just obscures the explanation too much, but I guess it's a Java blog.
The <i>Dasher</i> input method (aimed at people with disabilities who are able to enter data only by manipulating a pointer) uses a visualized trie with vertex areas proportional to linguistic probability:<p><a href="http://www.inference.phy.cam.ac.uk/dasher/DasherSummary2.html" rel="nofollow">http://www.inference.phy.cam.ac.uk/dasher/DasherSummary2.htm...</a><p>(Prof. Mackay, its author, uses it to teach information theory and compression, among other things.)
Implementing the Trie (on paper, in C) was about 50% of my final exam on my intro to CS undergrad class at Stanford. We had never seen Tries befor that point, but we had done a variety of trees, so we had the necessary prior experience. It was a fun exam and a very memorable experience.
Tries have hardly been neglected. "Path-compressed" tries were very recently added to FreeBSD[0] for use in the vm subsystem.<p>[0]: <a href="http://fxr.watson.org/fxr/source/sys/pctrie.h" rel="nofollow">http://fxr.watson.org/fxr/source/sys/pctrie.h</a>
Tries are great for caching URLs & other path-like data. I've found them to be faster (and smaller) than hashes for these purposes in the past.<p>However, this was back in the days of tiny caches. I suspect they may have lost the edge they had in 2003.