Can you recall a time when you have misspelled a word in your text message? If you have liked most people and myself, then you may also have noticed a red line spelling error message notification helping you to fix the error. You may have also encountered searching for something in using a search engine and a list with the next most similar words displayed to help you. Features such as spell check and auto- text in messages or search engine bars can be extremely useful. If you have ever wondered how this magic works then hopefully this short article will clear up some answers. In this short article, I will go over Prefix or Trie Trees ( also known as Redix and Dictionary Trees).
Please ensure you know what each below is before we dive into more about a Trie Tree is.
Warm Up:
- Vertice — a node in a tree
- Edge — a connection between Nodes
- Rood Node — Topmost Node of a Tree
- Child Node — A certain Node that has an edge connecting it to another Node one level above itself.
- Parent node — Any node which has 1 or more child Nodes.
- Leaf Node — a node in a tree, a Leaf Node does not have any child Nodes.
Definition: A rooted tree used for storing associative arrays where keys are usually strings.
Positive: The efficiency of a Trie Search is mainly related to the length of the Trie or Prefix.
Negative: Trie Trees consumes a lot of memory
Properties:
- A trie is a multi-way tree where
- Each node has between 1 and k descendants.
- Each link of the tree has a matching character.
- Each lead node corresponds to the final word or ‘string’ which can be collected on a path from the root to the node.
Unlike Binary Search Trees, Tries do not have a node in the tree that stores the key associated with that node. Indeed, its position in the tree shows what key it is associated with. All descendants of any one node have a common prefix of the string associated with that one node, and the root is associated with the empty string. Typically, values are normally not associated with every node, rather they are only with a leaf and inner nodes that happened to correspond to the keys of interest.
Search/Find: This algorithm follows the path from the root towards the leaf and can result in the word being either found or not. Ultimately, leaving a negative and/or positive impact on the complexity of this data structure with its depth.
def find(self, word):
'''
Returns the TrieNode representing the given word if it exists
and None otherwise.
'''
current = self.root
for char in word:
if char not in current.children:
return None
current = current.children[char] # New code, None returned implicitly if this is False
if current.is_word:
return current
Insertion in Tries/Prefix: The insertion checks if current_character is at the current level of the tree. This begins with the start of the root and continues down the branch labeled with the character. If not, then a new branch inserts at that point.
StartsWith():
Below are three basic operations: insert(), search(), startsWith() methods. We can assume that all the input below is in lowercase letters. If we can do the functions as shown below in the function, then we will see outputs.
- Trie trie = new Trie()
- trie.insert(“apple”)
- trie.search(“apple”) //This will return true
- trie.search(“app”) //This will return false
- trie.startsWith(“app”) //This will return true
- trie.insert(“app”)
- trie.search(“app”) //This will return true
To solve this, we will follow the Psuedocode steps below.
Psuedocode:
- Initially make one dictionary called child.
- The insert method will be like −current := child
- for each letter l in word −
- if l is not present in current, then current[l] := new dictionary
- Set current := current[l]
- Set current[#] = 1
- The search method will be like −current := child
- for each letter l in word , if l is not present in current, then return false
- Set current := current[l]
- return true if current[#] = 1, otherwise false
- The startsWith method will be like − current := child
- for each letter l in word −if l is not present in current, then return false
- Set current := current[l] and lastly return True.
Code Example:
