Design A Search Autocomplete System In C++

Introduction

Ensuring excellent user experience in modern applications can be significantly achieved by incorporating well-designed user interfaces. Features like the 'autocomplete' functionality, which is very popular in search engines, websites, and applications, aid in this aspect. Autocomplete assists users throughout the type in the queries by suggesting several possible questions or input, which makes searching a lot faster and more accurate. In this paper, we will discuss designing a search autocomplete algorithm in C++ that is high-performing, easy to use as well and scalable.

Problem Statement

The aim is to build a system in which a user types only part of a search query, and this system automatically generates related phrases or sentences as suggestions. This system has to be able to support large datasets and efficiently execute them in real time.

Requirements

✅ Input: A group of input search phrases represented as a dictionary or lexicon and the user text input string.
✅ Output: A list of possible search contracts that the user will be presented with and that will be sorted based on user input (most likely by popularity or through an alphabetizer).

Challenges:

✅ Substantive Efficiency: The system has to provide the users with suggestions instantaneously, even when a soft user has a search string list of many terms.
✅ Scalability: It does not have scalability limitations that restrict its operation to a certain limited number of search terms.
✅ Memory Usage: The optimization of memory usage of the system needs to be perfected, thus enabling it to handle a large dataset without compromising performance speed.
✅ Relevance: The system should order suggestions by factors such as frequency of past searches or alphabetical order.

Solution Approach

In order to tackle this problem, we will be employing different kinds of data structure , especially Tries (prefix trees), which tend to be the most efficient when it comes to problems that involve operations that deal with strings, such as prefix searching. With this data structure, we will be able to store search phrases and retrieve all the words which have a given prefix and this will take linear time relative to the length of the prefix.

Data Structure: Trie (Prefix Tree)

A trie is a tree structure that holds strings, and each character is represented as a node. This has the effect of making it particularly suitable for solving search problems that are based on prefixes. In our system:

✅ Each node of the trie will be a map such that it will explain the child nodes which express the possible following characters.
✅ The leaf nodes will form a boundary to the valuable word ending.
✅ In every leaf node, we can also include some more information regarding the words, such as how many times the word has been used for recommendations.

High-Level Design

✅ Insert Operation: Each searching word will be inserted in the trie. With respect to each character of the term, walk around the trie, creating new nodes when needed.
✅ Search Operation: With respect to a given input prefix, search the trie by starting at the root node and following the sub-nodes that correspond to the prefix. When the prefix has been completely matched, use depth-first search (DFS) to search for all the valid forms that start with that prefix.
✅ Relevance Ranking: Based on factors like the number of appearances of a particular word or the order in which words are listed, the results can be grouped.

Program 1:

Example


#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// Trie Node class
class TrieNode {
public:
    unordered_map<char, TrieNode*> children;  // Map to store children nodes
    bool isEndOfWord;  // To check if the node represents end of a word
    int frequency;  // To store word frequency for ranking
    
    TrieNode() {
        isEndOfWord = false;
        frequency = 0;
    }
};

// Trie class
class Trie {
private:
    TrieNode* root;

    // Helper function to perform DFS and collect words
    void dfs(TrieNode* node, string prefix, vector<pair<string, int>>& suggestions) {
        if (node->isEndOfWord) {
            suggestions.push_back({prefix, node->frequency});
        }
        for (auto& [ch, childNode] : node->children) {
            dfs(childNode, prefix + ch, suggestions);
        }
    }

public:
    Trie() {
        root = new TrieNode();
    }

    // Function to insert a word into the Trie
    void insert(const string& word, int frequency) {
        TrieNode* current = root;
        for (char ch : word) {
            if (current->children.find(ch) == current->children.end()) {
                current->children[ch] = new TrieNode();
            }
            current = current->children[ch];
        }
        current->isEndOfWord = true;
        current->frequency = frequency;
    }

    // Function to search for autocomplete suggestions based on a prefix
    vector<string> getAutoCompleteSuggestions(const string& prefix) {
        TrieNode* current = root;
        vector<pair<string, int>> suggestions;  // To store suggestions and their frequencies
        vector<string> result;

        // Traverse the Trie to the end of the prefix
        for (char ch : prefix) {
            if (current->children.find(ch) == current->children.end()) {
                return result;  // No suggestions if the prefix doesn't exist
            }
            current = current->children[ch];
        }

        // Perform DFS from the end of the prefix
        dfs(current, prefix, suggestions);

        // Sort the suggestions by frequency (and alphabetically for ties)
        sort(suggestions.begin(), suggestions.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
            if (a.second == b.second) {
                return a.first < b.first;  // Lexicographical order
            }
            return a.second > b.second;  // Higher frequency first
        });

        // Collect the sorted suggestions
        for (auto& suggestion : suggestions) {
            result.push_back(suggestion.first);
        }

        return result;
    }
};

int main() {
    Trie trie;
    
    // Insert search terms with frequencies
    trie.insert("apple", 5);
    trie.insert("app", 10);
    trie.insert("application", 7);
    trie.insert("apex", 3);
    trie.insert("bat", 8);
    trie.insert("batch", 4);
    
    string query = "ap";
    vector<string> suggestions = trie.getAutoCompleteSuggestions(query);
    
    cout << "Autocomplete suggestions for \"" << query << "\":" << endl;
    for (const string& suggestion : suggestions) {
        cout << suggestion << endl;
    }

    return 0;
}

Output:

Output


Autocomplete suggestions for "ap":
app
application
apple
apex

Explanation:

✅ Trie Insertion: The function insert employs a word along with its corresponding frequency and inserts it in the Trie one character at a time.
✅ Prefix Search: The function getAutoCompleteSuggestions begins by first locating the node for the last character of the prefix string in the Trie by locating the prefix string in the Trie with the previous character of the prefix string. Then, she goes to deepen the graph to collect all the possible versions.
✅ Sorting: The first frequency sorts the suggestions, and the second frequency sorts words of the same frequency lexicographically.

Time and Space Complexity Insertion:

✅ Each of the insertions of a word takes O(L). Here, L is the number of letters in a word that is being added.
✅ Autocomplete Query: For a prefix search, the time sought is O(P). In this case, P stands for the number of letters in the prefix. The depth-first search in order to gather completers takes O(WL) where W refers to words assuming the prefix and L the mean number of characters in words. For sorting purposes, O(W log W) is another addition by sorting.
✅ Space: A Ternary search trie uses O(NL) space complexity where N refers to the number of words while L means the mean length of the words.

Program 2: Advanced Search Autocomplete System in C++ with Radix Trees

Example


#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <memory>

// Class representing each node in the Radix Tree
class RadixTreeNode {
public:
    std::unordered_map<std::string, std::unique_ptr<RadixTreeNode>> children;
    bool isEndOfWord;
    int frequency;
    std::string word;

    RadixTreeNode() : isEndOfWord(false), frequency(0) {}
};

// Radix Tree class
class RadixTree {
private:
    std::unique_ptr<RadixTreeNode> root;

    void collectSuggestions(RadixTreeNode* node, std::vector<std::pair<std::string, int>>& suggestions) {
        if (node->isEndOfWord) {
            suggestions.push_back({ node->word, node->frequency });
            std::cout << "Found word: " << node->word << " with frequency: " << node->frequency << std::endl;  // Debug output
        }
        for (auto& childPair : node->children) {
            std::string prefix = childPair.first;
            RadixTreeNode* child = childPair.second.get();
            collectSuggestions(child, suggestions);
        }
    }

    RadixTreeNode* findNodeWithPrefix(const std::string& prefix) {
        RadixTreeNode* current = root.get();
        size_t i = 0;
        while (i < prefix.length()) {
            bool found = false;
            for (auto& childPair : current->children) {
                std::string edge = childPair.first;
                RadixTreeNode* child = childPair.second.get();
                size_t j = 0;
                while (i + j < prefix.length() && j < edge.length() && prefix[i + j] == edge[j]) {
                    ++j;
                }
                if (j == edge.length()) {
                    current = child;
                    i += j;
                    found = true;
                    break;
                }
            }
            if (!found) {
                std::cout << "Prefix '" << prefix << "' not found!" << std::endl;  // Debug output
                return nullptr;
            }
        }
        std::cout << "Node found for prefix: " << prefix << std::endl;  // Debug output
        return current;
    }

public:
    RadixTree() : root(std::unique_ptr<RadixTreeNode>(new RadixTreeNode())) {}

    void insert(const std::string& word, int frequency) {
        std::cout << "Inserting word: " << word << " with frequency: " << frequency << std::endl;  // Debug output
        RadixTreeNode* current = root.get();
        size_t i = 0;
        while (i < word.length()) {
            bool found = false;
            for (auto& childPair : current->children) {
                std::string edge = childPair.first;
                RadixTreeNode* child = childPair.second.get();
                size_t j = 0;
                while (i + j < word.length() && j < edge.length() && word[i + j] == edge[j]) {
                    ++j;
                }
                if (j > 0) {
                    if (j < edge.length()) {
                        std::unique_ptr<RadixTreeNode> newChild(new RadixTreeNode());
                        newChild->children[edge.substr(j)] = std::move(childPair.second);
                        current->children[edge.substr(0, j)] = std::move(newChild);
                    }
                    current = current->children[edge.substr(0, j)].get();
                    i += j;
                    found = true;
                    break;
                }
            }
            if (!found) {
                std::cout << "Creating new edge: " << word.substr(i) << std::endl;  // Debug output
                current->children[word.substr(i)] = std::unique_ptr<RadixTreeNode>(new RadixTreeNode());
                current = current->children[word.substr(i)].get();
                break;
            }
        }
        current->isEndOfWord = true;
        current->word = word;
        current->frequency = frequency;
    }

