Algorithms · Lecture Notes

Chapter 11: Tries

When “an” is typed into a search box, suggestions such as “and”, “ant” and “answer” appear below it. Finding these suggestions in milliseconds does not require trying every word in the dictionary one by one. If the words are stored in a tree in which they share their common beginnings, all the words that start with “an” are gathered under a single node. This tree is called a trie, also known as a prefix tree. The notes first introduce the structure of the trie and its node class in Java. Then insertion, search, prefix queries, autocomplete and deletion are presented with code and step-by-step traces. Applications such as wildcard search, spell checking and the longest common prefix are built on top of these basic operations. The analysis section works out the running times of the operations and the memory cost of the trie with numeric examples, and compares the trie with the hash table and the binary search tree. The notes end with the other members of the trie family: the binary trie, the ternary search trie, the compressed trie, the suffix trie and Aho–Corasick.

Learning outcomes

Structure
Explain the structure of a trie made up of a root, nodes, edges and an end-of-word marker; draw the trie of a set of words and count its nodes and null references.
Operations
Write insertion, search, prefix queries, autocomplete and deletion in Java and trace them step by step. Build derived operations such as prefix counts, wildcard search and the longest common prefix on this foundation.
Analysis
Justify the O(L) running time and the O(N · M) memory of the operations; weigh the ways of storing children; compare the trie with the hash table and the balanced binary search tree.
Variants
Explain which question the binary trie, the ternary search trie, the compressed trie, the suffix trie and the Aho–Corasick algorithm each solve, and trace them on small examples.

11.1The trie concept

Most programs that work with strings keep asking the same question: is this word in the dictionary? A spell checker asks it for every word. A compiler looks up every identifier in its table of keywords. A router looks up the address of every packet in its routing table. For many of these questions a hash table is a good answer. But some questions concern not the whole word but its beginning: “which words start with an?”, “which is the longest matching prefix of this address?” For questions of this kind we need a structure that keeps the common beginnings of words together.

Two terms used often in these notes should be made clear from the start. A prefix of a string is a part taken from the beginning of the string: the prefixes of the string “and” are “”, “a”, “an” and “and”. A suffix is a part taken from the end of the string: the suffixes of “and” are “and”, “nd”, “d” and “”. Every piece taken from inside a string as consecutive characters is a substring. Every substring is a prefix of some suffix. This observation is the basis of the suffix trie.

11.1.1Definition

Consider a dictionary: and, ant, dad, do. Of these four words, two start with “a” and two with “d”. “and” and “ant” also share the prefix “an”. A trie shows this sharing explicitly. Each step down from the root reads one character. Words that begin with the same character enter the same branch and part ways only at the first different character.

Definition 11.1

A trie (prefix tree) is a data structure that stores a set of strings in a rooted tree. Each edge of the tree carries a character; the characters on the edges leading to the children of a node are all different. The root represents the empty string. Each node represents the concatenation of the characters on the path from the root down to that node, that is, a prefix. The node at which a word of the set ends is additionally marked as an end of word. A word is in the set only if there is a path from the root for it and the last node of the path is marked.

The last sentence of the definition is important. The existence of a path alone is not enough. The path for “an” exists in the trie, but “an” is not in the set; the “an” node is unmarked. The path is merely a prefix of words in the set. The name trie comes from the word retrieval. It was proposed by E. Fredkin in his 1960 paper “Trie Memory”. In these notes the names trie and prefix tree refer to the same structure.

rootandandtantdaddadodo
Figure 11.1: The trie of the words and, ant, dad and do. A word ends at each node drawn with a double circle; the word is written below the node.

In Figure 11.1 there are two edges out of the root: “a” and “d”. The “a” node has a single child, “n”. At the “an” node the path forks: “d” leads to “and” and “t” to “ant”. On the right side the “d” node forks too: “a” to “da” and “o” to “do”. “da” has a single child, “d”, and “dad” ends there. The total number of characters in the four words is 3 + 3 + 3 + 2 = 11, but apart from the root there are only 8 nodes. The 3 characters in between were saved by sharing common prefixes: “and” and “ant” share two characters (“a”, “n”), and “dad” and “do” share one (“d”).

The uses of the trie follow from this structure. In autocomplete, we descend to the node of the typed prefix and suggest the words below it. In spell checking, a word is looked up in the trie; if it is not found, words close to it are also searched for on the trie itself. In IP routing, addresses are stored as bit strings and the route whose prefix matches the packet's address for the longest stretch is found.

11.1.2Why a trie?

The question is this: all the words that start with “an” are to be found in a dictionary. The dictionary has n words, and the words are at most L long. Different data structures answer this question at different costs.

Array or list. Each word is taken in turn and its first two characters are compared with “an”. One comparison reads at most L characters, so the total work is O(n · L). As the dictionary grows, the time grows linearly. If the array is sorted, the first matching word can be found by binary search in O(L · log n), but adding a new word becomes expensive because of the shifting in the array.

Hash table. It finds a whole word in O(L) time on average: first the hash value is computed from the L characters of the word, then the relevant bucket is examined. But a hash table cannot answer the prefix question. There is no relation between the hash values of “an” and “and”. A good hash function is in fact designed to scatter similar keys to distant places in the table. So the question “words starting with an” can be answered only by scanning the whole table.

Trie. From the root we first descend into the “a” branch, then into the “n” branch; two steps suffice. Every word below the node reached starts with “an”, and no word outside this subtree starts with “an”. The cost of finding the prefix node depends not on the number of words in the dictionary but on the length of the prefix.

danoatddrootan
Figure 11.2: The node of the prefix “an”. Every word in the subtree of this node (and, ant) starts with “an”; the remaining branches are never looked at.

This observation is the real contribution of the trie: the running time depends not on n but on L. Whether the dictionary has four words or a million, “dad” is found in at most three steps. A balanced binary search tree needs log2 106 ≈ 20 comparisons, and every comparison reads the characters of the word again.

11.1.3Basic components

A trie consists of four components. Each of these components corresponds to an element in the code.

  • Root: the node that represents the empty string; it corresponds to no character. Every operation starts at the root. An empty trie consists of the root alone.
  • Nodes: the path from the root to a node is a prefix. Each node holds the links to its children. A node can have at most M children, where M is the size of the alphabet. For lowercase English letters M = 26.
  • Edges: an edge joins a node to its child and carries a character. Two edges leaving the same node cannot carry the same character; this rule ensures that each prefix has at most one node in the trie.
  • End-of-word marker: its name in the code is isWord. It states that a word ends at the node. It is shown with a double circle in the figures.
rootandandtantdaddadodo
Figure 11.3: The components of a trie. The colored node represents the prefix “an”. “an” is not a word (it is unmarked), but it is a prefix of “and” and “ant”.

The relation among the components can be summarized as follows. There is a one-to-one mapping between nodes and prefixes: each prefix is represented by at most one node. Edges carry characters, while nodes stand for prefixes. The end-of-word marker says which prefixes are also words of the set. Leaf nodes are always marked: an unmarked leaf would be a useless node lying on the path of no word. That is why deletion leaves no unmarked leaf behind.

11.1.4Example: a trie of seven words

A somewhat bigger example shows why the end-of-word marker is indispensable. The words are ab, aba, abc, ad, ba, bad and bag. The total length of the seven words is 2 + 3 + 3 + 2 + 2 + 3 + 3 = 18 characters.

rootababaabacabcdadbabadbadgbag
Figure 11.4: The trie of the words ab, aba, abc, ad, ba, bad, bag. The “ab” and “ba” nodes are both an end of word and on the path of other words.
Example 11.1

Question. How many nodes does the trie of seven words have? Which nodes are marked?

Solution. The nodes are all the distinct prefixes of the words. Those starting with “a”: a, ab, aba, abc, ad (5 nodes). Those starting with “b”: b, ba, bad, bag (4 nodes). That makes 9 nodes, 10 including the root. The 18 characters have fitted into 9 nodes. The marked nodes are the words themselves: ab, aba, abc, ad, ba, bad, bag. Two unmarked nodes remain: a and b. These are only prefixes.

The “ab” node cannot be decided by looking at the figure alone. The node has two children (a and c); that is, “ab” is a prefix of other words. At the same time it is itself a word. The structure cannot tell these two cases apart; only the isWord marker makes the distinction. Without the marker, “ab” and “a” would be nodes of the same kind and the answer to the question “is ab in the dictionary?” would be lost.

Common mistake

Confusing the end of a word with being a leaf. The rule “a word ends at a leaf” is wrong. “ab” and “ba” are internal nodes, but they are words. The correct rule goes the other way: every leaf is an end of word, but not every end of word is a leaf.

11.1.5A trie that carries values

A trie can store not only a set of words but also a map. For this, a value is kept in the node instead of the isWord flag. If the value is null, the node is not the end of a key; otherwise it is the value of the key that ends at that node. In this way the trie works like a dictionary whose keys are strings.

Table 11.1: The keys and values of a trie that carries values.
KeyValueKeyValue
A15tea3
i11ted4
in5ten12
inn9to7
rootA15i11n5n9tea3d4n12o7
Figure 11.5: A trie that carries values. The numbers are the values stored in the nodes. The “t” and “te” nodes carry no value; they are only prefixes.

There are eight keys in the figure, and each ends at a node. “i”, “in” and “inn” form a chain in which each is a prefix of the next; all three carry values. The “t” node splits into two branches: “to” and “te”. “te” has three children: tea, ted and ten. The number of keys is 8, and the number of nodes other than the root is 10: A, i, in, inn, t, te, tea, ted, ten, to. The two nodes that carry no value (t and te) merely form the path.

There is one more detail in this example: “A” is an uppercase letter. An ordinary trie that holds its children in an array of 26 elements can store only lowercase letters. For a key with an uppercase letter, either a wider alphabet is needed or the children are kept in a HashMap. As the alphabet grows, the memory per node grows too; this cost is the weakest point of the trie.

11.2The node class

11.2.1The TrieNode class

The most direct way to build a trie in Java is to keep, in each node, a child reference for every letter of the alphabet. If the alphabet consists of lowercase English letters, an array of 26 elements in each node suffices. Cell i of the array points to the child reached from the node by the i-th letter; if there is no continuation with that letter, the cell is null.

public class TrieNode {
  TrieNode[] child;  // 'a'..'z'
  boolean isWord;      // does a word end here?

  public TrieNode() {
    isWord = false;
    child = new TrieNode[26];
  }
}

The class has two fields. The child array holds 26 references; Java initializes all reference cells of a new array to null. isWord says whether the path from the root to this node is a word of the set; it is set to false in the constructor. Java gives this value by default as well, but writing it out makes the intent clear.

The class does not store the character itself. Which character a node represents is known from the index at which it sits in its parent's array. The node in cell child[0] of the root is “a”, and the node in cell child[3] is “d”. Storing the character separately buys nothing but wasted memory. In some variants, however, such as the ternary search trie, the character has to be kept inside the node.

