dsa.trie

Module containing trie class.

  1""" Module containing trie class. """
  2
  3class TrieNode:
  4    """ 
  5    A trie node implementation.
  6    """
  7    def __init__(self):
  8        #: a dictionary of key (character) ->value (references)
  9        self.children = {}
 10
 11class Trie:
 12    """ 
 13    A trie implementation. 
 14    """
 15    #: end marker
 16    end_marker = "*"
 17
 18    def __init__(self):
 19        """ 
 20        Initialize a trie.
 21        """        
 22        #: root of the trie
 23        self.root = TrieNode()
 24            
 25    def insert(self, word: str):
 26        """ 
 27        Insert a word into a trie.
 28        
 29        Args:
 30            word (str): The word to insert.
 31
 32        Returns:
 33            None
 34        """        
 35        current = self.root
 36        for c in word:
 37            if c not in current.children:
 38                current.children[c] = TrieNode()
 39
 40            current = current.children[c]
 41        current.children[Trie.end_marker] = None
 42    
 43    def search(self, word: str) -> bool:
 44        """ 
 45        Search for a word in a trie.
 46        
 47        Args:
 48            word (str): The word to search for.
 49        
 50        Returns:
 51            Boolean on whether the complete word is found.
 52        """        
 53        if len(word) == 0:
 54            return False
 55
 56        current = self.root
 57        for c in word + Trie.end_marker:
 58            if c not in current.children:
 59                return False
 60            current = current.children[c]
 61        return True
 62
 63    def search_node(self, substr: str) -> TrieNode:
 64        """ 
 65        Search for a substring in a trie.
 66        
 67        Args:
 68            substr (str): A substring to search for.
 69        
 70        Returns:
 71            TriedNode where the substring begins
 72            None if the substring is not found
 73        """        
 74        if len(substr) == 0:
 75            return None
 76
 77        current = self.root
 78        for c in substr:
 79            if c not in current.children:
 80                return None
 81            current = current.children[c]
 82        return current
 83    
 84    def delete(self, word: str, i: int=0, current: TrieNode=None) -> bool:
 85        """ 
 86        Delete a word from the trie.
 87        
 88        Args:
 89            word (str): The word to delete.
 90            i (int): The index of character.
 91            current (TrieNode): The current node.
 92
 93        Returns:
 94            Boolean indicating if child node can be deleted.
 95
 96        Raises:
 97            ValueError: If the word is not found.
 98        """        
 99        if i == len(word):
100            return True
101
102        # set up the beginning of delete
103        if current is None:
104            current = self.root
105            word = word + Trie.end_marker
106
107        char = word[i]
108
109        # character is not found, so word is invalid and return False
110        if char not in current.children:
111            return False
112        
113        next_node = current.children[char]
114        should_delete_ref = self.delete(word, i + 1, next_node)
115
116        # delete the child reference
117        if should_delete_ref:
118            del current.children[char]
119
120            # return True if there are no more children
121            return len(current.children) == 0
122        return False
123    
124    def delete_preorder(self, word: str, i: int=0, current: TrieNode=None):
125        """ 
126        Delete a word using preorder (Do not use! For demonstration purposes only).
127        
128        Args:
129            word (str): The word to delete.
130            i (int): The index of character.
131            current (TrieNode): The current node.
132
133        Returns:
134            Boolean indicating if child node can be deleted.
135
136        Raises:
137            ValueError: If the word is not found.
138        """        
139        if i == len(word):
140            return True
141
142        if current is None:
143            current = self.root
144            word = word + Trie.end_marker
145
146        char = word[i]
147        if char not in current.children:
148            return False
149        
150        next_node = current.children[char]
151
152        del current.children[char]
153
154        self.delete(word, i + 1, next_node)
155        
156        return False
157            
158    def list_words(self) -> list:
159        """
160        Return a list of all words in the trie.
161        """
162        return self.build_word_list(self.root, "", [])
163
164    def build_word_list(self, node: TrieNode=None, word: str = "", words=None):
165        """ 
166        Helper method to return a list of words given a starting node.
167        
168        Args:
169            node (TrieNode): The current trie node.
170            word (str): The word to build after each recursive call.
171            words: The list of words.
172
173        Returns:
174            List of words that begin with a given prefix.
175
176        Raises:
177            ValueError: If the word is not found.
178        """        
179        if words is None:
180            words = []
181
182        if node is None:
183            current = self.root
184        else:
185            current = node
186        
187        for key, node in sorted(current.children.items()):
188            if key == Trie.end_marker:
189                words.append(word)
190            else:
191                self.build_word_list(node, word + key, words)
192        return words
193    
194    def autocomplete(self, prefix: str):
195        """ 
196        Return a list of words that begin with a given prefix.
197        
198        Args:
199            prefix (str): The prefix to search for.
200
201        Returns:
202            List of words that begin with a given prefix.
203            None if there are no matching words.
204
205        Raises:
206            ValueError: If no words are found.
207        """        
208        current = self.search_node(prefix)
209        if current is None:
210            return None #self.list_words(current, "")
211        return self.build_word_list(current, prefix)
212    
213    def suggest(self, prefix: str):
214        """ 
215        Return a list of close words with a given prefix.
216        
217        Args:
218            prefix (str): The prefix to search for.
219
220        Returns:
221            List of words that are similar to a given prefix.
222            None if there are no matching words.
223
224        Raises:
225            ValueError: If the word is not found.
226        """        
227        if prefix is None or len(prefix) == 0:
228            return None
229        suggestions = self.autocomplete(prefix)
230        if suggestions is None or len(suggestions) == 0:
231            return self.suggest(prefix[:-1])
232        else:
233            return suggestions
234    
235    def copy_node(self, node: TrieNode):
236        """
237        Recursively deep copy a node and its children.
238
239        Args:
240            node (TrieNode): The node to copy.
241        
242        Returns:
243            A deep copy of the node.
244        """
245        if not node:
246            return
247        new_node = TrieNode()
248        for char, child in node.children.items():
249            new_node.children[char] = self.copy_node(child)
250        return new_node
251
252    def copy(self):
253        """
254        Create a deep copy of the Trie.
255
256        Returns:
257            A deep copy of the trie.
258        """
259        new_trie = Trie()
260        new_trie.root = self.copy_node(self.root)
261        return new_trie
class TrieNode: 
 4class TrieNode:
 5    """ 
 6    A trie node implementation.
 7    """
 8    def __init__(self):
 9        #: a dictionary of key (character) ->value (references)
10        self.children = {}

A trie node implementation.

children
class Trie: 
 12class Trie:
 13    """ 
 14    A trie implementation. 
 15    """
 16    #: end marker
 17    end_marker = "*"
 18
 19    def __init__(self):
 20        """ 
 21        Initialize a trie.
 22        """        
 23        #: root of the trie
 24        self.root = TrieNode()
 25            
 26    def insert(self, word: str):
 27        """ 
 28        Insert a word into a trie.
 29        
 30        Args:
 31            word (str): The word to insert.
 32
 33        Returns:
 34            None
 35        """        
 36        current = self.root
 37        for c in word:
 38            if c not in current.children:
 39                current.children[c] = TrieNode()
 40
 41            current = current.children[c]
 42        current.children[Trie.end_marker] = None
 43    
 44    def search(self, word: str) -> bool:
 45        """ 
 46        Search for a word in a trie.
 47        
 48        Args:
 49            word (str): The word to search for.
 50        
 51        Returns:
 52            Boolean on whether the complete word is found.
 53        """        
 54        if len(word) == 0:
 55            return False
 56
 57        current = self.root
 58        for c in word + Trie.end_marker:
 59            if c not in current.children:
 60                return False
 61            current = current.children[c]
 62        return True
 63
 64    def search_node(self, substr: str) -> TrieNode:
 65        """ 
 66        Search for a substring in a trie.
 67        
 68        Args:
 69            substr (str): A substring to search for.
 70        
 71        Returns:
 72            TriedNode where the substring begins
 73            None if the substring is not found
 74        """        
 75        if len(substr) == 0:
 76            return None
 77
 78        current = self.root
 79        for c in substr:
 80            if c not in current.children:
 81                return None
 82            current = current.children[c]
 83        return current
 84    
 85    def delete(self, word: str, i: int=0, current: TrieNode=None) -> bool:
 86        """ 
 87        Delete a word from the trie.
 88        
 89        Args:
 90            word (str): The word to delete.
 91            i (int): The index of character.
 92            current (TrieNode): The current node.
 93
 94        Returns:
 95            Boolean indicating if child node can be deleted.
 96
 97        Raises:
 98            ValueError: If the word is not found.
 99        """        
