Creating a Python Autocomplete App with Tkinter and Trie Tree

Autocomplete features have become an essential part of modern user interfaces, enhancing user experience by providing real-time suggestions as users type. From search engines to messaging apps, the ability to predict and suggest text not only saves time but also improves accuracy. In this article, we will explore how to build a simple yet powerful autocomplete application using Python.

Leveraging the Tkinter library for the graphical user interface (GUI) and Trie data structures for efficient prefix-based searches, we’ll walk through the process of creating a responsive application that updates suggestions in real-time. Whether you’re a beginner looking to expand your Python skills or an experienced developer interested in GUI development and data structures, this tutorial will provide a comprehensive guide to building your own autocomplete feature.

By the end of this article, you’ll have a deeper understanding of how to integrate Tries with Tkinter to create intuitive and dynamic user interfaces, paving the way for more advanced applications and projects.

Building an Autocomplete Application in Python Using Tkinter and Trie Data Structures

Trie Tree Data Structure

Tries are a specialized data structure that excel at handling prefix-based searches, making them perfect for implementing autocomplete features. In this tutorial, we’ll use Python’s Tkinter library to build a simple autocomplete application powered by a Trie.

For a more in-depth exploration of Trie data structures, check out my Medium post on Tries.

What is a Trie or Prefix tree

Code

from tkinter import Tk, Entry, Listbox, END
from collections import defaultdict


class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.is_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            node = node.children[char]
        node.is_word = True

    def search(self, prefix):
        node = self.root
        suggestions = []
        for char in prefix:
            if char not in node.children:
                return suggestions
            node = node.children[char]
        self._find_suggestions(node, prefix, suggestions)
        return suggestions

    def _find_suggestions(self, node, prefix, suggestions):
        if node.is_word:
            suggestions.append(prefix)
        for char, child in node.children.items():
            self._find_suggestions(child, prefix + char, suggestions)


def load_words(filename):
    words = set()
    with open(filename, 'r') as f:
        for line in f:
            words.update(line.strip().split())
    return words


def update_suggestions(event, trie, entry, suggestions_listbox):
    prefix = entry.get()
    if not prefix:
        suggestions_listbox.delete(0, END)
        return
    suggestions = trie.search(prefix)
    suggestions_listbox.delete(0, END)
    for suggestion in suggestions:
        suggestions_listbox.insert(END, suggestion)


def main():
    words = load_words("words.txt")  # Replace with your word file path
    trie = Trie()
    for word in words:
        trie.insert(word)

    root = Tk()
    root.title("Autocomplete App")

    entry = Entry(root)
    entry.pack(padx=10, pady=10)
    entry.bind("<KeyRelease>", lambda e: update_suggestions(e, trie, entry, suggestions_listbox))

    suggestions_listbox = Listbox(root, width=50)
    suggestions_listbox.pack(padx=10, pady=10)

    root.mainloop()


if __name__ == "__main__":
    main()

Required modules

from tkinter import Tk, Entry, Listbox, END
from collections import defaultdict

Tkinter is a standard GUI library in Python, used to create graphical user interfaces. This line imports specific classes and constants from the Tkinter module:

from tkinter import Tk, Entry, Listbox, END

• Tk initializes the main application window.
• Entry allows users to type in a prefix.
• Listbox displays the autocomplete suggestions.
• END is used to clear and update the Listbox.

The collections module in Python provides alternative data structures to Python's built-in containers (like lists, dictionaries, etc.). This line imports the defaultdict class from the collections module:

from collections import defaultdict

When a key that does not exist in the dictionary is accessed, defaultdict automatically creates an entry for it using a specified default factory function. This is useful for avoiding KeyError exceptions and simplifying the code.

In the context of a Trie, defaultdict can be used to initialize child nodes automatically when traversing or inserting nodes.

TrieNode Class

This code defines the TrieNode class, which is a fundamental building block for creating a Trie data structure, used to implement efficient autocomplete features.

class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.is_word = False

• self.children: A dictionary where each key is a character and the corresponding value is another TrieNode. Using defaultdict(TrieNode), any non-existing key automatically creates a new TrieNode, simplifying node creation during insertion.
• self.is_word: A boolean flag that indicates whether the node represents the end of a valid word in the Trie. Initially set to False.

This class is used to create nodes that will form the Trie, enabling efficient storage and retrieval of words for autocomplete functionality.

Trie Class

The Trie class represents a Trie data structure, which is used to efficiently store and retrieve keys in a dataset of strings. Each node in the Trie represents a single character of a word, and the entire structure can be used to implement efficient prefix-based search operations, such as autocomplete.

__init__ Method

Initializes a new instance of the Trie class and creates a root node, which is an instance of the TrieNode class. This root node serves as the starting point for all insert and search operations.

class Trie:
    def __init__(self):
        self.root = TrieNode()

insert Method

Starts at the root node and iterates through each character of the word. For each character, it moves to the corresponding child node, creating new nodes as needed. Marks the final node as a complete word by setting is_word to True.

def insert(self, word):
    node = self.root
    for char in word:
        node = node.children[char]
    node.is_word = True

Initialization

node = self.root

The method starts by initializing a node variable to the root of the Trie. This node will be used to traverse through the Trie as the word is inserted.

Traversing and Creating Nodes

for char in word:
    node = node.children[char]

• The method iterates over each character char in the word.
• For each character, it checks if there is already a child node corresponding to that character in the current node’s children dictionary.
• If the child node exists, it moves to that node.
• If the child node does not exist, it creates a new TrieNode (thanks to the defaultdict(TrieNode)) and then moves to this newly created node.
• This step ensures that all characters in the word are linked in a chain of nodes.

Marking the End of the Word

node.is_word = True

• After all characters of the word have been processed, the method marks the current node (the node corresponding to the last character of the word) as the end of a valid word by setting its is_word attribute to True.
• This marking is crucial as it differentiates between prefixes that are also complete words and prefixes that are not complete words in the Trie.

Consider inserting the word “cat” into an empty Trie:

Initialization:

• Start at the root node.

Processing ‘c’:

• The root has no child node for ‘c’, so a new node for ‘c’ is created.
• Move to the node representing ‘c’.

Processing ‘a’:

• The node for ‘c’ has no child node for ‘a’, so a new node for ‘a’ is created.
• Move to the node representing ‘a’.

Processing ‘t’:

• The node for ‘a’ has no child node for ‘t’, so a new node for ‘t’ is created.
• Move to the node representing ‘t’.

Marking the End:

• The node for ‘t’ is marked as the end of the word by setting is_word to True.

The Trie now has a path from the root to a node representing ‘t’, with is_word set to True at the 't' node, indicating the end of the word "cat".

search Method

The search method in the Trie class is designed to find and return all words in the Trie that start with a given prefix. Here's a step-by-step description of how it works:

def search(self, prefix):
    node = self.root
    suggestions = []
    for char in prefix:
        if char not in node.children:
            return suggestions
        node = node.children[char]
    self._find_suggestions(node, prefix, suggestions)
    return suggestions

Initialization

node = self.root
suggestions = []

• The method starts by initializing a node variable to the root of the Trie. This node will be used to traverse the Trie as the prefix is processed.
• An empty list suggestions is initialized to store the words that match the prefix.

Traversing the Trie for the Prefix

for char in prefix:
    if char not in node.children:
        return suggestions
    node = node.children[char]

• The method iterates over each character char in the prefix.
• For each character, it checks if there is a child node corresponding to that character in the current node’s children dictionary.
• If the character is not found in the children, the method immediately returns the empty suggestions list, indicating that no words with the given prefix exist in the Trie.
• If the character is found, it moves to the corresponding child node, continuing this process until all characters in the prefix have been processed.

Finding All Suggestions

self._find_suggestions(node, prefix, suggestions)

• After successfully traversing the Trie to the end of the prefix, the method calls _find_suggestions with the current node, the prefix, and the suggestions list.
• This helper method recursively traverses all child nodes from the current node, collecting all complete words that start with the given prefix and adding them to the suggestions list.

Returning the Suggestions

return suggestions

The method returns the list of suggestions that match the given prefix.

Consider searching for the prefix “ca” in a Trie that contains the words “cat”, “car”, “cart”, and “dog”:

Initialization:

• Start at the root node.
• Initialize an empty suggestions list.

Processing ‘c’:

• The root has a child node for ‘c’, so move to the node representing ‘c’.

Processing ‘a’:

• The node for ‘c’ has a child node for ‘a’, so move to the node representing ‘a’.

Finding Suggestions:

• Call _find_suggestions on the node representing 'a' with the prefix "ca".
• _find_suggestions traverses the nodes for 't' and 'r', collecting the words "cat", "car", and "cart".

Returning Suggestions:

Return the list ["cat", "car", "cart"].