The trie itself is a class that holds the root. All the methods given in these notes are to be taken as written inside this class and use the root field:

public class Trie {
  private final TrieNode root = new TrieNode();
  // insert, search, startsWith, complete, delete ... live here

}
isWordfalseletterindexa0ab1⁄c2⁄d3de4⁄f5⁄g6⁄h7⁄i8⁄j9⁄k10⁄l11⁄m12⁄n13⁄o14⁄p15⁄q16⁄r17⁄s18⁄t19⁄u20⁄v21⁄w22⁄x23⁄y24⁄z25⁄
Figure 11.6: The child array of the root after and, ant, dad and do have been inserted. Of the 26 cells only 0 (a) and 3 (d) are filled; the ⁄ mark is null.

Figure 11.6 shows the root's array in full. Only two of the 26 cells are filled. This table is the first sign of the trie's memory problem. At the nodes below the root the situation is even sparser: the “an” node has 2 filled cells and the “a” node only 1. In the leaves all 26 cells of the array are empty, but the array is allocated all the same.

11.2.2From character to index

To find the index of a character in the array, we use the fact that Java's char type is a number. A char stores the UTF-16 code value of the character and is converted to int in arithmetic. The codes of the lowercase letters are consecutive: 'a' is 97 and 'z' is 122. So the expression ch - 'a' maps 'a' to 0 and 'z' to 25.

Table 11.2: The codes of some characters and their array indices.
chUnicodech − 'a'
'a'970
'd'1003
'n'11013
'o'11114
't'11619
'z'12225
031325ad'a' − 'a' = 0, 'd' − 'a' = 3root.child: the other 24 cells are null
Figure 11.7: In the root.child array, the cells 'a' − 'a' = 0 and 'd' − 'a' = 3 are filled; the other 24 cells are null.

Because a child is reached through an array index, access is O(1): node.child[ch - 'a']. For the word “and”, child[0], child[13] and child[3] are used in turn. This speed is the greatest advantage of the array representation. Finding a child needs neither a comparison nor a hash computation.

The same formula does not work for characters outside the alphabet. The code of the uppercase 'A' is 65, and 'A' - 'a' = 65 − 97 = −32. The code of the Turkish letter 'ç' is 231: 'ç' - 'a' = 231 − 97 = 134. For 'ş' the result is 351 − 97 = 254. None of these indices is in the range 0–25, and the array access throws an ArrayIndexOutOfBoundsException. There are two solutions: the input is first converted to lowercase and to the a–z alphabet, or the children are kept in a HashMap keyed by character.

Common mistake

Using ch - 'a' without checking the input. A word such as “Ankara” or “çay” causes an exception at the first character. A more insidious problem is a half-built path left in the trie when an insertion is interrupted: while “kaç” is being inserted, the 'k' and 'a' nodes are created and an exception is thrown at 'ç'. An unmarked “ka” path remains in the trie. The input must be checked before it is processed, or the alphabet must be chosen wide from the start.

11.3Insertion

11.3.1Algorithm and code

Inserting a word into a trie means walking the word's path from the root and completing the part that is missing. If the beginning of the path is shared with other words, that part already exists; insertion creates new nodes after the first missing character. When the path ends, the last node is marked.

  1. Start at the root.
  2. For each character of the word, look at the relevant child: child[ch − 'a'].
  3. If the child is null, create a new node; if it exists (a common prefix), use the existing node.
  4. Move on to that child.
  5. When the characters run out, set isWord = true at the last node.
public void insert(String word) {
  TrieNode node = root;
  for (char ch : word.toCharArray()) {
    int i = ch - 'a';
    if (node.child[i] == null)
      node.child[i] = new TrieNode();
    node = node.child[i];
  }
  node.isWord = true;
}

The code follows these five steps line by line. The variable node starts at the root and goes down one level on each iteration of the loop. toCharArray() turns the word into a character array; the for-each loop yields the characters from left to right. For each character i = ch - 'a' is computed. If node.child[i] == null, there is no path continuing with that character yet; a new TrieNode is created and attached to the cell. If the condition is false, the path already exists and nothing is created. In both cases we descend to the child with node = node.child[i]. When the loop ends, node is the node of the last character of the word, and it is marked.

One property of the code stands out: insertion never changes an existing node; it only attaches new nodes and sets the last node's marker to true. If the same word is inserted a second time, the loop finds all the nodes in place, creates no new node and sets the already true marker to true again. The structure does not change. For this reason a trie behaves like a set: repeated words are stored once.

11.3.2Step by step: and, ant, dad, do

Let and, ant, dad and do be inserted in order into an empty trie. At the start the trie consists of the root alone: all 26 children of the root are null and isWord = false. Table 11.3 gives the state of the relevant cell at each character and the work done.

Table 11.3: Inserting the words and, ant, dad, do in order. The “Node” column gives the prefix that node points to after the operation.
Wordchichild[i]ActionNode
and'a'0nullnew nodea
'n'13nullnew nodean
'd'3nullnew nodeand
———isWord = trueand ✓
ant'a'0filledmove on (common prefix)a
'n'13filledmove on (common prefix)an
't'19nullnew nodeant
———isWord = trueant ✓
dad'd'3nullnew noded
'a'0nullnew nodeda
'd'3nullnew nodedad
———isWord = truedad ✓
do'd'3filledmove on (common prefix)d
'o'14nullnew nodedo
———isWord = truedo ✓

When “and” is inserted the trie is empty; all three characters create new nodes and the last node is marked. From the root the path child[0] → child[13] → child[3] has been built.

rootandand
Figure 11.8: The trie after “and” is inserted: the root, a, an and the marked node and.

When “ant” is inserted, the first two characters find a ready path. For 'a', child[0] is filled, and for 'n', child[13] is filled; the loop only moves on. For 't', child[19] is empty and a single new node is created. The prefix “an” is shared between the two words. This sharing is the source of the trie's memory saving.

rootandandtant
Figure 11.9: “ant” inserted. Only 1 new node (t) was needed; the prefix “an” was shared.

“dad” meets an empty cell (child[3]) at the root and builds its own branch with three new nodes. Note that the two 'd's in “dad” are different nodes: one is the child of the root, the other the child of “da”. The same character corresponds to different nodes under different prefixes. Finally “do” shares the 'd' node and creates a single new node for 'o'.

rootandandtantdaddadodo
Figure 11.10: The final state: 4 words, 11 characters, 8 nodes not counting the root.

The numbers of new nodes created in the four insertions are 3, 1, 3 and 1, in that order; 8 in total. Since the total length of the words is 11, a saving of three characters has been achieved. Had the words been inserted in another order, the intermediate states would differ, but the final trie would be the same. The shape of a trie depends only on the set of words, not on the insertion order. This is an important difference from the binary search tree, where the insertion order determines the height of the tree.

11.3.3Code trace: insert("ant")

To see how the code works at the level of lines, we trace the call insert("ant") when the trie contains only “and”. Table 11.4 gives the values of the variables at each step.

Table 11.4: Trace of insert("ant"); at the start the trie contains only “and”.
StepLinechiCondition / actionnode
1node = root——startroot
2loop'a'0child[0] == null is false; no new nodea
3loop'n'13child[13] == null is falsean
4loop't'19child[19] == null is true → a new node is attachedant
5after the loop——node.isWord = trueant ✓
rootandandt
Figure 11.11: The fourth step: child[19] was found empty and the new “t” node (colored) was attached; node is still at “an”.

The trace shows three points clearly. First, the condition is true only once; that is, only one node is created. Second, at the moment a new node is created its isWord value is false; the marker is set only after the loop has ended, and only on the last node. The intermediate nodes (“a”, “an”) stay unmarked. Third, the loop always walks over all the characters of the word; insertion never ends early. That is why insertion takes exactly L iterations in every case.

11.3.4The cost of insertion

The loop runs once for each character of the word. In each iteration an index is computed, an array is accessed and, if needed, a node is created and an assignment is made. Creating a node means allocating an array of 26 cells. This takes time proportional to the alphabet size, but since the alphabet is taken as constant it is a constant cost. The total time is O(L), where L is the length of the word. The time is completely independent of the number of words in the trie.

As for memory, one insertion creates at most L new nodes; this worst case occurs when no prefix of the word is in the trie. Each node carries 26 references and a boolean, so one insertion allocates at most O(L · M) memory. If the word lies entirely on an existing path (for example, “ka” inserted when “kalem” is present), no node is created at all; only the marker changes.

Example 11.2

Question. The trie contains only “kalem” and insert("ka") is called. How many nodes are created? Then what does search("ka") return?

Solution. For 'k' the cell child[10] of the root is filled; the loop moves on. For 'a' the cell child[0] of the “k” node is filled too. The loop ends and the “ka” node is marked. No node is created. The “ka” path existed before but was not a word; now it is marked, and search("ka") returns true. “kalem” is not affected by this operation.

Common mistake

Putting the marking inside the loop. If the line node.isWord = true is moved into the loop body, “a” and “an” are marked as well when “and” is inserted. Then search("an") returns true and the trie “finds” words that were never inserted. The marker must be set only on the last node.

11.4Search and prefix queries

11.4.1The search algorithm

Search is the read-only counterpart of insertion. The same path is walked; the difference is that when a missing branch is met, no node is created and the search ends at once.

  1. Start at the root.
  2. For each character, go to the relevant branch (child).
  3. If the branch does not exist (null), the word is not in the trie.
  4. On reaching the end of the word, check isWord: if it is true, the word has been found; if it is false, the word is absent and is only a prefix of an existing word.
public boolean search(String word) {
  TrieNode node = root;
  for (char ch : word.toCharArray()) {
    int i = ch - 'a';
    if (node.child[i] == null)
      return false;
    node = node.child[i];
  }
  return node.isWord;
}

The code is almost the same as insertion. Two lines differ. First: if the child is null, no new node is created; we leave with return false. Second: after the loop ends the marker is not set but read: return node.isWord. This last line is the most important line of the search. Even if all the characters of the path have been found, the word is not in the trie unless the last node is marked.

Search also takes O(L). If the word is not in the trie, the loop may end earlier: if the path breaks at the k-th character, only k iterations run. Even with a million words in the trie, “dad” is found, or found absent, in at most 3 steps.

11.4.2Code trace: search("dad")

Let the trie consist of the words and, ant, dad and do. The trace of the call search("dad") is in Table 11.5.

Table 11.5: Trace of search("dad"); trie: and, ant, dad, do.
Iterationchichild[i]node (after)
————root
1'd'3filled, continued
2'a'0filled, continueda
3'd'3filled, continuedad
endthe word has ended; node.isWord = trueresult true
rootandandtantdaddadodo
Figure 11.12: The last step of search("dad"): node is at the “dad” node and the node is marked; the method returns true.

The same index (3) is used in the first and third iterations, but in the arrays of different nodes: the first is the root's array, the second is that of “da”. Each iteration of the search works one level further down. After three iterations the path is complete and the last node's marker is read.

