Trie Search

The most classic trie operation is search—namely, determining whether a string is found in the trie. Search has two flavors: we can search to see whether the string is a complete word, or we can search to see whether the string is at least a word prefix (that is, the beginning of a word). These two versions are similar, but we’ll implement the latter one, where our search will look for prefixes. This search will end up finding complete words as well, since a complete word is at least as good as a prefix.

The algorithm for prefix search performs the following steps (they’ll become clearer when we walk though an example that follows):

We establish a variable called current_node. At the beginning of our algorithm, this points to the root node.
We iterate over each character of our search string.
As we point to each character of our search string, we look to see if the current_node has a child with that character as a key.
If it does not, we return None, as it means our search string does not exist in the trie.
If the current_node does have a child with the current character as the key, we update the current_node to become that child. We then go back to Step 2, continuing to iterate over each character in our search string.
If we get to the end of our search string, it means we’ve found our search string.

Let’s see this in action by searching for the string "cat" in our trie from earlier.

Setup: We set the current_node to be the root node. (The current_node is indicated in bold in the diagrams on the following pages.) We also point to the first character of our string, which is the "c", as shown in the top .

Step 1: Since the root node has "c" as a child key, we update the current_node to become that key’s value. We also continue iterating through the characters in our search string, so we point to the next character, which is the "a", as shown in the bottom .

Step 2: We inspect the current_node for a child with the key of "a". It has one, so we make that child the new current_node. We then proceed to search for the next character in our string, which is the "t":

Step 3: We’re now pointing to the "t" of our search string. Since the current_node has a "t" child, we follow it, as shown in the .

/books/45079/OEBPS/tries/follow_the_t.png

Since we’ve reached the end of our search string, it means we’ve found "cat" in our trie.

Code Implementation: Trie Search

Let’s implement trie search by adding a search method to our Trie class:

	def search(self, word):
	current_node = self.root

	for char in word:
	if current_node.children.get(char):
	current_node = current_node.children[char]
	else:
	return None

	return current_node

Our search method accepts a string that represents the word (or prefix) we’re searching for.

First, we establish the root node as our current_node:

current_node = self.root

Then we iterate over each character of our search word:

for char in word:

Within each round of the loop, we check whether the current node has any children with the current character as the key. If there is such a child, we update the current node to be the child node:

	if current_node.children.get(char):
	current_node = current_node.children[char]

If there is no such child, we return None, as it means we’ve hit a dead end and our search word isn’t contained in the trie.

If we get past the end of the loop, it means we’ve found the entire word in our trie. In this case, we return the current_node. The reason we return the current node, as opposed to just returning True, is to help us with the autocomplete feature, as I’ll explain when we get there.