autocomplete using trie Algorithm

The autocomplete using Trie Algorithm is a highly efficient technique employed in applications such as text editors, search engines, and messaging apps to predict and suggest the possible word completions for a given prefix. Trie, also known as a prefix tree or digital tree, is a tree data structure that allows quick retrieval of words based on their prefixes. Each node in the trie represents a single character of a word, and the edges between the nodes denote the character connections in the words. The primary advantage of using a trie for autocomplete functionality is the fast search and insertion capabilities, which enable the efficient suggestion of relevant completions in real-time. For implementing an autocomplete system using the trie algorithm, a trie data structure is first constructed by inserting all the words from the given dictionary. Whenever a user inputs a sequence of characters, the algorithm traverses the trie, following the path of the input prefix. As soon as the last character of the prefix is encountered, the algorithm performs a depth-first search (DFS) on the remaining subtree to identify all possible word completions. These completions are then returned to the user as suggestions, significantly enhancing the user experience by reducing typing effort and minimizing the occurrence of spelling errors. The trie-based autocomplete system can also be extended to support advanced features such as frequency-based suggestions and auto-correction.
END = "#"


class Trie:
    def __init__(self):
        self._trie = {}

    def insert_word(self, text):
        trie = self._trie
        for char in text:
            if char not in trie:
                trie[char] = {}
            trie = trie[char]
        trie[END] = True

    def find_word(self, prefix):
        trie = self._trie
        for char in prefix:
            if char in trie:
                trie = trie[char]
            else:
                return []
        return self._elements(trie)

    def _elements(self, d):
        result = []
        for c, v in d.items():
            if c == END:
                sub_result = [" "]
            else:
                sub_result = [c + s for s in self._elements(v)]
            result.extend(sub_result)
        return tuple(result)


trie = Trie()
words = ("depart", "detergent", "daring", "dog", "deer", "deal")
for word in words:
    trie.insert_word(word)


def autocomplete_using_trie(s):
    """
    >>> trie = Trie()
    >>> for word in words:
    ...     trie.insert_word(word)
    ...
    >>> matches = autocomplete_using_trie("de")

    "detergent " in matches
    True
    "dog " in matches
    False
    """
    suffixes = trie.find_word(s)
    return tuple(s + w for w in suffixes)


def main():
    print(autocomplete_using_trie("de"))


if __name__ == "__main__":
    main()

LANGUAGE:

DARK MODE: