Jul-20-2019, 12:09 AM
I am new to python, I found different codes that implements trie, like this one example below, but I have hard time understanding how to search the trie..
Which I was able to obtain through another code (see below), but this one test only if the word is in the trie.
Thank you for your help
from collections import defaultdict class TrieNode: def __init__(self): self.children = defaultdict(TrieNode) self.isEnd = False def insert(self, word): node = self for w in word: node = node.children[w] node.isEnd = True def search(self, word): node = self for w in word: if w in node.children: node = node.children[w] else: return [] # prefix match # traverse currnt node to all leaf nodes result = [] self.traverse(node, list(word), result) return [''.join(r) for r in result] def traverse(self, root, prefix, result): if root.isEnd: result.append(prefix[:]) for c,n in root.children.items(): prefix.append(c) self.traverse(n, prefix, result) prefix.pop(-1) if __name__ == "__main__": words = ['a', 'apple', 'angle', 'angel', 'bat', 'bats'] root = TrieNode() for w in words: root.insert(w) print (root.search('an')) # ['angle', 'angel'] print (root.search('ap')) # ['apple']What I am trying to accomplish is create a method that search an existing trie and produce a suggestion list, rather than creating a trie every time, for example the existing trie for words = ['a', 'apple', 'angle', 'angel', 'bat', 'bats'] is: {'a': {'': '', 'p': {'p': {'l': {'e': {'': ''}}}}, 'n': {'g': {'l': {'e': {'': ''}}, 'e': {'l': {'': ''}}}}}, 'b': {'a': {'t': {'': '', 's': {'': ''}}}}}
Which I was able to obtain through another code (see below), but this one test only if the word is in the trie.
for word in words: # create a temporary dict based off our root # dict object temp_dict = trie for letter in word: # update our temporary dict and add our current # letter and a sub-dictionary temp_dict = temp_dict.setdefault(letter, {}) # If our word is finished, add {'*': '*'} # this tells us our word is finished temp_dict[_end] = _end return trie def find_word(trie, word): sub_trie = trie mylist = [] for letter in word: if letter in sub_trie: sub_trie = sub_trie[letter] mylist.append(letter) else: return False else: if _end in sub_trie: return True else: return False # Test our trie creation trie = make_trie('a', 'apple', 'angle', 'angel', 'bat', 'bats') # print out our new trie print(trie) find = find_word(trie,"apple") print (find)Please help explaining how can I create a method that search an existing trie and produce a suggestion list, the reason I want to that is because the trie that I am dealing with is large and fixed, so if I create it every time I try to obtain a suggestion list, it takes a long time which defeats the main purpose of the trie.
Thank you for your help