100        if i == len(word):
101            return True
102
103        # set up the beginning of delete
104        if current is None:
105            current = self.root
106            word = word + Trie.end_marker
107
108        char = word[i]
109
110        # character is not found, so word is invalid and return False
111        if char not in current.children:
112            return False
113        
114        next_node = current.children[char]
115        should_delete_ref = self.delete(word, i + 1, next_node)
116
117        # delete the child reference
118        if should_delete_ref:
119            del current.children[char]
120
121            # return True if there are no more children
122            return len(current.children) == 0
123        return False
124    
125    def delete_preorder(self, word: str, i: int=0, current: TrieNode=None):
126        """ 
127        Delete a word using preorder (Do not use! For demonstration purposes only).
128        
129        Args:
130            word (str): The word to delete.
131            i (int): The index of character.
132            current (TrieNode): The current node.
133
134        Returns:
135            Boolean indicating if child node can be deleted.
136
137        Raises:
138            ValueError: If the word is not found.
139        """        
140        if i == len(word):
141            return True
142
143        if current is None:
144            current = self.root
145            word = word + Trie.end_marker
146
147        char = word[i]
148        if char not in current.children:
149            return False
150        
151        next_node = current.children[char]
152
153        del current.children[char]
154
155        self.delete(word, i + 1, next_node)
156        
157        return False
158            
159    def list_words(self) -> list:
160        """
161        Return a list of all words in the trie.
162        """
163        return self.build_word_list(self.root, "", [])
164
165    def build_word_list(self, node: TrieNode=None, word: str = "", words=None):
166        """ 
167        Helper method to return a list of words given a starting node.
168        
169        Args:
170            node (TrieNode): The current trie node.
171            word (str): The word to build after each recursive call.
172            words: The list of words.
173
174        Returns:
175            List of words that begin with a given prefix.
176
177        Raises:
178            ValueError: If the word is not found.
179        """        
180        if words is None:
181            words = []
182
183        if node is None:
184            current = self.root
185        else:
186            current = node
187        
188        for key, node in sorted(current.children.items()):
189            if key == Trie.end_marker:
190                words.append(word)
191            else:
192                self.build_word_list(node, word + key, words)
193        return words
194    
195    def autocomplete(self, prefix: str):
196        """ 
197        Return a list of words that begin with a given prefix.
198        
199        Args:
200            prefix (str): The prefix to search for.
201
202        Returns:
203            List of words that begin with a given prefix.
204            None if there are no matching words.
205
206        Raises:
207            ValueError: If no words are found.
208        """        
209        current = self.search_node(prefix)
210        if current is None:
211            return None #self.list_words(current, "")
212        return self.build_word_list(current, prefix)
213    
214    def suggest(self, prefix: str):
215        """ 
216        Return a list of close words with a given prefix.
217        
218        Args:
219            prefix (str): The prefix to search for.
220
221        Returns:
222            List of words that are similar to a given prefix.
223            None if there are no matching words.
224
225        Raises:
226            ValueError: If the word is not found.
227        """        
228        if prefix is None or len(prefix) == 0:
229            return None
230        suggestions = self.autocomplete(prefix)
231        if suggestions is None or len(suggestions) == 0:
232            return self.suggest(prefix[:-1])
233        else:
234            return suggestions
235    
236    def copy_node(self, node: TrieNode):
237        """
238        Recursively deep copy a node and its children.
239
240        Args:
241            node (TrieNode): The node to copy.
242        
243        Returns:
244            A deep copy of the node.
245        """
246        if not node:
247            return
248        new_node = TrieNode()
249        for char, child in node.children.items():
250            new_node.children[char] = self.copy_node(child)
251        return new_node
252
253    def copy(self):
254        """
255        Create a deep copy of the Trie.
256
257        Returns:
258            A deep copy of the trie.
259        """
260        new_trie = Trie()
261        new_trie.root = self.copy_node(self.root)
262        return new_trie

