Introduction to Trie Data Structure and Implementation in Python
When it comes to information retrieval, dictionaries, and phonebooks, the Trie Data Structure is one of the most efficient ways of storing and accessing data. It’s a tree-like structure that is primarily used for word searching and auto-text suggestions.
In this article, we will focus on the implementation of Trie Data Structure in Python and how to insert and search for elements in the structure.
Implementing the TrieNode class
To implement the Trie Data Structure in Python, we need to start by implementing the TrieNode class. A TrieNode is defined as a tree node that contains a character, a boolean value (is_end), a list of children (which can be of 26 sizes representing characters A to Z), and a string value representing the word (if it is the end of the word).
class TrieNode:
def __init__(self):
self.children = [None]*26
self.is_end = False
self.word = ""
Here, we initialize an empty list of size 26 to represent 26 characters (A to Z) in the trie structure. The is_end variable represents whether a node is the end of a saved word or not, and the word variable is an empty string.
Creating the Trie Data Structure Class
Now that we have defined the TrieNode class, the next step will be to implement the Trie Data Structure Class. Our implementation would have two primary methods – insert and search.
Let’s take a closer look at each of them.
Inserting Elements into the Trie Structure
Inserting words into the Trie Data Structure requires a character by character traversal of the word, and then adding the characters to the list of children as TrieNodes.
To insert a word into the Trie Data Structure, we start from the root and check if each character in the word is in the Trie data structure.
If a character is not found in the data structure, we add it as a new TrieNode.
def insert(self, word):
node = self.root
for char in word:
index = ord(char) - ord('a')
if not node.children[index]:
node.children[index] = TrieNode()
node = node.children[index]
node.is_end = True
node.word = word
This code snippet traverses through each character in the word and checks if it exists in the Trie data structure.
If it doesn’t exist, it creates a new TrieNode for the character and adds it to the ‘children’ list of the current node. After traversing all the characters, the ‘is_end’ variable of the last node should be set to true to indicate that a complete word has been inserted.
Visualization of Trie with Inserted Words
Let’s assume we have inserted the words “panda,” “pan,” and “pand” into the Trie data structure. Our Trie data structure would resemble the graph below.
root
/ …
p …
z
/
a e … | |
n r z
| | |
d a z
With the visualization of the Trie data structure, we can see that the last node for “pan,” “panda,” and “pand” all have their ‘is_end’ variable set to True, indicating that we have successfully inserted the words.
Implementing the Searching Operation in Trie Data Structure in Python
In addition to inserting words into the Trie Data Structure, we also need to be able to search for words in the Trie in Python. In this section of the article, we will be focusing on how to search for exact matches and prefix matches in the Trie Data Structure.
Searching for Words in the Trie in Python
The search operation in the Trie Data Structure involves finding all the words in the Trie that match a given search query. Two types of searches are commonly performed with a Trie Data Structure: exact match, which returns all the words in the Trie that match the search query, and prefix match, which returns all the words in the Trie that start with the search query.
Exact match can be performed by performing a DFS search of the Trie Data Structure, starting from the root, while keeping track of all the words that are found during the search. Prefix match involves searching through the Trie Data Structure, starting from the root and nipping the graph when a prefix of the search query is matched.
The DFS Function
To perform an exact match search on a Trie Data Structure, we need a DFS function that traverses the Trie Data Structure and returns all the words found that match our search query. The DFS function must take three inputs – node, pre, and output.
The node represents the current node being traversed; pre represents the prefix of the word that has been built up during the traversal, which is all the characters that have been visited so far, and output represents the list of words found to match the search query.
def dfs(self, node, pre, output):
if node and node.is_end:
output.append(pre + node.word)
for next_node in node.children:
self.dfs(next_node, pre + node.word, output)
The DFS function is a recursive function that starts at the root of the Trie Data Structure and calls itself recursively for each child of the current node.
When it finds a node that is the end of a word, it will add the ‘pre variable’ (which is a prefix of the word built up so far) plus the ‘word variable’ (which is the remaining characters of the word) to the output list.
The Search Function
Now that we have our DFS search function, we can use it to complete our search functionality in the Trie Data Structure. The search function involves taking a search query and moving down the Trie data Structure, character by character until we reach the last character in the search query.
We will then perform a DFS search on the Trie Data Structure starting from the node of the last character, to find all the complete words in the Trie that match the search query. The search function should take one input – a search query – and return a list of words that match the search query.
def search(self, query):
node = self.root
output = []
for char in query:
if not node.children[ord(char) - ord('a')]:
return output
else:
node = node.children[ord(char) - ord('a')]
self.dfs(node, query[:-1], output)
return output
In this function, we move down the Trie data Structure character by character to find the last TrieNode that matches the search query. Then, we perform a DFS search, starting from the last node, to find all the complete words in the Trie that match the search query.
Finally, we return the list of matching words found during our search.
Testing the Trie Data Structure Implementation in Python
It’s time to test our Trie Data Structure implementation in Python to see if it is working correctly. We can easily utilize the Trie implementation by inserting words we would like to search in the Trie.
After inserting the words, we can perform search queries to retrieve and output the results.
Utilizing the Python Trie Implementation
To test the Python Trie implementation, we start by creating an instance of our Trie data structure and inserting a few words into it. trie = Trie()
trie.insert("computer")
trie.insert("programming")
trie.insert("language")
trie.insert("code")
Output Results of the Search Query
To perform a search query, we can query our Trie data structure by passing in a search query to our search function. In this case, we will search for all words in the Trie that have a prefix of “pro.”
results = trie.search("pro")
print(results)
The output of the above code will be:
[‘programming’]
As we can see, the output of the search query only returned “programming,” which is the only word in the Trie that starts with the prefix “pro.”
Final Words
In conclusion, we have covered the basics of implementing the Trie Data Structure in Python and how to insert and search for words using the data structure. The Trie Data Structure is an efficient way of storing and accessing data, especially when it comes to information retrieval, dictionaries, and phonebooks.
By implementing the TrieNode class, creating the Trie Data Structure class, and implementing the search functionality, we can utilize Python’s Trie Data Structure to power our web and mobile applications effectively.
Conclusion
In this article, we have explored the basics of implementing the Trie Data Structure in Python, how to insert elements, search for exact matches and prefix matches, and test the implementation of the data structure. The Trie Data Structure is a tree-like structure used primarily for word searching and auto-text suggestions.
It is an efficient way to store and access data, especially when it comes to information retrieval, dictionaries, and phonebooks.
Summary and Key Takeaways
We have learned that a Trie Data Structure implementation consists of the TrieNode class, which includes a character, a boolean value representing the end of a word, a list of children representing 26 characters (A to Z), and a string value representing the word. The Trie Data Structure class is responsible for creating the Trie nodes, inserting words, and searching words in the Trie.
To implement word insertion in the Trie Data Structure, we traverse through the Trie structure character by character for each word and create new nodes for the characters that do not exist in the Trie structure. We also set the ‘is_end’ variable of the node for the last character in each word to True, indicating that a complete word has been inserted into the structure.
We can search for words in the Trie Data Structure in two ways: by performing an exact match search or a prefix search. There are different algorithms for each search type.
For an exact match search, we use a Depth-First Search (DFS) algorithm to traverse the Trie data structure starting from the root down to the last character in the search query. We also keep track of all complete words that match the search query.
For prefix search, we nip the Trie data structure at the last character of the search query and traverse the Trie data structure from the truncated graph’s root.
Finally, we have seen that testing the Trie Data Structure implementation requires creating an instance of the Trie class and inserting words into the structure.
We can then perform search queries on the Trie Data Structure to retrieve results. In conclusion, the Trie Data Structure is a powerful data structure that can be implemented in Python.
It is an efficient way to store and access data, especially for applications that require prefix-based searches or support auto-complete features. With the understanding of the TrieNode class, adding nodes, searching, and testing, we can utilize the Python Trie data structure to improve the performance of our web and mobile applications.
In this article, we have explored the implementation of the Trie Data Structure in Python, including the TrieNode class, constructing the Trie Data Structure, and implementing insertion and search operations. We have seen how the Trie Data Structure is an efficient way to store and access data for information retrieval, dictionaries, phonebooks, and auto-complete features.
Key takeaway points are that the Trie Data Structure can be implemented in Python, efficiently stores and accesses data, supports prefix-based searches and prefixes based auto-complete, and the understanding of Trie Data Structure usage can be utilized to improve application performance.