So in the kickoff post of my series on data structures and algorithms I’d like to begin with a relatively simple but handy little data structure: the trie. If you want to jump ahead and look at a very simplistic implementation of a trie data structure (only the insert and dump operations have been completed), I’ve put my experimental code up on GitHub here.

A clever little play on the word retrieval (though I, and many others, insist on pronouncing it “try”… suck it etymology), a trie is a key-value store represented as an n-ary tree, except that unlike a typical key-value store, no one node stores the key itself. Instead, the path to the value within the tree is defined by the characters/bits/what-have-you that define the key itself. Yeah, that’s pretty abstract, why don’t we just look at an example:

In this construction I’ve chosen the following set of keys:

• allow
• alter
• alloy
• ant
• bad
• bar

As you can see, each character in the key is used to label an edge in the tree, while the nodes store the values associated with that key (note, in this example I’ve chosen to use the keys as values as well… this entirely artificial, and a bit confusing. Just remember, those values could be absolutely anything.) ¹ Typically these keys are strings, as depicted here, although it’s entirely possible to build a bit-wise trie that can be keyed off of arbitrary strings of bits. To find the value for a key, you take each character and, starting with the root node, transition through the graph until the target node is found. Or, as pseudo-code:

find(root_node, key):
  current_node = root_node
  current_key = key
   
  while (current_key.length > 0):
    character = current_key[0]
   
     if current_node.has_edge_for(character):
       current_node = current_node.get_get_for(character).endpoint
     else
       throw "ERMAGERD"
   
   return current_node.value

Strangely, a very similar algorithm can be used for both inserts and deletes.

Some Interesting Properties

The trie offers a number of interesting advantages over traditional key-value stores such as hash tables and binary search trees:

1. As mentioned previously, they have the peculiar feature that inserts, deletes, and lookups use very similar codepaths, and thus have very similar performance characteristics. As such, in applications where these operations are performed with equal frequency, the trie can provide better overall performance than other more traditional key-value stores.
2. Lookup performance is a factor of key length as opposed to key distribution or dataset size. As such, for lookups they often outperform both hash tables and BSTs.
3. They are quite space efficient for short keys, as key prefixes are shared between edges, resulting in compression of the graph.
4. They enable longest-prefix matching. Given a candidate key, a trie can be used to perform a closest fit search with the same performance as an exact search.
5. Pre-order traversal of the graph generates an ordered list of the keys (in fact, this implementation is a form of radix sort).
6. Unlike hashes, there’s no need to design a hash function, and collisions can only occur if identical keys are inserted multiple times.

Applications

Because tries are well-suited to fuzzy matching algorithms, they often see use in spell checking implementations or other areas involving fuzzy matching against a dictionary. In addition, the trie forms the core of Radix/PATRICIA and Suffix Trees, both of which are interesting enough to warrant separate posts of their own. Stay tuned!

References

• Trie
• http://www.allisons.org/ll/AlgDS/Tree/Trie/
• http://xlinux.nist.gov/dads//HTML/trie.html

So, generally speaking, I’ve typically adhered to the rule that those who develop software should be aware of various classes of algorithms and data structures, but should avoid implementing them if at all possible. The reasoning here is pretty simple, and I think pretty common:

1. You’re reinventing the wheel. Stop that, we have enough wheels.
2. You’re probably reinventing it badly.

So just go find yourself the appropriate wheel to solve your problem and move on.

Ah, but there’s a gotcha, here: Speaking for myself, I never truly understand an algorithm or data structure, both theoretically (ie, how it works in the abstract, complexity, etc) and practically (ie, how you’d actually implement the thing) until I try to implement it. After all, these things in the abstract can be tricky to grok, and when actually implemented you discover there’s all kinds of details and edge cases that you need to deal with.

Now, I’ve spent a lot of my free time learning about programming languages (the tools of our trade that we use to express our ideas), and about software architecture and design, the “blueprints”, if you will. But if languages are the tools and the architecture and design are the blueprints, algorithms and data structures are akin to the templates carpenters use for building doors, windows, etc. That is, they provide a general framework for solving various classes of problems that we as developers encounter day-to-day.

And, like a framer, day-to-day we may very well make use of various prefabbed components to get our jobs done more quickly and efficiently. But without understanding how and why those components are built the way they are, it can be very easy to misuse or abuse them. Plus, it can’t hurt if, when someone comes along and asks you to show off your mad skillz, you can demonstrate your ability to build one of those components from scratch.

Consequently, I plan to kick off a round of posts wherein I explore various interesting algorithms and data structures that happen to catch my attention. So far I have a couple on the list that look interesting, either because I don’t know them, or because it’s been so long that I’ve forgotten them…

Data Structures

1. Skip list
2. Fibonacci heap
3. Red-Black tree
4. Tries
   1. Radix/PATRICIA Tries
   2. Suffix Tries
5. Bloom filter

Algorithms

1. Various streaming algorithms (computations over read-once streams of data):
   1. Heavy hitters (finding elements that appear more often than a proscribed freqency)
   2. Counting distinct elements
   3. Computing entropy
2. Topological sort

And I guarantee there’s more that belong on this list, but this is just an initial roadmap… assuming I follow through, anyway.