update_suggestions Method

he update_suggestions function is designed to update the suggestions shown in a Tkinter Listbox based on the current input in an Entry widget. This function is typically called whenever there is a key release event in the Entry widget, providing an autocomplete feature. Here's a step-by-step description of how it works:

def update_suggestions(event, trie, entry, suggestions_listbox):
    prefix = entry.get()
    if not prefix:
        suggestions_listbox.delete(0, END)
        return
    suggestions = trie.search(prefix)
    suggestions_listbox.delete(0, END)
    for suggestion in suggestions:
        suggestions_listbox.insert(END, suggestion)

Retrieve the Current Text from the Entry Widget

prefix = entry.get()

• The method starts by retrieving the current text (prefix) from the Entry widget using the get method. This text is what the user has typed so far and will be used to search for autocomplete suggestions.

Handle the Case Where the Entry is Empty

if not prefix:
    suggestions_listbox.delete(0, END)
    return

• If the Entry widget is empty (i.e., prefix is an empty string), the method clears all current suggestions in the Listbox by calling delete(0, END).
• The function then returns early because there are no suggestions to display when there is no input.

Search for Suggestions Based on the Prefix

suggestions = trie.search(prefix)

• The method searches for suggestions by calling the search method of the Trie object, passing the current prefix. This returns a list of words in the Trie that start with the given prefix.

Clear the Current Suggestions in the Listbox

suggestions_listbox.delete(0, END)

• Before adding new suggestions, the method clears any existing suggestions in the Listbox by calling delete(0, END). This ensures that only relevant suggestions based on the current prefix are displayed.

Add New Suggestions to the Listbox

for suggestion in suggestions:
    suggestions_listbox.insert(END, suggestion)

• The method iterates over the list of suggestions returned by the Trie search.
• For each suggestion, it inserts the suggestion into the Listbox using the insert method with the END parameter, which adds the item to the end of the list

Consider a scenario where the user types “ca” into the Entry widget:

The user types “c”:

• update_suggestions is called.
• The prefix is “c”.
• The Trie search returns words like “cat”, “car”, “cart”.
• The Listbox is updated to display these suggestions.

The user types “a”:

• update_suggestions is called again.
• The prefix is now “ca”.
• The Trie search refines the suggestions to “cat”, “car”, “cart”.
• The Listbox updates to show the refined suggestions.

Functions

load_words Function

The load_words function is designed to read words from a text file and store them in a set data structure. Here's a breakdown of its purpose and how it achieves this:

def load_words(filename):
    words = set()
    with open(filename, 'r') as f:
        for line in f:
            words.update(line.strip().split())
    return words

• filename: Takes a string argument representing the path to the text file containing words.
• words = set(): Initializes an empty set to store unique words.
• with open(filename, 'r') as f:: Opens the specified file (filename) in read mode ('r') using a context manager (with statement), ensuring the file is properly closed after reading.
• for line in f:: Iterates through each line in the file.
• line.strip().split(): Removes any leading/trailing whitespace from each line (strip()), splits the line into a list of words based on whitespace (split()), and updates the words set with these words.
• return words: Returns the set containing all unique words read from the file.

update_suggestions Function

def update_suggestions(event, trie, entry, suggestions_listbox):
    prefix = entry.get()
    if not prefix:
        suggestions_listbox.delete(0, END)
        return
    suggestions = trie.search(prefix)
    suggestions_listbox.delete(0, END)
    for suggestion in suggestions:
        suggestions_listbox.insert(END, suggestion)

• event: Represents the event trigger, typically a <KeyRelease> event from the Entry widget.
• trie: Instance of the Trie data structure (Trie class) used to store and retrieve words for autocomplete.
• entry: Tkinter Entry widget where the user inputs text for autocomplete.
• suggestions_listbox: Tkinter Listbox widget where autocomplete suggestions are displayed.
• prefix = entry.get(): Retrieves the current text input from the Entry widget (entry).
• if not prefix:: Checks if the input prefix is empty.
• suggestions_listbox.delete(0, END): Clears the Listbox (suggestions_listbox) if the prefix is empty, ensuring no suggestions are displayed.
• return: Exits the function early if the prefix is empty, as no further processing is needed.
• suggestions = trie.search(prefix): Uses the Trie's search method to find all words that start with the current prefix.
• suggestions_listbox.delete(0, END): Clears the Listbox (suggestions_listbox) to prepare for displaying new suggestions.
• for suggestion in suggestions:: Iterates through each suggestion retrieved from the Trie.
• suggestions_listbox.insert(END, suggestion): Inserts each suggestion into the Listbox (suggestions_listbox) at the end (END position), displaying them to the user for selection.