A trie implementation.

Trie() 
19    def __init__(self):
20        """ 
21        Initialize a trie.
22        """        
23        #: root of the trie
24        self.root = TrieNode()

Initialize a trie.

end_marker = '*'
root
def insert(self, word: str): 
26    def insert(self, word: str):
27        """ 
28        Insert a word into a trie.
29        
30        Args:
31            word (str): The word to insert.
32
33        Returns:
34            None
35        """        
36        current = self.root
37        for c in word:
38            if c not in current.children:
39                current.children[c] = TrieNode()
40
41            current = current.children[c]
42        current.children[Trie.end_marker] = None

Insert a word into a trie.

Args: word (str): The word to insert.

Returns: None

def search(self, word: str) -> bool: 
44    def search(self, word: str) -> bool:
45        """ 
46        Search for a word in a trie.
47        
48        Args:
49            word (str): The word to search for.
50        
51        Returns:
52            Boolean on whether the complete word is found.
53        """        
54        if len(word) == 0:
55            return False
56
57        current = self.root
58        for c in word + Trie.end_marker:
59            if c not in current.children:
60                return False
61            current = current.children[c]
62        return True

Search for a word in a trie.

Args: word (str): The word to search for.

Returns: Boolean on whether the complete word is found.

def search_node(self, substr: str) -> TrieNode: 
64    def search_node(self, substr: str) -> TrieNode:
65        """ 
66        Search for a substring in a trie.
67        
68        Args:
69            substr (str): A substring to search for.
70        
71        Returns:
72            TriedNode where the substring begins
73            None if the substring is not found
74        """        
75        if len(substr) == 0:
76            return None
77
78        current = self.root
79        for c in substr:
80            if c not in current.children:
81                return None
82            current = current.children[c]
83        return current

Search for a substring in a trie.

Args: substr (str): A substring to search for.

Returns: TriedNode where the substring begins None if the substring is not found

def delete(self, word: str, i: int = 0, current: TrieNode = None) -> bool: 
 85    def delete(self, word: str, i: int=0, current: TrieNode=None) -> bool:
 86        """ 
 87        Delete a word from the trie.
 88        
 89        Args:
 90            word (str): The word to delete.
 91            i (int): The index of character.
 92            current (TrieNode): The current node.
 93
 94        Returns:
 95            Boolean indicating if child node can be deleted.
 96
 97        Raises:
 98            ValueError: If the word is not found.
 99        """        
100        if i == len(word):
101            return True
102
103        # set up the beginning of delete
104        if current is None:
105            current = self.root
106            word = word + Trie.end_marker
107
108        char = word[i]
109
110        # character is not found, so word is invalid and return False
111        if char not in current.children:
112            return False
113        
114        next_node = current.children[char]
115        should_delete_ref = self.delete(word, i + 1, next_node)
116
117        # delete the child reference
118        if should_delete_ref:
119            del current.children[char]
120
121            # return True if there are no more children
122            return len(current.children) == 0
123        return False

Delete a word from the trie.

Args: word (str): The word to delete. i (int): The index of character. current (TrieNode): The current node.

Returns: Boolean indicating if child node can be deleted.

Raises: ValueError: If the word is not found.

def delete_preorder(self, word: str, i: int = 0, current: TrieNode = None): 
125    def delete_preorder(self, word: str, i: int=0, current: TrieNode=None):
126        """ 
127        Delete a word using preorder (Do not use! For demonstration purposes only).
128        
129        Args:
130            word (str): The word to delete.
131            i (int): The index of character.
132            current (TrieNode): The current node.
133
134        Returns:
135            Boolean indicating if child node can be deleted.
136
137        Raises:
138            ValueError: If the word is not found.
139        """        
140        if i == len(word):
141            return True
142
143        if current is None:
144            current = self.root
145            word = word + Trie.end_marker
146
147        char = word[i]
148        if char not in current.children:
149            return False
150        
151        next_node = current.children[char]
152
153        del current.children[char]
154
155        self.delete(word, i + 1, next_node)
156        
157        return False

