Words that start the same
You type "ca" into a search box and it instantly suggests "car", "cart" and "cat". Behind that is a question a hash table cannot answer well: which stored words begin with these letters?
A hash table can tell you whether "cat" is stored. It cannot find words near "cat", because hashing scatters similar words to unrelated places. A sorted list can do it with some searching. A trie is built for exactly this.
The name comes from retrieval. It is usually pronounced "try".
A tree of letters
In a trie, a word is not stored in one place. It is spelled out along a path.
Start at an empty root
It stands for "nothing typed yet".
Each step down adds one letter
The node you reach stands for everything typed so far.
Mark the nodes where a complete word ends
The path to "car" passes through "c" and "ca". Only "car" is marked.
Words with the same beginning share that part of the path
"car" and "cat" share "c" and "a", then split.
- the path just walked
- end of a word
- a word found by the search
Start. An empty trie: just a root. Each step down from here will stand for one letter.
- Nodes
- 1
- Letters in all the words
- 15
Five words with 15 letters between them fit in 9 nodes, because the common beginnings are stored once.
Why prefix search is nearly free
To find everything starting with "ca":
- Walk down c, then a. Two steps.
- Every word below that node starts with "ca". Collect them.
The walk takes one step per letter typed. It does not depend on how many words are stored. A trie holding every word in the language answers "ca" in the same two steps.
Example
Looking up one word
Is "cart" stored? Follow c, a, r, t. Four steps, and the last node is marked: yes.
Is "ca" stored? Follow c, a. The node exists but is not marked: "ca" is only the beginning of other words.
Is "cow" stored? Follow c, then look for o. There is no such branch: no, and you found out after two letters.
Lookup time depends on the length of the word, not on the number of words.
class TrieNode:
def __init__(self):
self.children = {} # letter -> TrieNode
self.is_word = False
def insert(root, word):
node = root
for letter in word:
node = node.children.setdefault(letter, TrieNode())
node.is_word = True
def starts_with(root, prefix):
node = root
for letter in prefix:
if letter not in node.children:
return None # nothing starts with this
node = node.children[letter]
return node # everything below here matchesWhat it costs
Good at
- Finding all words with a given prefix takes one step per letter of the prefix
- Looking up a word takes one step per letter, however many words are stored
- Words come out in alphabetical order for free
- Shared beginnings are stored once
Where it bites
- Uses a lot of memory: a node for every letter of every distinct path, each with its own links
- Nodes are scattered in memory, so walking them is slower than scanning an array
- For plain exact lookups, a hash table is simpler and faster
Compact versions exist that merge chains of single-child nodes into one node holding several letters. These are called radix trees or compressed tries, and they are what most real systems use.
Where you will meet it
- Autocomplete and search suggestions.
- Spell checkers: is this a word, and what words are close to it?
- Routing in networks. A router picks where to send a packet by finding the longest stored prefix that matches its address. That is a walk down a trie of bits.
- Phone keypads and word games: which words can be made from these letters?
- URL routing in web frameworks: matching
/users/42/ordersagainst the registered paths.
Key takeaways
- A trie stores words as paths, with one letter for each step down.
- Words that begin the same way share the start of their path.
- Finding every word with a given prefix means walking down the prefix and collecting what is below.
- Lookup time depends on the word's length, not on how many words are stored.
- The cost is memory, so use a trie when prefix questions matter and a hash table when they do not.