Main Function

    words = load_words("words.txt")  # Replace with your word file path
    trie = Trie()
    for word in words:
        trie.insert(word)

    root = Tk()
    root.title("Autocomplete App")

    entry = Entry(root)
    entry.pack(padx=10, pady=10)
    entry.bind("<KeyRelease>", lambda e: update_suggestions(e, trie, entry, suggestions_listbox))

    suggestions_listbox = Listbox(root, width=50)
    suggestions_listbox.pack(padx=10, pady=10)

    root.mainloop()

Loading Words from File

words = load_words("words.txt")  # Replace with your word file path

• Reads words from a text file specified by "words.txt" using the load_words function. This function reads the file and returns a set of words.

Creating and Populating the Trie

trie = Trie()
for word in words:
    trie.insert(word)

• Initializes an instance of the Trie class (trie).
• Iterates through each word in the words set obtained from the file.
• Inserts each word into the Trie using the insert method of the Trie class. This builds a data structure optimized for fast prefix-based searches.

Creating the GUI with Tkinter

root = Tk()
root.title("Autocomplete App")

• Initializes the main Tkinter window (root) and sets its title to "Autocomplete App".

Setting up the Entry Widget for Input

entry = Entry(root)
entry.pack(padx=10, pady=10)

• Creates an Entry widget (entry) within the main window (root) where the user can input text.
• Packs the Entry widget with 10 pixels of padding on the x and y axes.

Binding Entry Widget to Update Suggestions

entry.bind("<KeyRelease>", lambda e: update_suggestions(e, trie, entry, suggestions_listbox))

• Binds the <KeyRelease> event of the Entry widget (entry) to call the update_suggestions function whenever a key is released.
• Passes the event object (e), Trie data structure (trie), Entry widget (entry), and Listbox widget (suggestions_listbox) to the update_suggestions function.

Setting up the Listbox Widget for Suggestions

suggestions_listbox = Listbox(root, width=50)
suggestions_listbox.pack(padx=10, pady=10)

• Creates a Listbox widget (suggestions_listbox) within the main window (root) to display autocomplete suggestions.
• Sets the width of the Listbox to 50 characters.
• Packs the Listbox widget with 10 pixels of padding on the x and y axes.

Starting the Tkinter Event Loop

root.mainloop()

• Enters the Tkinter event loop, which listens for events (such as key presses, mouse clicks) and updates the GUI accordingly.
• Keeps the GUI window (root) open and responsive to user interactions until the window is closed.

__main__ Block

if __name__ == "__main__":
    main()

When a Python script is run, Python sets the special variable __name__ to "__main__" for the script being executed. If the script is imported as a module into another script, the __name__ variable is set to the name of the module instead of "__main__".

Sample Text File (words.txt)

the quick brown fox jumps over the lazy dog
a dusty old book lies on the shelf
the president gave a speech to the crowd
a large apple fell from the high tree
the children played in the park all day
the sun shone brightly on the summer day
the cat chased the mouse through the house
the train sped down the tracks
the boat sailed across the ocean
the plane flew high above the clouds
the stars twinkled in the night sky
the moon cast a silvery glow over the land
the fire crackled in the fireplace
the wind whistled through the trees
the rain poured down from the sky
the snow fell softly on the ground
the flowers bloomed in the spring
the birds sang their songs
the bees buzzed around the hive
the butterflies fluttered among the flowers
the fish swam in the pond
the frogs croaked in the marsh
the crickets chirped in the night
the owls hooted in the trees
the deer grazed in the meadow
the bears hibernated in their caves
the squirrels gathered nuts for the winter
the chipmunks hid their acorns in the ground
the birds flew south for the winter
the leaves changed color and fell from the trees
the days grew shorter and the nights grew longer
the air grew colder and the wind grew stronger
the first snowflakes fell on the ground
the children bundled up in their coats and hats
they went outside to play in the snow
they built a snowman and had a snowball fight
they laughed and played until they were tired
then they went inside to warm up by the fire
they drank hot chocolate and ate cookies
they told stories and sang songs
they were happy and cozy inside on a cold winter day

Read More

Find the names of the network interfaces by their IPs

My YouTube Channel

More shell script videos and linux tutorials on my YouTube Channel.