Trie based Auto complete Program in Python

    A trie is basically a ‘try’. It is a tree type data structure. It has a root and nodes.

This system provides you a brilliant way to find words depends on the user input. Generally, this input is a prefix text.

How it works???

• Here, a root node and some child nodes are there. Each node represents a chqracter.
• It is prefix searching, which finds the words according to the given prefix.
• Generally, it is suitable for auto complete data.

Autocomplete:

• First, the traversal is happening to find the node with prefix value.
• Once found, it retrieves the data from top.
• Next, give the suggestion of words.

Python implementation:

class TrieNodeEg:

    def __init__(T_self):

        T_self.children = {}

        T_self.is_end_of_word = False

class Trie1:

    def __init__(T_self):

        T_self.root = TrieNodeEg()

    def add(T_self, word):

        node = T_self.root

        for char in word:

            node = node.children.setdefault(char, TrieNodeEg())

        node.is_end_of_word = True

    def _dfs(T_self, node, prefix, results):

        if node.is_end_of_word:

            results.append(prefix)

        for char, child in node.children.items():

            T_self._dfs(child, prefix + char, results)

     def autocompleteIt(T_self, prefix):

        node = T_self.root

        for char in prefix:

            if char not in node.children:

                return []

            node = node.children[char]

        results = []

        T_self._dfs(node, prefix, results)

        return results

 def main():

    trie1 = Trie1()

    words = ["banana","bat","car","cat", "carrot","dog","dot"]

    for word in words:

        trie1.add(word)

     while True:

        prefix = input("\nEnter a prefix as input (or 'exit' to quit): ").strip()

        if prefix.lower() == "exit":

            break

        suggestions = trie1.autocompleteIt(prefix)

        if suggestions:

            print("Here are the Suggestions:", suggestions)

        else:

            print("sorry, No matches found.")

 if __name__ == "__main__":

    main()

Output:

C:\raji>py TrieNodeEg.py

Enter a prefix as input (or 'exit' to quit): ca

Here are the Suggestions: ['car', 'carrot', 'cat']

Enter a prefix as input (or 'exit' to quit): ba

Here are the Suggestions: ['banana', 'bat']

Enter a prefix as input (or 'exit' to quit): do

Here are the Suggestions: ['dog', 'dot']

Enter a prefix as input (or 'exit' to quit): exit

This code is useful to you because it is scalable, memory usage is less. One more added advantage is its time complexity.