11.4.3The three outcomes of a search

A search can end in three different ways. Telling the three apart is also the way to understand the difference between search and a prefix query.

rootandtdado rootandtdado rootandtdadog
Figure 11.13: From left to right: search("dad"), search("da") and search("dog"). The dashed red circle is a node that was looked for but is not in the trie.
  • search("dad") → true. All the characters are found and the last node is marked.
  • search("da") → false. The path exists, but at the “da” node isWord = false. “da” is only a prefix of “dad”. The loop completes two iterations and the last line returns false.
  • search("dog") → false. The cell child[6] of the “do” node ('g' − 'a' = 6) is null. There is no branch; the loop exits early in the third iteration. Even if “do” is a word, this does not change the result.

The second and third cases return the same value (false), but for different reasons. In the second the path is complete and what is missing is the marker. In the third the path is broken. This difference is decisive in the prefix query: the prefix query returns true in the second case and false in the third.

11.4.4Prefix query

A prefix query asks whether the trie contains at least one word that starts with the given prefix. It is the counterpart, over a set, of the startsWith method of Java's String class. In a trie this question is the same as asking whether the path of the prefix exists. Every node in the trie lies on the path of at least one word, because nodes are created only during insertion and deletion leaves no unmarked leaf. So if the path exists, there is also a word that starts with that prefix.

public boolean startsWith(String prefix) {
  TrieNode node = root;
  for (char ch : prefix.toCharArray()) {
    int i = ch - 'a';
    if (node.child[i] == null)
      return false;
    node = node.child[i];
  }
  return true;  // search: node.isWord
}

The code is the same as search; the only difference is the last line. If startsWith finishes the loop without the path breaking, it returns true and does not look at the last node's marker. The comment line spells out the difference: at this point search returns node.isWord. The time is O(P), where P is the length of the prefix.

Table 11.6: Results of search and startsWith; trie: and, ant, dad, do.
QuerysearchstartsWithExplanation
"dad"truetruepath complete, last node marked
"da"falsetruepath complete, last node unmarked
"an"falsetruepath complete, last node unmarked
"dog"falsefalseno 'g' branch after “do”

The results in the table show the one difference between the two methods: for queries that end at an unmarked node, search returns false and startsWith returns true. For queries where the path breaks, both return false.

For a code trace, take two calls: startsWith("da") and startsWith("dog"). In the first call node is set to the root. For 'd', i = 3, child[3] is filled and we descend to the “d” node. For 'a', i = 0, child[0] is filled and we descend to “da”. The prefix has ended and the path has not broken; the method returns true. Because the “da” node is unmarked, search("da") would have given false here.

danoatddroot
Figure 11.14: startsWith("da"): we descended to the “da” node without the path breaking; the result is true.

In the second call node is set to the root again. For 'd' (i = 3) and 'o' (i = 14) the cells are filled; we descend to the “do” node. For 'g', i = 6, and the cell child[6] of the “do” node is null. The method returns false. “do” is a word, but there is no word that starts with “dog”.

danoatddrootnullg
Figure 11.15: startsWith("dog"): the “do” node has no 'g' branch; the result is false.
Common mistake

Confusing search with startsWith. If return true is written on the last line of search, the method silently turns into a prefix query. It still returns false when a branch is not found, but every prefix that has a path counts as a word. This bug may not show in small tests: tests with real words such as “dad” and “and” give correct results. The bug appears only when it is tried with an unmarked prefix such as “da”. Search tests should always include at least one unmarked prefix.

11.4.5Prefix counts

startsWith says whether there is a word that starts with a prefix, but not how many. The question “how many words start with an?” requires counting the marked nodes in the subtree of the prefix node. This count walks over all the nodes of the subtree. If the subtree has S nodes and 26 cells are checked at each node, the query takes O(P + S · M). If the dictionary is large and the prefix is short (for example a single letter), this means walking a large part of the dictionary.

A better way is to do the counting during insertion. A field int count is added to the TrieNode class. This field holds the number of words passing through the node's path. Insertion starts at the root and increments the counter of every node it passes through. During a query we descend to the prefix node and read the counter.

void insert(String word) {
  if (search(word)) return;  // don't recount
  TrieNode node = root;
  node.count++;
  for (char ch : word.toCharArray()) {
    int i = ch - 'a';
    if (node.child[i] == null) node.child[i] = new TrieNode();
    node = node.child[i];
    node.count++;       // one more word passed
  }
  node.isWord = true;
}
int prefixCount(String prefix) {
  TrieNode node = root;
  for (char ch : prefix.toCharArray()) {
    node = node.child[ch - 'a'];
    if (node == null) return 0;
  }
  return node.count;
}

If the word already exists, insert returns at once because of the search check; the counters grow only for a new word. The root's counter is incremented before the loop; this way the root holds the total number of words in the trie. The line node.count++ in the loop increments the counter of every node, newly created or existing. In prefixCount, if the path breaks, 0 is returned; when the path ends, the prefix node's counter is returned. The loop descends to the child first and then checks for null; this order differs from that in search but does the same job.

addtndao11221112root
Figure 11.16: The count counters (green) in the trie of and, ant, dad, do. The root has 4, “a” and “an” have 2, “d” has 2, and “da” and “do” have 1.
Table 11.7: prefixCount queries; trie: and, ant, dad, do.
QueryResultReason
prefixCount("an")2and and ant pass through the “an” node
prefixCount("da")1only dad passes through
prefixCount("x")0the cell child[23] of the root is empty

The counter method reduces the query to O(P). Its price is one int per node; in a node of 26 references this extra memory is very small. In deletion, however, all the counters along the path must be decremented by one. If the decrement is forgotten, the counters keep counting deleted words. If the same word were inserted twice, the counters would be incremented twice; that is why insert begins with the check search(word) and returns without recounting a word that is already in the trie.

Common mistake

Incrementing the counter only at the end of the word. If the line node.count++ is taken out of the loop and run only at the last node, the counter turns into “the number of words ending at this node”. The value at the “an” node becomes 0 and prefixCount("an") gives a wrong result. The counter must be incremented at every node of the path.

11.4.6Wildcard search

A program that solves puzzles or plays word games may ask: “is there a word of the form d, an unknown letter, d?” In the pattern, a dot (.) stands for any letter. This kind of query is called wildcard search. An ordinary letter reduces the search to a single path. A dot, however, requires trying every filled branch at that level. The search is therefore written recursively.

boolean wildcard(TrieNode node, String pat, int j) {
  if (node == null) return false;
  if (j == pat.length()) return node.isWord;
  char ch = pat.charAt(j);
  if (ch != '.')
    return wildcard(node.child[ch - 'a'], pat, j + 1);
  for (int i = 0; i < 26; i++)
    if (wildcard(node.child[i], pat, j + 1)) return true;
  return false;
}

The method takes three parameters: the current node node, the pattern pat and the index j of the next character in the pattern. The first call has the form wildcard(root, pattern, 0). If the node is null, this branch does not exist and false is returned. If the pattern has ended (j == pat.length()), the result is the node's marker, just as on the last line of search. If the next character is a letter, we descend only into that letter's child. If it is a dot, each of the 26 children is tried in turn; if a match is found in one, true is passed straight up and the remaining branches are not tried. A call made for an empty child returns at once on the first line.

Table 11.8: Results of wildcard search; trie: and, ant, dad, do.
PatternResultMatch / reason
"d.d"truedad
".n."trueand (ant is never looked at)
".o"truedo
"b.."falsethe root has no 'b' branch
"...."falseno word with 4 letters
Example 11.3

Question. Which nodes does the call wildcard(root, "d.d", 0) pass through?

Solution. With j = 0, the character 'd' is a letter; we descend only to root.child[3], the “d” node. With j = 1 the character is a dot; the 26 children of “d” are tried in turn. For i = 0 the “da” node exists and wildcard(da, "d.d", 2) is called. In this call the character is 'd' and we descend to the “dad” node. j = 3 equals the length of the pattern, and since “dad” is marked, true is returned. The value is passed up; the loop at the “d” node never reaches i = 1. The “do” branch (i = 14) is not tried.

The cost depends on the pattern and the trie. If the pattern has k dots, at most 26k branches are tried in the worst case. But because empty branches return at once, the real cost is bounded by the paths that actually exist in the trie. The pattern “....” walks the whole trie down to the fourth level at most and finds no 4-letter word. A hash table can answer this query only by trying all the words one by one: there is no way to turn the pattern into a known key.

11.4.7Spell checking: edit distance on a trie

A spell checker offers suggestions for a word that is not in the dictionary. The suggestions are dictionary words “close” to the word. The measure of closeness is usually the edit distance: the smallest number of single-character insertions, deletions and substitutions needed to turn one string into the other. This measure is also called the Levenshtein distance. The distance between “dod” and “dad” is 1 (o → a). The distance between “dod” and “do” is also 1 (the last d is deleted).

The distance between two strings is computed by dynamic programming, filling in a table. Let the query string be q and the dictionary word w. Row i of the table holds the distances between the first i characters of w and all prefixes of q. A row is computed from the previous row by the following rule:

Si[0] = i,   Si[j] = min( Si[j − 1] + 1,   Si−1[j] + 1,   Si−1[j − 1] + (wi ≠ qj ? 1 : 0) )

The three terms are, in order, the cost of an insertion, a deletion and a substitution (or of a free move if the characters are equal). The last cell of the last row is the distance between the two strings.

The naive method fills a separate table for each word in the dictionary. But row i of the table depends only on the first i characters of the word. Words that have a common prefix share these rows. A trie provides exactly this sharing: each node is a prefix, and a node's row is computed from its parent's row in one step. The trie is walked depth first; one row is produced at each node. The row of the “d” node is computed once and used for both “dad” and “do”.

Pruning is added to the walk. If the smallest value of a row exceeds k, no word below this node can be within distance k of the query. Every cell of a new row is obtained, directly or through its left neighbor, by adding 0 or more to a cell of the previous row. So the smallest value of a row does not decrease as the depth increases. The subtree of such a node is not entered.

Table 11.9: Query “dod”, k = 1; trie: and, ant, dad, do. The columns of a row are the prefixes “”, d, o, d, in order. The “Last” column is meaningful only at word nodes.
Node“” d o dMinimumLastDecision
(root)0 1 2 30—initial row
a1 1 2 31—continue
an2 2 2 32—prune (minimum 2 > 1)
d1 0 1 20—continue
da2 1 1 21—continue
dad3 2 2 111suggest
do2 1 0 101suggest
Example 11.4

Question. How are the rows of “a” and “dad” computed, starting from the root's row?

Solution. The root's row holds the distances between the empty prefix and the prefixes of “dod”: 0, 1, 2, 3. In the row of “a” the first cell is 1. The second cell is min(1 + 1, 1 + 1, 0 + [a ≠ d]) = min(2, 2, 1) = 1. The third cell is min(1 + 1, 2 + 1, 1 + [a ≠ o]) = 2. The fourth cell is min(2 + 1, 3 + 1, 2 + [a ≠ d]) = 3. The row is 1, 1, 2, 3. The row of “dad” is computed from the row of “da” (2, 1, 1, 2): the first cell is 3; then min(4, 2, 2 + 0) = 2; min(3, 2, 1 + 1) = 2; min(3, 3, 1 + 0) = 1. The row is 3, 2, 2, 1, and the last cell, 1, is the distance between “dad” and “dod”.

At the end of the walk the suggestions are dad (o → a) and do (the last d is deleted). The minimum of the “an” row is 2, which exceeds 1; the “and” and “ant” nodes are never entered. Indeed the distance between “and” and “dod” is 2, and that with “ant” is 3. The nodes visited are a, an, d, da, dad and do. Each row costs O(|q|) work. Thanks to pruning, most of a large dictionary is never visited. The same walk also works with a weighted distance that counts neighboring letters on the keyboard as cheaper. But as k grows, pruning weakens and the number of visited nodes rises quickly; in applications k is mostly chosen as 1 or 2.

11.5Autocomplete and the longest common prefix

11.5.1complete and collect

Autocomplete suggests possible words according to the prefix typed. In a trie this is done in two phases. First the prefix node is found; this step is the same as the prefix query. Then the subtree of this node is walked depth first, and the word of every marked node is added to the list.

List<String> complete(String prefix) {
  List<String> result = new ArrayList<>();
  TrieNode node = findNode(prefix);
  if (node != null)
    collect(node, new StringBuilder(prefix), result);
  return result;
}
void collect(TrieNode node, StringBuilder path,
             List<String> result) {
  if (node.isWord) result.add(path.toString());
  for (int i = 0; i < 26; i++)
    if (node.child[i] != null) {
      path.append((char) ('a' + i));
      collect(node.child[i], path, result);
      path.setLength(path.length() - 1);
    }
}

complete first looks for the prefix node with the helper findNode. The helper is the version of startsWith that returns the node itself instead of a boolean:

TrieNode findNode(String prefix) {
  TrieNode node = root;
  for (char ch : prefix.toCharArray()) {
    node = node.child[ch - 'a'];
    if (node == null) return null;  // path broke
  }
  return node;
}

If there is no prefix node, findNode returns null and complete gives an empty list. If the node exists, collect is called. The path parameter of collect is a StringBuilder that holds the string from the root to the current node; at the start it is the prefix itself. The method first looks at the node's marker: if the node is an end of word, the current value of path is added to the result. Then the 26 indices are walked in turn. For each filled child three things are done: the child's character is appended to path, collect is called recursively for the child, and when the call returns, the appended character is removed.

The last step, path.setLength(path.length() - 1), is a backtracking step. All calls share the same StringBuilder object. If, when returning from a subtree, the character appended for that subtree is not removed, the next sibling's word is built with a wrong prefix. Each call leaves path as it was handed to it.

11.5.2Code trace: complete("te")

Let the trie consist of the words a, to, tea, ted, ten, i, in and inn. This is the lowercase version of the trie that carries values. We trace the call complete("te").

rootaaiininninnteateadtedntenoto
Figure 11.17: findNode("te") finds the “te” node by descending t → e from the root.
Table 11.10: Trace of complete("te"). The indentation shows the recursion depth.
StepCall / actionpathresult
1findNode("te") → the “te” nodete[]
2collect(te): unmarked, not addedte[]
3  i = 0 ('a') filled → append, collect(tea)tea[]
4    “tea” marked → added; no childrentea[tea]
5  return, last letter removedte[tea]
6  i = 3 ('d') filled → collect(ted)ted[tea, ted]
7  return, last letter removedte[tea, ted]
8  i = 13 ('n') filled → collect(ten)ten[tea, ted, ten]
9  return, last letter removed; the loop endste[tea, ted, ten]
rootaaiininninnteateadtedntenoto
Figure 11.18: The result of complete("te"): [tea, ted, ten]. Only the subtree of the “te” node was walked; the faded nodes were never looked at.

The result is [tea, ted, ten] and is in alphabetical order. This order is no coincidence: the loop walks the indices from 0 to 25, and index order is letter order (a < d < n). Moreover, a node is added to the list before its children; so a prefix comes before the words that extend it. The output is the same whatever order the words were inserted into the trie.

The cost has two parts. Finding the prefix node takes O(P). If the subtree has S nodes, each is visited once and 26 cells are checked at each visit: O(S · M). The total is O(P + S · M). In addition, toString() makes a copy for each word found; the total length of these copies is the size of the output. If the prefix is short, the subtree can be large. That is why applications usually settle for the first few suggestions. To show the most frequently used words first, a usage frequency is also stored in the nodes.

Example 11.5

Question. The words bal, ba, bas, bat and baba were inserted in that order. What do complete("ba"), complete("bx") and complete("bas") return?

Solution. “ba” is marked and is added to the list first. Then the children are walked in index order: b (1), l (11), s (18), t (19). The result is [ba, baba, bal, bas, bat]. The “bx” node does not exist, findNode returns null and the result is an empty list. “bas” is marked and has no children: [bas].

Common mistake

Forgetting to backtrack. If the line path.setLength(...) is deleted, the characters 'a', 'd', 'n' pile up at the “te” node. The result becomes [tea, tead, teadn]. After every recursive call, shared state must be restored to what it was before the call.

11.5.3The longest common prefix

The longest common prefix of a set of strings is the longest beginning that all the strings in the set share. In a trie this prefix is a chain of single branches starting at the root. We descend from the root; if the node has a single child and is not the end of a word, we move on. The characters passed are the answer.

String longestCommonPrefix() {
  StringBuilder sb = new StringBuilder();
  TrieNode node = root;
  while (!node.isWord) {
    int only = -1, kids = 0;
    for (int i = 0; i < 26; i++)
      if (node.child[i] != null) { kids++; only = i; }
    if (kids != 1) break;  // fork or leaf
    sb.append((char) ('a' + only));
    node = node.child[only];
  }
  return sb.toString();
}

The loop condition is !node.isWord: we stop on reaching a marked node. In the loop body the 26 cells are counted; kids holds the number of filled cells and only the last filled index seen. If kids is not 1 (if it is 0 we have reached a leaf, if 2 or more a fork), the loop is broken. If there is a single child, its character is appended and we descend to the child.

Table 11.11: Trace of longestCommonPrefix(); trie: kar, kart, karton.
Node nodeisWordkids, onlyActionsb
rootfalse1, 10 ('k')'k' appendedk
kfalse1, 0 ('a')'a' appendedka
kafalse1, 17 ('r')'r' appendedkar
kartrue—the loop endskar
kartonrootkkakarkartkartokarton
Figure 11.19: The trie of kar, kart, karton is a single chain. The descent stops at the “kar” node, because “kar” is a word.

The “kar” node has a single child (t), but the descent stops there. Why? A common prefix must be a prefix of every word in the set. The word “kar” itself cannot have a prefix longer than “kar”. Without the marker check in the condition, the descent would continue to “karton” and wrongly return “karton”. If the trie held only kart and karton, the descent would continue to “kart” and there isWord would stop it: the answer would be “kart”.

The cost is O(P · M), where P is the length of the answer: 26 cells are counted at each level. If the root has more than one child, the loop breaks in the first iteration and the answer is the empty string; for example, the set and, ant, dad, do has no common prefix.

11.6Deletion

11.6.1Three cases

Deletion is the trie operation that needs the most care. The path of a word may be shared with other words. Deleting the path from start to end would also destroy the other words that share the prefix. Deletion must therefore remove only the nodes that are specific to the word. Three cases arise, depending on the word's position in the trie.

androotan: marker removed androotdeleted dorootno g
Figure 11.20: The three cases of deletion. Left, “an” is deleted: only the marker is removed. Middle, “ant” is deleted: the t node is removed and we stop at the prefix “an”. Right, “dog” is looked for: the word is not in the trie.
  1. The word is a prefix of another word. The last node has children. Only isWord = false is set; the node is not deleted, because it lies on the path of other words.
  2. The word has a tail of its own. From the end back toward the start, nodes that have no children and are unmarked are deleted. We stop on reaching a shared prefix or the end of another word.
  3. The word is not in the trie. A branch is not found or the last node is unmarked. Nothing changes.

The “tail” in the second case is the chain of nodes, going up from the word's last node, that serve only this word. A node can be deleted if two conditions hold together: it has no children and it is unmarked. If it has children, it is on the path of another word. If it is marked, it is itself a word. The tail ends at the first node that breaks one of these two conditions.

Example 11.6

Question. The trie holds “apple” and “app”. How does the structure change when “app” is deleted?

Solution. The second 'p' node, the last node of “app”, has a child: 'l'. “apple” continues below this node. The node cannot be deleted; only its marker is removed (case 1). After that search("app") returns false and search("apple") returns true. The number of nodes does not change.

11.6.2Step by step: app, apple, apt

Let the trie consist of the words app, apple and apt. Apart from the root there are 6 nodes: a, ap, app, appl, apple, apt. Both scenarios below start from this initial trie.

rootappappleappletapt
Figure 11.21: The trie of the words app, apple and apt.

Scenario 1: delete("app"). The path a → p → p is followed. The “app” node is marked, that is, the word exists. The marker is removed: isWord = false. Because the node has an 'l' child, it is not deleted. This is case 1. “apple” can still be found; the number of nodes stays at 6.

Scenario 2: delete("apple"). The path a-p-p-l-e is followed and “apple” is found. The marker of the 'e' node is removed. This node has no children; its parent deletes it (child[4] = null). Then the 'l' node is examined: it is now childless and unmarked, so it is deleted too. Next we come to the “app” node. This node is marked, because “app” is another word. The deletion stops here.

rootappappletapt rootappappltapt rootappapptapt
Figure 11.22: delete("apple"): first the 'e', then the 'l' node is deleted; we stop at the marked “app” node. Result: app and apt, 4 nodes not counting the root.

The two scenarios show that deletion decisions are made from the bottom up. Whether a node is deleted depends on whether its children are deleted. The 'l' node could not have been deleted at first, because it had the child 'e'. After 'e' was deleted, 'l' became deletable. This dependence is why deletion is naturally written recursively: first we descend to the end of the word, and the decisions are made on the way back.

11.6.3Recursive code

// true: parent may drop node
boolean delete(TrieNode node, String word, int j) {
  if (j == word.length()) {    // word ended
    if (!node.isWord) return false;
    node.isWord = false;
    return isEmpty(node);       // no children?
  }
  int i = word.charAt(j) - 'a';
  TrieNode next = node.child[i];
  if (next == null) return false;  // no such word
  if (delete(next, word, j + 1)) {
    node.child[i] = null;       // unlink child
    return !node.isWord && isEmpty(node);
  }
  return false;
}

