Clojure Data Structures and Algorithms Cookbook

Designing an autocomplete system using a trie

A trie is a particular tree data structure that makes it possible for us to store prefixed data. As you descend a trie, you construct prefixes. As such, a node's children share a common prefix, which is the one we constructed so far while descending the tree. In fact, tries are like automaton, where descending a branch is analogous to consuming a transition literal and the state you'd get into when you do so is the prefix of that target node.

Generally, nodes of a trie carry information about the transitions and can carry weight depending on their use.

One interesting application of tries is text autocompletion. You can store strings in a prefixed manner in a trie. These strings would span over the shared ...