Autocomplete System Using Trie in Go

A Trie (pronounced “try”) is a tree-like data structure that stores a dynamic set of strings, where the keys are usually strings. It is highly efficient for retrieval operations, such as searching for a word in a dictionary. In this implementation, we will use a Trie to design an autocomplete system that suggests words based on a given prefix.

Program Structure

The Go program implementing the autocomplete system using a Trie is structured into the following components:

1. TrieNode Struct: This struct represents a node in the Trie, containing a map of child nodes and a boolean indicating if the node represents the end of a word.
2. Trie Struct: This struct represents the Trie itself, containing the root node.
3. Insert Method: This method inserts a word into the Trie.
4. SearchPrefix Method: This method searches for the node corresponding to a given prefix in the Trie.
5. Autocomplete Method: This method returns a list of all words in the Trie that start with a given prefix.
6. CollectWords Method: This helper method recursively collects all words that can be formed from a given node in the Trie.

Go Code Implementation

package main

import "fmt"

// TrieNode represents a node in the Trie
type TrieNode struct {
    children map[rune]*TrieNode // Map of child nodes
    isEnd    bool               // Is true if the node represents the end of a word
}

// Trie represents the Trie structure
type Trie struct {
    root *TrieNode // Root node of the Trie
}

// NewTrie creates a new Trie
func NewTrie() *Trie {
    return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}

// Insert inserts a word into the Trie
func (t *Trie) Insert(word string) {
    node := t.root
    for _, char := range word {
        if _, exists := node.children[char]; !exists {
            node.children[char] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[char]
    }
    node.isEnd = true
}

// SearchPrefix searches for the node corresponding to the given prefix in the Trie
func (t *Trie) SearchPrefix(prefix string) *TrieNode {
    node := t.root
    for _, char := range prefix {
        if _, exists := node.children[char]; !exists {
            return nil
        }
        node = node.children[char]
    }
    return node
}

// Autocomplete returns a list of words in the Trie that start with the given prefix
func (t *Trie) Autocomplete(prefix string) []string {
    results := []string{}
    node := t.SearchPrefix(prefix)
    if node != nil {
        t.collectWords(node, prefix, &results)
    }
    return results
}

// collectWords recursively collects all words that can be formed from the given node
func (t *Trie) collectWords(node *TrieNode, prefix string, results *[]string) {
    if node.isEnd {
        *results = append(*results, prefix)
    }
    for char, childNode := range node.children {
        t.collectWords(childNode, prefix+string(char), results)
    }
}

func main() {
    // Create a new Trie and insert some words
    trie := NewTrie()
    words := []string{"apple", "app", "apricot", "banana", "band", "bandana", "bandit"}
    for _, word := range words {
        trie.Insert(word)
    }

    // Test the autocomplete function
    prefix := "ban"
    fmt.Printf("Autocomplete results for prefix '%s':\n", prefix)
    for _, word := range trie.Autocomplete(prefix) {
        fmt.Println(word)
    }
}
    

Explanation of the Code

Here’s a breakdown of the code:

• TrieNode Struct: The TrieNode struct represents each node in the Trie. It contains a map of child nodes, where each key is a character, and a boolean isEnd that indicates if the node represents the end of a word.
• Trie Struct: The Trie struct represents the Trie itself and contains the root node.
• Insert Method: This method inserts a word into the Trie by iterating over each character in the word and creating the necessary child nodes if they don’t already exist.
• SearchPrefix Method: This method searches for the node corresponding to a given prefix in the Trie. It returns the node if the prefix exists or nil if it doesn’t.
• Autocomplete Method: This method returns a list of all words in the Trie that start with a given prefix. It first finds the node corresponding to the prefix using SearchPrefix and then collects all possible words from that node using collectWords.
• CollectWords Method: This helper method recursively traverses the Trie from a given node, appending all complete words (where isEnd is true) to the results slice.

Usage Example

Here’s an example of how you might use this Trie-based autocomplete system in a Go program:

func main() {
    // Create a new Trie and insert some words
    trie := NewTrie()
    words := []string{"apple", "app", "apricot", "banana", "band", "bandana", "bandit"}
    for _, word := range words {
        trie.Insert(word)
    }

    // Test the autocomplete function
    prefix := "ban"
    fmt.Printf("Autocomplete results for prefix '%s':\n", prefix)
    for _, word := range trie.Autocomplete(prefix) {
        fmt.Println(word)
    }
}
    

Conclusion

This Go program demonstrates a basic implementation of an autocomplete system using a Trie data structure. Tries are highly efficient for prefix-based queries, making them ideal for applications like autocomplete, spell-checking, and dictionary implementations. The structure allows for fast insertion, search, and prefix-based word retrieval.