Python Forum
How to create an autocomplete method that search an existing trie in python
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
How to create an autocomplete method that search an existing trie in python
#1
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..

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
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Python best library for Excel reports & review of existing code MasterOfDestr 4 497 Feb-14-2024, 03:39 PM
Last Post: MasterOfDestr
  Python beginner that needs an expression added to existing script markham 1 665 Sep-04-2023, 05:24 AM
Last Post: Pedroski55
  how to easily create a list of already existing item CompleteNewb 15 3,382 Jan-06-2022, 12:48 AM
Last Post: CompleteNewb
  How to add an image to an existing facebook post using python graph API? Ascalon 0 2,180 Dec-01-2020, 08:33 PM
Last Post: Ascalon
  Create new variable dependent on two existing variables JoeOpdenaker 6 2,934 Oct-25-2020, 02:15 PM
Last Post: jefsummers
  autocomplete working code sample not working... aviper4u 0 1,602 Oct-24-2020, 03:04 AM
Last Post: aviper4u
  Python Paramiko mkdir command overwriting existing folder. How can i stop that? therenaydin 1 3,168 Aug-02-2020, 11:13 PM
Last Post: therenaydin
  ipython autocomplete broke indentation! Exsul 6 4,467 Aug-20-2019, 01:29 AM
Last Post: Exsul

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020