The method's return value is a decision passed to the parent: true means that the parent may delete this node. The call has the form delete(root, word, 0); the root's return value is ignored, because the root is never deleted. j is the index of the next character in the word.

The method has two parts. The first is the base case: if j == word.length(), we have reached the word's last node. If the node is unmarked, the word is not in the trie and false is returned (case 3). If it is marked, the marker is removed and we check whether the node has children. If it has none, true is returned: the parent may delete this node. If it has children, false is returned (case 1).

The second part is the recursive case. The child next for the next character is found. If next is null, the word is not in the trie and false is returned (case 3). If it exists, delete(next, word, j + 1) is called. If the call returns true, the child can be deleted: the link is cut with node.child[i] = null. Then the same question is asked about this node: is it unmarked and now childless? The answer is passed up one level. If the call returns false, nothing is deleted and false is passed up. Once the chain is broken at one level, no node above is deleted. In a trie with prefix counters, the word's existence is first checked with search; if the word exists, node.count-- is done at every node during the descent.

The code uses the helper isEmpty. The helper checks whether all 26 cells are null:

boolean isEmpty(TrieNode node) {
  for (int i = 0; i < 26; i++)
    if (node.child[i] != null) return false;
  return true;
}

In Java, “deleting” a node means setting the last reference to it to null. The detached node is no longer reachable and the garbage collector reclaims its memory. That is why the code only empties the cell in the parent.

11.6.4Code trace: delete("dad")

Let the trie consist of the words and, ant, dad and do. We trace the call delete(root, "dad", 0). The recursion first descends three levels, and decisions are made on the way back. Table 11.12 gives the descent and return steps in order.

Table 11.12: Trace of delete(root, "dad", 0); trie: and, ant, dad, do. The frame is the call's node.
StepFramejActionReturns
1root0'd' → i = 3, next = “d”; delete(d, "dad", 1)—
2d1'a' → i = 0, next = “da”; delete(da, "dad", 2)—
3da2'd' → i = 3, next = “dad”; delete(dad, "dad", 3)—
4dad3j == word.length(); marked → isWord = false; isEmpty(dad) = truetrue
5da2child[3] = null; “da” is unmarked and childlesstrue
6d1child[0] = null; “d” is unmarked but has the child 'o'false
7root0the call returned false; the root deletes nothingfalse
danoatddroot danotdroot
Figure 11.23: Left, the fourth step: the marker of the “dad” node has been removed. Right, the result: the “dad” and “da” nodes have been detached; the remaining words are and, ant, do.

Two nodes are deleted in the trace: “dad” and “da”. The “d” node is unmarked, but it has the child 'o' for “do”; isEmpty returns false and the chain breaks there. The call at the root gets false and the root's return value is ignored. The remaining trie holds the words and, ant and do; apart from the root there are 6 nodes.

The cost of deletion is computed as follows. The descent takes L levels. On the way back at most one isEmpty call is made per level, and each scans 26 cells. The total is O(L · M). If each node held a counter for its number of filled children, isEmpty would answer in constant time and deletion would drop to O(L). This counter is incremented when a cell is filled during insertion and decremented when a cell is emptied during deletion.

Common mistake

Deleting a shared node. Deletion is sometimes written as “every node on the word's path, from the root on, is set to null”. In a trie that holds app, apple and apt, this version empties the root's 'a' cell on the call delete("app"). All three words that begin with a are lost. A correct deletion only removes the marker and deletes, from the bottom up, nodes that are childless and unmarked. Because “app” has an 'l' child, no node is deleted.

Common mistake

Skipping the marker check on the way back. If the condition !node.isWord && in the recursive part is removed, the call delete("apple") deletes the “app” node too, because after 'l' is detached “app” is left childless. The word “app” is thereby lost. A node can be deleted only if it is childless and unmarked.

11.7Analysis

11.7.1Complexity

The cost of trie operations depends on two quantities: the length of the string being processed and the size of the alphabet. L is the length of the word and P the length of the prefix. M is the alphabet size; for lowercase English letters it is 26. S is the number of nodes in the subtree of the prefix node.

Table 11.13: Running times of the operations in an array-based trie.
OperationTimeExplanation
insert(word)O(L)one step per character; at most L new nodes
search(word)O(L)ends earlier if a branch is missing
startsWith(prefix)O(P)the existence of the path is enough
prefixCount(prefix)O(P)with the count counter
complete(prefix)O(P + S · M)depth-first walk from the prefix node
delete(word)O(L · M)isEmpty scans 26 cells; O(L) with a child counter

The most important feature of the table is that a quantity is missing: in no row is there an n, the number of stored words. The log n factor of the binary search tree does not appear in a trie. Even if the trie stores a million words, the search for “dad” takes 3 steps. This also explains why it is wrong to state the cost of trie operations as O(log n) or O(n).

It should not be forgotten, though, that L has a limit too. If a dictionary has n distinct words and the alphabet has M letters, at least some of the words must have a length of order logM n. With a short alphabet, a large number of distinct words can be built only from long words. Still, in real dictionaries L is small (most English and Turkish words are shorter than 15 letters) and the advantage of the trie holds in practice.

The memory requirement is O(N · M). N is the number of nodes, and is at most the total length of all the words plus 1 (the root). This bound is reached when no word shares a prefix with another. Since each node carries an array of M references, the total memory is proportional to N · M.

11.7.2Memory: a numeric example

Let us count the memory one item at a time for the trie of the words and, ant, dad and do.

Table 11.14: Memory breakdown of the trie of and, ant, dad, do.
QuantityValue
Total characters3 + 3 + 3 + 2 = 11
Number of nodes N1 (root) + 8 = 9
Child references9 × 26 = 234
Filled references8 (the number of edges)
Empty (null) references226 (≈ 97%)
rootandandtantdaddadodo
Figure 11.24: The trie of and, ant, dad, do: the root and 8 nodes, 8 edges.

The number of filled references equals the number of edges, because each edge is represented by exactly one filled cell. Since every node other than the root has a single parent in the tree, the number of edges is N − 1 = 8. The remaining 234 − 8 = 226 cells are empty; the ratio 226 / 234 ≈ 0.966, about 97%. Common prefixes have reduced the 11 characters to 8 nodes, but arrays of 26 elements fill almost all of the memory with null.

At a larger scale the picture is more striking. A trie of a million nodes holds 26 million references. On a 64-bit Java virtual machine a reference is 8 bytes, or 4 bytes if compressed references are on. The reference arrays alone are 26 · 106 · 8 ≈ 208 · 106 bytes, about 200 MB; with 4-byte references about 100 MB. To this is added the header information of each object. The problem worsens as the alphabet grows. The basic plane of Unicode has 65,536 characters; allocating an array of that size in every node is clearly impossible.

11.7.3Strengths and weaknesses

The strengths of the trie are as follows:

  • Fast prefix-based search. Prefix queries, prefix counts and autocomplete are natural operations.
  • Word search takes O(L) and the time is independent of the number of words.
  • Common prefixes are stored once. In sets with a lot of prefix sharing (dictionaries, URLs, file paths) the number of nodes stays far below the total number of characters.
  • Order information is preserved. A depth-first walk yields the words in lexicographic order. There is no such thing as a hash collision; the worst case is also O(L).

Its weaknesses are also clear:

  • High memory consumption, especially with large alphabets. The space complexity is O(N · M).
  • No gain for sets with few common prefixes. With random keys almost every character creates a new node.
  • Many small objects. A search jumps between nodes that are far apart in memory. The processor's cache copes poorly with this access pattern. For this reason, between two structures of the same order, the trie may be slower in practice.

11.7.4Ways of storing children

The logic of a trie is independent of how the children are stored. All that changes is how the operation “give me the child with character ch” is carried out. There are four common options.

Table 11.15: Ways of storing children.
RepresentationChild accessMemory per nodeNote
TrieNode[26] arrayO(1)M referencessimple, fast; wasteful for sparse nodes
HashMap<Character, TrieNode>O(1) avg.as many as there are childrenworks for any alphabet (Turkish, Unicode); order is not preserved
TreeMap / sorted listO(log M)as many as there are childrenalphabetical traversal is preserved
Ternary search trie (TST)O(log M) avg.3 referencessmaller / equal / larger links in each node
array: 26 referencesa and d filled, 24 cells wastedHashMap: only 2 entries'a' → node'd' → node
Figure 11.25: The array representation allocates 26 cells in every node; a HashMap stores only the children that exist.

The HashMap representation also solves the problem of characters outside the a–z alphabet, such as Turkish letters. The key is the character itself; there is no index computation. The insertion code becomes shorter:

class MapNode {
  Map<Character, MapNode> child = new HashMap<>();
  boolean isWord;
}

void insert(String word) {
  MapNode node = root;
  for (char ch : word.toCharArray())
    node = node.child.computeIfAbsent(ch, x -> new MapNode());
  node.isWord = true;
}

computeIfAbsent creates a new value with the given function and adds it if the key is not in the map, and returns the value; if the key exists, it returns the existing value. So the two steps of the array version, “create if null, then descend”, shrink to a single call. “çay”, “çam”, “şeker” and “Ankara” can be inserted into this trie; the root's map then has the keys 'A', 'ç' and 'ş'. The price is a map object and a hash computation at every node. Also, because a HashMap keeps its keys unordered, the alphabetical output of autocomplete is lost. If sorted output is required, a TreeMap is used; access rises to O(log M).

The choice is made by three questions: how large is the alphabet, how tight is the memory, is sorted output needed? For a small, fixed alphabet an array is fastest. For a large alphabet or one not known beforehand, a map is needed. If memory is the most important constraint, a ternary search trie or a compressed trie is preferred.

11.7.5Trie, hash table and balanced BST

Three structures are often compared for storing string keys. Table 11.16 gives the typical costs for a set of n words of length L.

Table 11.16: Trie, hash table and balanced binary search tree (BST). S: the number of nodes in the subtree of the prefix node.
OperationTrieHash tableBalanced BST
Exact word searchO(L)O(L) averageO(L · log n)
Prefix queryO(P)not supportedO(P · log n)
k words starting with a prefixO(P + S · M)scan the whole tableO(P · log n + k · L)
Sorted listingDFS, O(N · M)sorting neededinorder traversal, O(n)
Worst caseO(L)O(n · L) (collisions)O(L · log n)
Memoryhighlowlow

For exact word search the trie and the hash table are of the same order. This may look surprising at first, since a hash table is often quoted as “O(1)”. But that O(1) holds when the key's hash value is taken as already computed. To compute the hash value of a string, all L characters are read. The equality check also compares L characters. So the hash table is also O(L). In a balanced BST, log n nodes are visited and two strings are compared at each visit; this comparison reads at most L characters.

The real difference of the trie is in prefix and order queries. A hash table supports prefixes not at all. Because a BST is sorted, it keeps the words that start with a prefix in a consecutive range and finds the start of the range in O(P · log n). A trie answers the same question without the log n factor. In return the trie is the most expensive structure in memory. The choice depends on the kind of queries to be made: if only exact matches are needed, a hash table is enough; if prefix and order queries are frequent, the trie comes to the fore.