    std::vector<std::string> getAutoCompleteSuggestions(const std::string& prefix) {
        std::vector<std::pair<std::string, int>> suggestions;
        std::vector<std::string> result;

        RadixTreeNode* node = findNodeWithPrefix(prefix);
        if (!node) {
            return result;
        }

        collectSuggestions(node, suggestions);

        std::sort(suggestions.begin(), suggestions.end(), [](const std::pair<std::string, int>& a, const std::pair<std::string, int>& b) {
            if (a.second == b.second) {
                return a.first < b.first;
            }
            return a.second > b.second;
        });

        for (const auto& suggestion : suggestions) {
            result.push_back(suggestion.first);
        }

        return result;
    }
};

// Main class to handle autocomplete system
class AutoCompleteSystem {
private:
    RadixTree tree;

public:
    AutoCompleteSystem() {}

    void insertSearchTerm(const std::string& term, int frequency) {
        tree.insert(term, frequency);
    }

    std::vector<std::string> getSuggestions(const std::string& prefix) {
        return tree.getAutoCompleteSuggestions(prefix);
    }
};

// Test the autocomplete system
int main() {
    AutoCompleteSystem autoComplete;

    // Insert search terms
    autoComplete.insertSearchTerm("apple", 20);
    autoComplete.insertSearchTerm("app", 25);
    autoComplete.insertSearchTerm("application", 15);
    autoComplete.insertSearchTerm("apex", 10);
    autoComplete.insertSearchTerm("apartment", 8);
    autoComplete.insertSearchTerm("bat", 30);
    autoComplete.insertSearchTerm("batch", 12);

    std::string query = "ap";
    std::vector<std::string> suggestions = autoComplete.getSuggestions(query);

    std::cout << "Autocomplete suggestions for \"" << query << "\":" << std::endl;
    for (const std::string& suggestion : suggestions) {
        std::cout << suggestion << std::endl;
    }

    return 0;
}

Output:

Output


Inserting word: apple with frequency: 20
Creating new edge: apple
Inserting word: app with frequency: 25
Inserting word: application with frequency: 15
Creating new edge: ication
Inserting word: apex with frequency: 10
Creating new edge: ex
Inserting word: apartment with frequency: 8
Creating new edge: artment
Inserting word: bat with frequency: 30
Creating new edge: bat
Inserting word: batch with frequency: 12
Creating new edge: ch
Node found for prefix: ap
Found word: apartment with frequency: 8
Found word: apex with frequency: 10
Found word: app with frequency: 25
Found word: application with frequency: 15
Found word: apple with frequency: 20

Explanation:

✅ Radix Tree Insertion: The Radix Tree optimizes the standard Trie by compressing paths with a single branch into one edge. This saves memory and reduces traversal time.
✅ Radix Tree Search: Given a prefix, the tree is traversed to find the corresponding node that matches the prefix. From there, a depth-first search collects all the possible completions.
✅ Caching Frequent Searches: The SearchCache class stores the results of frequently searched queries, allowing faster retrieval for subsequent searches. If the cache exceeds the capacity, it removes the least recently used prefix from the cache.
✅ Dynamic Ranking: Suggestions are ranked based on their frequency. This system also supports adding more metadata like user interactions or recency to enhance the ranking further.
✅ The Radix Tree optimizes the standard Trie by compressing paths with a single branch into one edge. This saves memory and reduces traversal time.
✅ Given a prefix, the tree is traversed to find the corresponding node that matches the prefix. From there, a depth-first search collects all the possible completions.
✅ The SearchCache class stores the results of frequently searched queries, allowing faster retrieval for subsequent searches. If the cache exceeds the capacity, it removes the least recently used prefix from the cache.
✅ Suggestions are ranked based on their frequency. This system also supports adding more metadata like user interactions or recency to enhance the ranking further.

Conclusion:

In conclusion, the use of a trie-based approach for the design of search autocomplete systems is not only faster but also easy to scale. This system provides in no time suggestions as it works flawlessly in an environment of extensive data with the aid of prefix search. With additional optimizations, such as caching frequently searched prefixes, the system can be further enhanced to meet the demands of real-world applications.

Introduction

Problem Statement

Requirements

Challenges:

Solution Approach

Data Structure: Trie (Prefix Tree)

Program 1:

Explanation:

Time and Space Complexity Insertion:

Program 2: Advanced Search Autocomplete System in C++ with Radix Trees

Explanation:

Conclusion:

Input Required