Delete a word using preorder (Do not use! For demonstration purposes only).

Args: word (str): The word to delete. i (int): The index of character. current (TrieNode): The current node.

Returns: Boolean indicating if child node can be deleted.

Raises: ValueError: If the word is not found.

def list_words(self) -> list: 
159    def list_words(self) -> list:
160        """
161        Return a list of all words in the trie.
162        """
163        return self.build_word_list(self.root, "", [])

Return a list of all words in the trie.

def build_word_list(self, node: TrieNode = None, word: str = '', words=None): 
165    def build_word_list(self, node: TrieNode=None, word: str = "", words=None):
166        """ 
167        Helper method to return a list of words given a starting node.
168        
169        Args:
170            node (TrieNode): The current trie node.
171            word (str): The word to build after each recursive call.
172            words: The list of words.
173
174        Returns:
175            List of words that begin with a given prefix.
176
177        Raises:
178            ValueError: If the word is not found.
179        """        
180        if words is None:
181            words = []
182
183        if node is None:
184            current = self.root
185        else:
186            current = node
187        
188        for key, node in sorted(current.children.items()):
189            if key == Trie.end_marker:
190                words.append(word)
191            else:
192                self.build_word_list(node, word + key, words)
193        return words

Helper method to return a list of words given a starting node.

Args: node (TrieNode): The current trie node. word (str): The word to build after each recursive call. words: The list of words.

Returns: List of words that begin with a given prefix.

Raises: ValueError: If the word is not found.

def autocomplete(self, prefix: str): 
195    def autocomplete(self, prefix: str):
196        """ 
197        Return a list of words that begin with a given prefix.
198        
199        Args:
200            prefix (str): The prefix to search for.
201
202        Returns:
203            List of words that begin with a given prefix.
204            None if there are no matching words.
205
206        Raises:
207            ValueError: If no words are found.
208        """        
209        current = self.search_node(prefix)
210        if current is None:
211            return None #self.list_words(current, "")
212        return self.build_word_list(current, prefix)

Return a list of words that begin with a given prefix.

Args: prefix (str): The prefix to search for.

Returns: List of words that begin with a given prefix. None if there are no matching words.

Raises: ValueError: If no words are found.

def suggest(self, prefix: str): 
214    def suggest(self, prefix: str):
215        """ 
216        Return a list of close words with a given prefix.
217        
218        Args:
219            prefix (str): The prefix to search for.
220
221        Returns:
222            List of words that are similar to a given prefix.
223            None if there are no matching words.
224
225        Raises:
226            ValueError: If the word is not found.
227        """        
228        if prefix is None or len(prefix) == 0:
229            return None
230        suggestions = self.autocomplete(prefix)
231        if suggestions is None or len(suggestions) == 0:
232            return self.suggest(prefix[:-1])
233        else:
234            return suggestions

Return a list of close words with a given prefix.

Args: prefix (str): The prefix to search for.

Returns: List of words that are similar to a given prefix. None if there are no matching words.

Raises: ValueError: If the word is not found.

def copy_node(self, node: TrieNode): 
236    def copy_node(self, node: TrieNode):
237        """
238        Recursively deep copy a node and its children.
239
240        Args:
241            node (TrieNode): The node to copy.
242        
243        Returns:
244            A deep copy of the node.
245        """
246        if not node:
247            return
248        new_node = TrieNode()
249        for char, child in node.children.items():
250            new_node.children[char] = self.copy_node(child)
251        return new_node

Recursively deep copy a node and its children.

Args: node (TrieNode): The node to copy.

Returns: A deep copy of the node.

def copy(self): 
253    def copy(self):
254        """
255        Create a deep copy of the Trie.
256
257        Returns:
258            A deep copy of the trie.
259        """
260        new_trie = Trie()
261        new_trie.root = self.copy_node(self.root)
262        return new_trie

Create a deep copy of the Trie.

Returns: A deep copy of the trie.