Example 11.7

Question. A trie holds n = 1,000,000 words; the word searched for has length L = 8. How many node steps does search take in the worst case? What is the situation in a balanced BST?

Solution. In the trie one descends to a child for each character; at most 8 steps are taken. In a balanced BST, log2 106 ≈ 19.9, that is about 20 nodes are visited. At each visit at most 8 characters are compared; in the worst case about 20 · 8 = 160 characters are read. In a plain list the words are tried one by one and the work is O(n · L).

11.7.6Sorting with a trie

The trie's property of yielding words in lexicographic order can be turned into a sorting algorithm. Let the input order be dog, ant, do, and, dad. All the words are inserted into the trie. Then a preorder traversal is made from the root: first the node itself is processed, then its children are visited in order from 'a' to 'z'. At every marked node the word is written. This traversal is the same as calling collect from the root.

addtngdao12354root
Figure 11.26: The trie of the words dog, ant, do, and, dad. The green numbers are the order in which the words are written in a preorder traversal.

The output is and, ant, dad, do, dog. Two rules guarantee this order. First, siblings are visited in index order, that is, in alphabetical order: all words in the “a” branch come before those in the “d” branch. Second, a node is written before its children: “do” comes before “dog”. This agrees with the definition of lexicographic order: a prefix is smaller than every string that extends it.

For the cost, let the total number of characters be N. Insertion takes O(N) in all. The traversal checks 26 cells at each node: O(N · M). With a fixed alphabet this is O(N). Comparison-based sorting, on the other hand, makes O(n log n) comparisons and each comparison can take O(L); with words that have long common prefixes, the same characters are read again and again. The trie removes this repetition. The same idea underlies “burst sort” and the string versions of MSD radix sort. MSD radix sort also splits the words into buckets by the first character and divides each bucket by the second character; this tree of divisions is in fact a trie.

11.8Applications and variants

11.8.1Areas of use

The basic operations of the trie are the core of many real applications. Four areas stand out.

  • Autocomplete. Search boxes and integrated development environments (IDEs) descend to the node of the typed prefix and suggest the words in the subtree. If usage frequency is also stored in the nodes, frequently used words are shown first.
  • Spell checking. The dictionary is kept in a trie. If a word is not found, close words are searched for on the trie with small edits (insertion, deletion, substitution); the edit distance rows are computed while the trie is walked.
  • IP routing. Longest prefix match is done with a binary trie whose alphabet is {0, 1}. A packet's address is directed to the longest matching one among the prefixes in the routing table.
  • Word games and T9. A program that solves Boggle or a word puzzle builds paths from letters. If the path being built is a prefix of no word, the search in that direction is cut off at once; this pruning is done with startsWith. The T9 system on old phones also uses a trie-like structure to suggest words from a sequence of keys.

11.8.2The binary trie and longest-prefix match

Internet routers decide where to send a packet by looking at the packet's destination address. The routing table stores not individual addresses but address prefixes. A route of the form “0*” covers all addresses that begin with 0, and “011*” those that begin with 011. An address may match more than one prefix; the rule is to choose the longest prefix match. The longer prefix is a more specific route and takes priority over the general route.

Let the routes be 0* → A, 01* → B, 011* → C, 1* → D and 110* → E. Each route is stored in the binary trie at the node that represents the prefix. The node class carries an array with two children and a route field; adding a route is the same as ordinary insertion:

class BitNode {
  BitNode[] child = new BitNode[2];  // '0' and '1'
  String route;                        // null: no route
}

void addRoute(String prefix, String route) {
  BitNode node = root;
  for (char b : prefix.toCharArray()) {
    int i = b - '0';
    if (node.child[i] == null) node.child[i] = new BitNode();
    node = node.child[i];
  }
  node.route = route;
}

The longest match for an address is found as follows. We start at the root and follow the bits of the address in order. At every node along the path that carries a route, the route is remembered. When the path breaks or the address ends, the last remembered route is the answer. The last route seen is the deepest among those seen on the path, that is, the longest prefix.

String longestMatch(String addr) {
  BitNode node = root;
  String best = null;
  for (int k = 0; k < addr.length(); k++) {
    if (node.route != null) best = node.route;  // longer prefix
    node = node.child[addr.charAt(k) - '0'];
    if (node == null) return best;
  }
  return node.route != null ? node.route : best;

}

In each iteration of the loop, the current node's route is checked first; if there is one, best is updated. Then we descend to the child according to the k-th bit of the address: addr.charAt(k) - '0' turns the character '0' into 0 and '1' into 1. If there is no child, the best route remembered is returned. If the loop processes all the bits, the last node's route is also checked: if it has one, that is returned, otherwise best.

Table 11.17: Trace of longestMatch; routes 0* → A, 01* → B, 011* → C, 1* → D, 110* → E.
AddressNodes visited (route)Reason for stoppingResult
0110root, 0 (A), 01 (B), 011 (C)k = 3: no '0' branchC
1001root, 1 (D)k = 1: no '0' branchD
1101root, 1 (D), 11 (—), 110 (E)k = 3: no '1' branchE
011110rootABCDEno 0routes0* → A01* → B011* → C1* → D110* → E 011110rootABCDEno 1routes0* → A01* → B011* → C1* → D110* → E
Figure 11.27: Left, the address 0110: we descend 0 → 01 → 011, there is no '0' branch; the last route seen is C. Right, the address 1101: “11” is an intermediate node with no route; the E at “110” is chosen.

For the address 0110, best becomes A, B and C in turn. Each new route is a longer prefix than the previous one and takes its place. For the address 1001 only D is seen; since there is no more specific route, the general route is used. For the address 1101 the “11” node is only on the path and does not change best. The number of steps is bounded by the length of the address: for a 32-bit IPv4 address at most 32 steps are taken, however many routes the routing table holds.

Real routers speed this idea up with compressed binary tries (Patricia) and hardware support, but the basic principle is the same. Had the prefix table been kept in a hash table, a separate lookup would have been needed for every possible prefix length.

11.8.3The maximum XOR pair

A less well-known use of the binary trie concerns bit operations. The question is: in an array of numbers, which pair makes the value a ⊕ b largest? ⊕ is the bitwise exclusive or (XOR): if two bits differ the result is 1, if they are the same it is 0. Let the array be [3, 10, 5, 25, 2, 8]. Brute force tries all pairs: n(n − 1)/2 pairs for n numbers.

The trie method inserts the numbers, starting from the most significant bit, into a binary trie of fixed length (here 5 bits). Then for each x we descend from the root and at every bit choose the branch that is the opposite of that bit of x; if there is no such branch, the same bit is chosen of necessity. At every level where the opposite bit is chosen, that bit of the result is 1.

int maxXor(int[] a, int B) {
  BitNode root = new BitNode();
  for (int x : a) {                       // insert with B bits
    BitNode node = root;
    for (int b = B - 1; b >= 0; b--) {
      int bit = (x >> b) & 1;
      if (node.child[bit] == null) node.child[bit] = new BitNode();
      node = node.child[bit];
    }
  }
  int best = 0;
  for (int x : a) {                       // seek opposite bits
    BitNode node = root;
    int y = 0;
    for (int b = B - 1; b >= 0; b--) {
      int bit = (x >> b) & 1;
      if (node.child[1 - bit] != null) { node = node.child[1 - bit]; y |= (1 - bit) << b; }
      else { node = node.child[bit]; y |= bit << b; }
    }
    best = Math.max(best, x ^ y);
  }
  return best;
}

The correctness of the greedy choice rests on a property of binary numbers. In a number, a 1 in a high bit is worth more than all the lower bits together: 2b > 2b−1 + … + 2 + 1 = 2b − 1. So getting a 1 in a high bit pays off whatever is lost in the lower bits. At every level, choosing the opposite branch when possible is the right decision.

numberbinary (5 bits)300011100101050010125110012000108010005 ⊕ 2511100 = 28
Figure 11.28: The 5-bit representation of six numbers. The XOR of 5 and 25 is 11100 = 28, the largest value in the array.
Example 11.8

Question. For x = 5 = 00101, which path is followed in the trie and which number is reached?

Solution. The bits wanted are the opposite of 5: 11010. At bit 4 a 1 is wanted; only 25 (11001) has this branch and we descend. At bit 3 a 1 is wanted; the bit of 25 is 1, so it exists. At bit 2 a 0 is wanted; the bit of 25 is 0, it exists. At bit 1 a 1 is wanted; only 25 is left and its bit is 0, so we are forced to descend to 0. At bit 0 a 0 is wanted; the bit of 25 is 1, so we are forced to descend to 1. The number reached is 11001 = 25, and 5 ⊕ 25 = 00101 ⊕ 11001 = 11100 = 28. Doing the same for all the numbers, the largest value found is 28.

Table 11.18: Cost of the two methods for maximum XOR; n = 105, B = 30 bits.
MethodTimeAmount of work
All pairsO(n2)n(n − 1)/2 ≈ 5 · 109 operations
Binary trieO(n · B)insertion and query, 2 · n · B ≈ 6 · 106 steps

The trie method walks B levels twice for each number: once when inserting, once when querying. The difference is about a thousandfold. Here the trie's “length” parameter is the number of bits of the number, B.

11.8.4The ternary search trie

One solution to the memory problem of the array representation is the ternary search trie (TST). In a TST each node carries a character and three links: left (smaller), mid (equal, move on to the next character) and right (larger). The left and right chains of a node form a small binary search tree for the sibling children of an ordinary trie. The middle link corresponds to the trie's step “go down one level”. The end of a word is marked at the node.

class TstNode {
  char c;                    // the node's character
  boolean end;               // does a word end here?
  TstNode left, mid, right;
  TstNode(char c) { this.c = c; }
}

TstNode insert(TstNode node, String s, int i) {
  char ch = s.charAt(i);
  if (node == null) node = new TstNode(ch);
  if (ch < node.c) node.left = insert(node.left, s, i);
  else if (ch > node.c) node.right = insert(node.right, s, i);
  else if (i < s.length() - 1) node.mid = insert(node.mid, s, i + 1);
  else node.end = true;
  return node;
}

Insertion is recursive. If there is no node, a new node is created with the next character. If the character is smaller than the node's, we go left; if larger, right; in these two cases i does not change, because a sibling for the same character is being sought. If the characters are equal and the word has not ended, we go to the middle and i increases by one. If they are equal and it is the last character, the node is marked.

<===<>>=katarlsve
Figure 11.29: The ternary search trie of the words kar, kal, at, ve, kas. The solid line is the middle (=) link, the dashed lines are the left (<) and right (>) links.

The TST in the figure was built by inserting the words in the order kar, kal, at, ve, kas. The first word “kar” forms the k → a → r spine. “kal” follows this spine up to “ka”; since 'l' < 'r', it is attached to the left of 'r'. “at” goes to the left of the root because 'a' < 'k' at the root, and “ve” to the right because 'v' > 'k'. “kas” descends to 'r' and is attached to the right since 's' > 'r'. The insertion order changes the shape: the word inserted first becomes the spine.

Table 11.19: Memory comparison of the two representations for kar, kal, at, ve, kas.
StructureNodesLinks
Trie with 26-element arrays (including root)1010 × 26 = 260
TST99 × 3 = 27

The array trie has the root and the nodes k, ka, kar, kal, kas, a, at, v, ve; 10 nodes allocate 260 references. The TST has no empty root; each character is a node, and 9 nodes carry only 27 links. The difference is about tenfold.

boolean search(String s) {
  TstNode node = root;
  int i = 0;
  while (node != null) {
    char ch = s.charAt(i);
    if (ch < node.c) node = node.left;
    else if (ch > node.c) node = node.right;
    else if (i == s.length() - 1) return node.end;
    else { node = node.mid; i++; }
  }
  return false;
}

Search is written iteratively. i is the index of the next character in the word. If the character is smaller than the node's, we go left; if larger, right, and i does not change. If equal there are two cases: if it is the last character the node's marker is returned, otherwise we descend to the middle and i increases. When a link is null the loop ends and false is returned.

Table 11.20: Trace of search("kas") and search("al") in the TST.
Callnode.cch, iDecision
search("kas")kk, 0equal, not last → mid, i = 1
aa, 1equal → mid, i = 2
rs, 2's' > 'r' → right, i unchanged
ss, 2equal and last index → node.end = true
search("al")ka, 0'a' < 'k' → left
aa, 0equal, not last → mid, i = 1
tl, 1'l' < 't' → left; the link is null → false
<===<>>=katarlsve
Figure 11.30: The last step of search("kas"): k → a → r → s; 4 nodes were visited for 3 characters.

In the search for “kas”, 4 nodes are visited for 3 characters: three are middle steps, and one is the right step taken to find 's' among the siblings of “r”. In general, a search in a TST is the sum of L middle steps and the binary search steps among siblings at each level. If the words are inserted in random order, the average cost is O(L + log n). If the words are inserted in sorted order, the sibling trees degrade: in a TST built by inserting at, kal, kar, kas, ve in that order, 'k' is placed to the right of 'a', 'v' to the right of 'k', and the siblings 'l', 'r', 's' form a chain. This is the same problem as inserting sorted keys into a binary search tree. In their 1997 work, Bentley and Sedgewick studied the TST in detail as a structure that keeps a balance between memory and speed for large alphabets (for example Unicode).

11.8.5The compressed trie

In a standard trie most nodes have a single child. The part of the word “karton” after “kar” is a chain of the nodes “t”, “o”, “n”, each with a single child. These chains contain no decisions; they only carry characters in order. A compressed trie (radix tree) merges chains of single-child, unmarked nodes into a single edge. An edge now carries not a single character but a substring.

rootandandtantdaddadodo anddtadorootandantdaddo
Figure 11.31: The words and, ant, dad, do. Left, the standard trie: 8 nodes not counting the root. Right, the compressed trie: 6 nodes; the edges carry substrings such as “an” and “ad”.

In the figure the “a” node has a single child and is unmarked; “a” and “an” merge into a single “an” edge. The “an” node stays because it has two children. The “da” node is also single-child and unmarked; the path from “d” to “dad” becomes the edge “ad”. The “d” node stays because it has two children. In the end, apart from the root, the nodes an, and, ant, d, dad and do remain.

Theorem 11.1 (Size of a compressed trie)

A compressed trie of n words has at most 2n − 1 nodes, not counting the root.

After compression, every node other than the root is either marked or has at least two children; single-child unmarked nodes have been merged. The number of marked nodes equals the number of words: n. Every leaf is marked; so the number of leaves is at most n. In any rooted tree, the number of nodes with at least two children is smaller than the number of leaves: each such node adds at least one to the leaf count. Hence the unmarked nodes with at least two children number at most n − 1. The total is at most n + (n − 1) = 2n − 1. □

The theorem says that the number of nodes is O(n) regardless of the length of the words. In a standard trie, by contrast, the number of nodes is proportional to the total number of characters. In the example and, ant, dad, do, for n = 4 the bound is 7 and the actual value is 6. The edge labels still carry the characters in total; but these labels can be stored not as separate strings but as (start, length) pairs pointing into the original words. In this way memory too stays bounded by O(n) nodes and the words themselves.

Example 11.9

Question. How many nodes, not counting the root, does the standard trie of the words car, cart, care, cat and dog have? How many remain in the compressed trie?

Solution. The nodes of the standard trie are c, ca, car, cart, care, cat, d, do, dog: 9 nodes. In compression “c” is single-child and unmarked; “c” and “ca” merge and a “ca” edge results. “ca” stays because it has two children (r, t). “car” is marked and stays. cart, care and cat are leaves. “d” and “do” are single-child and unmarked; the “dog” edge reduces to a single node. The remaining nodes are ca, car, cart, care, cat, dog: 6 not counting the root, 7 including it.

In 1968 Morrison published the binary-alphabet version of this idea under the name Patricia. The Patricia trie is used in IP routing tables and in file systems. The price of compression is that insertion and deletion become more complicated. If a new word diverges in the middle of an edge, the edge is split in two and a new node is placed between. In deletion, a node that is left with a single child is merged again with its parent edge.

11.8.6The suffix trie

In the examples so far the trie stored a set of words. To search inside a text, a different set is chosen: all the suffixes of the text. The suffixes of the text T = “abab” are abab, bab, ab and b. If these four suffixes are inserted into a trie, we get a suffix trie.

The power of the suffix trie comes from a chain of equivalences:

P is a substring of T ⇔ P is a prefix of some suffix of T ⇔ P is a path from the root in the suffix trie.

The first equivalence comes from the definition of a substring: if P begins at position i in T, it is a prefix of the suffix that begins at position i. The second holds because every prefix in a trie is a path. As a result, the question “does P occur in T?” is answered by startsWith(P). The time is O(m), where m = |P|, independent of the length of the text. The text is processed once, and then any number of patterns can be searched quickly.

TrieNode suffixTrie(String t) {
  TrieNode root = new TrieNode();
  for (int s = 0; s < t.length(); s++) {
    TrieNode node = root;
    for (int j = s; j < t.length(); j++) {
      int i = t.charAt(j) - 'a';
      if (node.child[i] == null)
        node.child[i] = new TrieNode();
      node = node.child[i];
    }
    node.isWord = true;  // suffix ends
  }
  return root;
}

In the outer loop the code walks over the start s of each suffix. The inner loop, starting from s, inserts the characters of the suffix into the trie like an ordinary insertion. When the suffix ends, the last node is marked. The marker is not needed for the substring query, but can be used to ask whether a string is a suffix.

Table 11.21: Trace of suffixTrie("abab").
sSuffixNodes createdMarked
0ababa, ab, aba, abab (4)abab
1babb, ba, bab (3)bab
2abnone; the path already existsab
3bnone; the path already existsb
abbaabbrootta0b1a2b3
Figure 11.32: The suffix trie of the text “abab”: 8 nodes including the root. The suffixes abab, bab, ab and b are marked.

The first two suffixes open new branches; the last two stay on the paths of earlier suffixes and only get a marker. In all, 7 nodes were created; with the root there are 8. Queries are answered as follows: “ba” is a path from the root (b → a), so it is a substring of “abab”. For “bb” there is no 'b' branch after “b”; “bb” is not a substring. “bab” is found in three steps, “bb” is rejected in two.

The cost of the suffix trie is its size. A text of length n has at most n(n + 1)/2 distinct non-empty substrings, and every node of the suffix trie is a different substring. In the text “abcd”, whose characters are all different, this bound is reached: 10 nodes. Of the 21 possible substrings of the text “banana”, 15 are distinct, and the suffix trie has 15 nodes besides the root. In general the memory is O(n2); for a text of a million characters this is unacceptable.

The remedy is again compression. A compressed suffix trie is called a suffix tree. Since a suffix tree has n suffixes, by the compressed trie theorem it has O(n) nodes. The edge labels are stored as (start, end) position pairs in the text. The algorithm published by Ukkonen in 1995 builds a suffix tree in O(n) time. An option that needs less memory is the suffix array: an array holding the starting indices of the suffixes in lexicographic order. Substring search in a suffix array takes O(m log n) with binary search.

11.8.7Aho–Corasick

An antivirus scanner looks for thousands of signatures in a file at the same time. Scanning the text separately for each signature means as many scans as there are patterns. The Aho–Corasick algorithm puts all the patterns into a trie and reads the text only once, from left to right. During reading it moves from one node of the trie to another. This approach is the multi-pattern generalization of the single-pattern KMP algorithm.

Let the patterns be he, she, his and hers. The trie has the paths h → he → her → hers, h → hi → his and s → sh → she. Besides the trie, a failure link is computed for each node.

Definition 11.2

In a pattern trie, the failure link of a node u is the link to the node of the longest proper suffix (a suffix shorter than the string itself) of the string that u represents, among those that have a node in the trie. If there is no such suffix, the link goes to the root.

In the example, the suffixes of “she” are “he” and “e”; “he” is in the trie, so the failure link goes to “he”. The suffix “h” of “sh” is in the trie. The suffixes of “hers” are “ers”, “rs” and “s”; only “s” is in the trie. The failure link of “his” goes to “s” as well. The links of the remaining nodes (h, s, he, hi, her) go to the root.

hersisshe{he}{hers}{his}{she, he}
Figure 11.33: The trie of the patterns he, she, his, hers. The dashed lines are failure links; the braces show a node's output set.

While the text is read, if the current node has a branch for the character read, we move to that branch. If there is none, we fall back along the failure link and try the same character at the new node; this corresponds to falling back with the prefix table in KMP. If the root has no branch either, we stay at the root. At each node the node's output set is reported. The output set is the union of the node's own pattern and the patterns reached along the failure chain. The output of the “she” node is {she, he}, because its failure link goes to “he” and “he” is a pattern.

Table 11.22: Scanning the text “ushers” with Aho–Corasick.
IndexCharacterState (node)Found
0uroot (no 'u' branch)—
1ss—
2hsh—
3esheshe, he
4rshe → (failure) he → her—
5shershers

At the character at index 4 (r), the “she” node has no 'r' branch. We fall back by the failure link to “he”; “he” has an 'r' branch and we move to the “her” node. This fallback keeps the last two characters read with “she” (h, e) from going to waste: “he” already represents a matched prefix. The text is read in a single pass and three matches are found: she and he ending at index 3, hers ending at index 5.

The failure links are computed on the trie by breadth-first traversal: the link of a node is found by starting from its parent's link and looking for a branch for the same character. This preprocessing is proportional to m, the sum of the pattern lengths. The scan takes O(n) transitions for a text of length n, plus the cost of reporting z matches. The total time is O(n + m + z) (Aho and Corasick, 1975). The algorithm is used in virus signature scanning, in network intrusion detection systems and in banned-word filters. The first versions of the Unix fgrep command were also based on this algorithm.

