C++ 中设计搜索自动完成系统

2025年5月10日 | 阅读 9 分钟

引言

在现代应用程序中，通过整合精心设计的用户界面，可以显著提升用户体验。诸如搜索自动补全功能等特性在搜索引擎、网站和应用程序中非常流行，它们在这方面发挥了作用。自动补全通过建议几个可能的查询或输入，帮助用户完成查询输入，从而使搜索更快、更准确。在本文中，我们将讨论如何设计一个高性能、易用且可扩展的 C++ 搜索自动补全算法。

问题陈述

目标是构建一个系统，用户只需输入搜索查询的一部分，该系统就会自动生成相关的短语或句子作为建议。该系统必须能够支持大型数据集并实时高效地执行它们。

要求

输入： 一组输入搜索短语（表示为字典或词典）和用户文本输入字符串。
输出： 一个可能的搜索合约列表，将呈现给用户并根据用户输入进行排序（最有可能按受欢迎程度或按字母顺序排列）。

挑战

实质性效率： 系统必须即时向用户提供建议，即使软用户有包含许多术语的搜索字符串列表。
可扩展性： 它没有限制其操作到某个有限数量的搜索词的可扩展性限制。
内存使用： 需要完善系统内存使用优化，从而使其能够在不影响性能速度的情况下处理大型数据集。
相关性： 系统应根据过去搜索的频率或字母顺序等因素对建议进行排序。

解决方案方法

为了解决这个问题，我们将采用不同类型数据结构，特别是 Trie（前缀树），它在涉及字符串操作（如前缀搜索）的问题中往往是最有效的。通过这种数据结构，我们将能够存储搜索短语并检索所有具有给定前缀的单词，这将花费与前缀长度成线性关系的时间。

数据结构：Trie（前缀树）

Trie 是一种存储字符串的树形结构，每个字符都表示为一个节点。这使得它特别适合解决基于前缀的搜索问题。在我们的系统中

Trie 的每个节点都将是一个映射，它将解释表示可能的后续字符的子节点。
叶节点将形成有价值的单词结尾的边界。
在每个叶节点中，我们还可以包含一些关于单词的更多信息，例如该单词被用于推荐的次数。

高层设计

插入操作： 每个搜索词都将插入到 Trie 中。对于术语的每个字符，遍历 Trie，在需要时创建新节点。
搜索操作： 对于给定的输入前缀，从根节点开始搜索 Trie，并跟随与前缀对应的子节点。当前缀完全匹配后，使用深度优先搜索（DFS）搜索所有以该前缀开头的有效形式。
相关性排名： 结果可以根据特定单词出现的次数或单词的排列顺序等因素进行分组。

程序 1

 
#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;
}   

输出

 
Autocomplete suggestions for "ap":
app
application
apple
apex

说明

Trie 插入： `insert` 函数使用一个单词及其对应的频率，并将其逐个字符地插入到 Trie 中。
前缀搜索： `getAutoCompleteSuggestions` 函数首先通过定位前缀字符串中前一个字符在 Trie 中的节点来找到前缀字符串中最后一个字符在 Trie 中的节点。然后，它深入图表以收集所有可能的版本。
排序： 首先按频率对建议进行排序，然后按相同频率的单词进行字典序排序。

时间和空间复杂度插入

每个单词的插入操作需要 O(L) 时间。这里，L 是正在添加的单词中的字母数量。
自动补全查询： 对于前缀搜索，所需时间为 O(P)。在这种情况下，P 表示前缀中的字母数量。深度优先搜索以收集补全项需要 O(WL) 时间，其中 W 表示假设该前缀的单词数量，L 表示单词的平均字符数。为了排序，O(W log W) 是排序的另一个附加项。
空间： 三叉搜索树使用 O(NL) 的空间复杂度，其中 N 指的是单词的数量，L 表示单词的平均长度。

程序 2：使用基数树的 C++ 高级搜索自动补全系统

 
#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;
}   

输出

 
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

说明

基数树插入
- 基数树通过将具有单个分支的路径压缩成一条边来优化标准 Trie。这节省了内存并减少了遍历时间。
基数树搜索
- 给定一个前缀，遍历树以找到与该前缀匹配的相应节点。从那里，通过深度优先搜索收集所有可能的补全。
缓存频繁搜索
- `SearchCache` 类存储频繁搜索查询的结果，从而使后续搜索更快地检索。如果缓存超出容量，它会从缓存中删除最近最少使用的前缀。
动态排名
- 建议根据其频率进行排名。此系统还支持添加更多元数据，例如用户交互或近期性，以进一步增强排名。

结论

总而言之，使用基于 Trie 的方法设计搜索自动补全系统不仅速度更快，而且易于扩展。该系统借助前缀搜索，在大量数据的环境中完美运行，即时提供建议。通过额外的优化，例如缓存频繁搜索的前缀，可以进一步增强系统以满足实际应用的需求。

下一个主题C++ 中的可重构数

C++ 中设计搜索自动完成系统

引言

问题陈述

要求

挑战

解决方案方法

数据结构：Trie（前缀树）

程序 1

说明

时间和空间复杂度插入

程序 2：使用基数树的 C++ 高级搜索自动补全系统

说明

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中设计搜索自动完成系统

引言

问题陈述

要求

挑战

解决方案方法

数据结构：Trie（前缀树）

程序 1

说明

时间和空间复杂度插入

程序 2：使用基数树的 C++ 高级搜索自动补全系统

说明

结论

相关帖子

C++ 中的不区分大小写搜索

C++ Std::pmr::monotonic_buffer_resource

C++ 中的莫比乌斯函数计算

C++ 替罪羊树

C++ 中的索菲·热尔曼素数

C++ 位操作

C++ 中的施泰纳树近似

C++ Jaccard 相似系数