11.8.8The trie family

The variants of the trie are different forms of a common idea. Table 11.23 summarizes which question is answered best by which structure.

Table 11.23: The trie family: which structure for which question?
StructureWhat it storesQuestion it is strong atQuery
Standard triea set of wordsexact word, prefix, autocompleteO(L)
Trie with prefix counts+ the number of words passing through a node“how many words have this prefix?”O(P)
Compressed triesingle-child chains mergedkeys with long common prefixes, memoryO(L)
Ternary search trie3 links per nodelarge alphabet, little memoryO(L + log n) avg.
Binary triebit strings (IP, integers)longest-prefix match, maximum XORO(B)
Suffix trie / arrayall suffixes (array: O(n) memory)“is P a substring of T?”O(m) / O(m log n)
Aho–Corasickpattern trie + failure linksfinding many patterns in a text at onceO(n + z)

The common idea is always the same: the key is read character by character (or bit by bit) and common prefixes are shared. The differences lie in what is stored in a node and how the children are reached. In choosing a structure, the kind of problem comes first: exact match, prefix, substring, or many patterns? Then the size of the alphabet and the memory budget are considered.

11.9Common mistakes

Trie code is short, but a few subtle points are often overlooked. Most of the mistakes below do not show up in small tests and appear only with special inputs.

Common mistake

Forgetting isWord. Looking only at the existence of the path in a search counts every prefix as a word. In the trie of and, ant, dad, do, “da” would seem to be found. Without the end-of-word marker, a trie stores not a set of words but all the prefixes of the set.

Common mistake

Confusing search with startsWith. A prefix query does not look at the last node's marker; an exact word search must. The two methods differ only in the last line, and writing that line wrongly does not cause a compile error.

Common mistake

Characters outside the alphabet. 'A' - 'a' = −32 and 'ş' - 'a' = 254; the array bound is exceeded. The input must be converted to lowercase and to the a–z alphabet, or the children must be kept in a HashMap. Care is also needed when lowercasing Turkish text: in Java, "I".toLowerCase() gives “i” in the English locale and “ı” in the Turkish locale; a call without a parameter depends on the machine's locale.

Common mistake

Deleting a shared node during deletion. Deleting the path from start to end destroys the other words that share the prefix. Only childless, unmarked nodes are deleted, from the bottom up.

Common mistake

Expressing the complexity in terms of n. Trie operations are O(L), not O(log n) or O(n): they are independent of the number of words. On the other hand, counting a search in a hash table as “O(1), faster than a trie” is also wrong; computing the hash value reads L characters as well.

Common mistake

Underestimating memory. Each node carries 26 references; with millions of nodes this comes to hundreds of MB. For a sparse trie a HashMap, a ternary search trie or compression is needed.

Common mistake

Not undoing shared state when backtracking. If recursive walks such as collect use a shared StringBuilder, the appended character must be removed after each call. Otherwise the words of the following siblings come out corrupted.

11.10Summary

  • Structure: a trie stores a set of strings in a rooted tree. The root is the empty string, each edge carries a character, each node is a prefix. A word is a path from the root whose last node is marked. Common prefixes are stored once; the shape of a trie does not depend on the insertion order.
  • Node: TrieNode[26] child and boolean isWord. The character is not stored in the node; the index is found with ch − 'a'. Characters outside the alphabet exceed the array bound.
  • Insertion: if the child does not exist it is created, if it does we move on; at the end the last node is marked. O(L); at most L new nodes.
  • Search and prefix query: false if a branch is missing; search returns isWord at the end, the prefix query returns true. O(L) and O(P). A count counter gives the number of words that start with a prefix in O(P).
  • Wildcard and spell checking: a wildcard character tries every filled branch. The edit distance rows are computed on the trie from parent to child; the row of a common prefix is computed once, and branches whose row minimum exceeds the bound are pruned.
  • Autocomplete: the prefix node is found and the subtree is walked depth first; the result is in alphabetical order. O(P + S · M). The longest common prefix is found by descending from the root along single-child, unmarked nodes.
  • Deletion: the marker is removed; childless, unmarked nodes are deleted from the bottom up. Three cases: if the word is a prefix only the marker is removed, if it has a tail the tail is deleted, if the word is absent nothing changes. O(L · M), O(L) with a child counter.
  • Memory: O(N · M); in the trie of and, ant, dad, do, 226 of the 234 references are null. For sparse nodes a HashMap, a TreeMap, a ternary search trie or a compressed trie is used.
  • Comparison: for exact search the trie and the hash table are O(L); the trie's difference is in prefix and order queries. A preorder traversal yields the words in lexicographic order.
  • Variants: the binary trie (longest-prefix match, maximum XOR), the ternary search trie (3 links per node), the compressed trie and Patricia (at most 2n − 1 nodes for n words), the suffix trie → suffix tree and suffix array, Aho–Corasick (multi-pattern search with failure links, O(n + m + z)).

11.11Key terms

  • trie (prefix tree)
  • prefix
  • suffix
  • substring
  • end of word
  • alphabet
  • reference (child pointer)
  • prefix query
  • wildcard search
  • edit distance
  • autocomplete
  • backtracking
  • depth-first search (DFS)
  • longest common prefix
  • lexicographic order
  • hash table
  • radix sort
  • binary trie
  • longest prefix match
  • ternary search trie (TST)
  • compressed trie (radix tree)
  • suffix trie / suffix tree
  • suffix array
  • Aho–Corasick algorithm
  • failure link

11.12Test Yourself

Questions 1–7 use the same trie: the words sel, selam, sen, ses and su have been inserted into a trie with 26-element arrays.

  1. How many nodes does the trie have, counting the root? How many child references are null in total?

    Answer

    The nodes are s, se, sel, sela, selam, sen, ses and su: 8 nodes, 9 with the root. The number of references is 9 × 26 = 234. The number of filled references equals the number of edges (8); 234 − 8 = 226 references are null.

  2. What do search("se"), startsWith("se"), search("sela") and startsWith("sela") return?

    Answer

    false, true, false, true, in that order. The paths of “se” and “sela” exist, but both nodes are unmarked; both are only prefixes.

  3. Which list does complete("se") return? Why is the list in this order?

    Answer

    [sel, selam, sen, ses]. Since “se” is unmarked it is not added. The children are walked in index order: l (11), n (13), s (18). The “sel” node, being itself marked, is added before “selam”.

  4. Suppose the words were inserted with the prefix-counting insert. What is the value of count at the root, at the “se” node and at the “sel” node?

    Answer

    5 at the root, 4 at “se” (all except su), 2 at “sel” (sel and selam). prefixCount("se") returns 4.

  5. If each deletion is applied separately to the initial trie, how many nodes do delete("sel"), delete("selam") and delete("su") remove?

    Answer

    delete("sel"): 0; “sel” has an 'a' child, only the marker is removed. delete("selam"): 2; “selam” and “sela” are deleted, and we stop at the marked “sel” node. delete("su"): 1; “su” is deleted, and we stop because the “s” node has the child 'e'.

  6. What does longestCommonPrefix() return? What would the result be if the word “su” were not in the trie?

    Answer

    “s”. The root's only child is 's', but the “s” node has two children (e, u) and the descent stops. Without “su”, the only child of “s” would be 'e'; the “se” node has three children (l, n, s) and the descent stops there: “se”.

  7. For the query “sez” and k = 1, which words does the edit distance search on the trie suggest? At which node is pruning done?

    Answer

    The rows (with columns “”, s, e, z) are: s → 1 0 1 2, se → 2 1 0 1, sel → 3 2 1 1, sen and ses → 3 2 1 1, su → 2 1 1 2, sela → 4 3 2 2. The words whose last cell is 1 are sel, sen and ses; all three are suggested. The last cell of “su” is 2, so it is not suggested. The minimum of the “sela” row is 2, and it is pruned; “selam” is not entered.

  8. How many nodes, not counting the root, does the compressed trie of the same five words have? What is the upper bound from the theorem?

    Answer

    s (two children), se (three children), sel, selam (with the edge “am”), sen, ses and su: 7 nodes. The “sela” node of the standard trie has been merged into the “am” edge. The bound is 2 · 5 − 1 = 9.

  9. In the array [2, 9, 12, 5], which pair has the largest XOR value? In a 4-bit binary trie, which number is reached for 2?

    Answer

    The representations are 0010, 1001, 1100, 0101. For 2 the wanted bits are 1101: a 1 at bit 3 (9 and 12 have it), a 1 at bit 2 (only 12), a 0 at bit 1 (the bit of 12 is 0), a 1 is wanted at bit 0 but the bit of 12 is 0. The number reached is 12 and 2 ⊕ 12 = 1110 = 14. The largest value is 14 (2 and 12).

  10. How many nodes, not counting the root, does the suffix trie of the text “aab” have? Are “ba” and “ab” substrings?

    Answer

    The suffixes are aab, ab, b. The nodes are a, aa, aab, ab, b: 5 nodes; this number is the number of distinct substrings of the text (“a” occurs twice and is counted once). “ab” is the path a → b from the root, so it is a substring. For “ba”, “b” has no children at all; it is not a substring.

11.13Further reading

  • R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 5.2: gives Java code, deletion and memory measurements for R-way tries and ternary search tries in detail.
  • D. Gusfield, Algorithms on Strings, Trees, and Sequences (1997): covers suffix trees, Ukkonen's algorithm and Aho–Corasick together with applications to biological sequences.
  • J. L. Bentley and R. Sedgewick, “Fast Algorithms for Sorting and Searching Strings”, Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1997: analyzes the ternary search trie and the three-way string quicksort based on it.
  • A. V. Aho and M. J. Corasick, “Efficient String Matching: An Aid to Bibliographic Search”, Communications of the ACM 18(6), 1975: the original paper on the multi-pattern matching algorithm with failure links.

11.14References

  1. A. V. Aho, M. J. Corasick, “Efficient String Matching: An Aid to Bibliographic Search”, Communications of the ACM 18(6), 1975.
  2. J. L. Bentley, R. Sedgewick, “Fast Algorithms for Sorting and Searching Strings”, Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, 1997.
  3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
  4. E. Fredkin, “Trie Memory”, Communications of the ACM 3(9), 1960.
  5. D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997.
  6. U. Manber, G. Myers, “Suffix Arrays: A New Method for On-Line String Searches”, SIAM Journal on Computing 22(5), 1993.
  7. D. R. Morrison, “PATRICIA — Practical Algorithm To Retrieve Information Coded in Alphanumeric”, Journal of the ACM 15(4), 1968.
  8. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 (Section 5.2: Tries).
  9. E. Ukkonen, “On-line Construction of Suffix Trees”, Algorithmica 14(3), 1995.

Related pages: Chapter 11 slides · © Sercan Külcü. All rights reserved.