如何用C++结合string_view与字典压缩实现高性能前缀树搜索

前缀树（Trie）是一种用于快速检索字符串集合的多叉树结构，核心思想是利用字符串的公共前缀来减少查询时间，时间复杂度可优化到O(L)，L为待查询字符串的长度。传统前缀树实现中，每个节点都需要存储对应的字符以及子节点映射，同时插入字符串时往往会产生额外的拷贝开销，在大规模字符串场景下内存占用和性能都会受到影响。结合string_view和字典压缩可以有效解决这两个问题，提升前缀树的整体性能。

核心优化思路

string_view减少拷贝开销

传统前缀树插入字符串时，通常会将字符串拷贝到节点中存储，当字符串较长或者插入操作频繁时，拷贝开销会非常明显。C++17引入的string_view是字符串的只读视图，不会持有字符串的所有权，也不会发生拷贝，仅记录字符串的起始地址和长度，非常适合前缀树中不需要修改字符串内容的场景，用来传递字符串片段可以大幅降低内存拷贝成本。

字典压缩合并单分支节点

传统前缀树中，如果某个节点只有一个子节点，且不是终止节点，那么这个节点和子节点可以合并为一个节点，将原本两个节点存储的字符拼接起来。这种压缩方式可以减少节点的数量，降低内存占用，同时减少查询时的节点跳转次数，提升查询效率。

数据结构设计

首先定义压缩后的前缀树节点结构，每个节点存储压缩后的字符串片段，以及子节点映射和是否为终止节点的标记：

#include <string>
#include <string_view>
#include <unordered_map>
#include <vector>
#include <memory>

// 前缀树节点定义
struct TrieNode {
    std::string compressed_str; // 压缩后的字符串片段
    std::unordered_map<char, std::unique_ptr<TrieNode>> children; // 子节点映射
    bool is_end; // 是否为某个字符串的终止节点

    TrieNode() : is_end(false) {}
};

核心功能实现

插入字符串

插入逻辑需要先找到公共前缀，然后处理剩余部分的插入，同时触发压缩逻辑：

class CompressedTrie {
private:
    std::unique_ptr<TrieNode> root;

    // 查找节点中匹配的前缀长度
    int matchPrefix(const TrieNode* node, std::string_view str) {
        int len = 0;
        while (len < node->compressed_str.size() && len < str.size()) {
            if (node->compressed_str[len] != str[len]) {
                break;
            }
            len++;
        }
        return len;
    }

public:
    CompressedTrie() : root(std::make_unique<TrieNode>()) {}

    void insert(std::string_view str) {
        if (str.empty()) return;
        TrieNode* cur = root.get();
        size_t pos = 0;

        while (pos < str.size()) {
            std::string_view remaining = str.substr(pos);
            // 查找当前节点的子节点中是否有匹配的首字符
            auto it = cur->children.find(remaining[0]);
            if (it == cur->children.end()) {
                // 没有匹配的子节点，直接创建新节点存储剩余字符串
                auto new_node = std::make_unique<TrieNode>();
                new_node->compressed_str.assign(remaining.begin(), remaining.end());
                new_node->is_end = true;
                cur->children[remaining[0]] = std::move(new_node);
                return;
            }

            TrieNode* child = it->second.get();
            int match_len = matchPrefix(child, remaining);
            if (match_len == 0) {
                // 首字符不匹配，理论上不会走到这里，因为已经通过首字符找到子节点
                break;
            }

            if (match_len < child->compressed_str.size()) {
                // 部分匹配，需要拆分节点
                std::string common_part = child->compressed_str.substr(0, match_len);
                std::string remaining_child = child->compressed_str.substr(match_len);
                // 创建新的公共节点
                auto new_common_node = std::make_unique<TrieNode>();
                new_common_node->compressed_str = common_part;
                // 将原节点的剩余部分作为新子节点
                auto old_remaining_node = std::make_unique<TrieNode>();
                old_remaining_node->compressed_str = remaining_child;
                old_remaining_node->children = std::move(child->children);
                old_remaining_node->is_end = child->is_end;
                new_common_node->children[remaining_child[0]] = std::move(old_remaining_node);
                // 替换原节点
                cur->children[common_part[0]] = std::move(new_common_node);
                // 处理剩余待插入的字符串
                pos += match_len;
                if (pos >= str.size()) {
                    // 插入的字符串已经完全匹配公共部分，标记当前公共节点为终止节点
                    cur->children[common_part[0]]->is_end = true;
                } else {
                    // 还有剩余部分，创建新节点插入
                    std::string_view left_str = str.substr(pos);
                    auto new_node = std::make_unique<TrieNode>();
                    new_node->compressed_str.assign(left_str.begin(), left_str.end());
                    new_node->is_end = true;
                    cur->children[common_part[0]]->children[left_str[0]] = std::move(new_node);
                }
                return;
            } else {
                // 完全匹配当前节点的压缩字符串
                pos += match_len;
                if (pos >= str.size()) {
                    // 字符串已经全部插入，标记当前节点为终止节点
                    child->is_end = true;
                    return;
                }
                // 继续处理剩余部分
                cur = child;
            }
        }
    }
};

前缀搜索实现

前缀搜索需要遍历前缀树，找到所有以目标前缀开头的字符串：

    // 收集以当前节点为根的所有字符串
    void collectWords(TrieNode* node, std::string& current, std::vector<std::string>& result) {
        if (node->is_end) {
            result.push_back(current + node->compressed_str);
        }
        for (auto& pair : node->children) {
            collectWords(pair.second.get(), current + node->compressed_str, result);
        }
    }

    // 前缀搜索接口
    std::vector<std::string> searchPrefix(std::string_view prefix) {
        std::vector<std::string> result;
        TrieNode* cur = root.get();
        size_t pos = 0;
        std::string matched_str;

        // 先匹配前缀
        while (pos < prefix.size()) {
            auto it = cur->children.find(prefix[pos]);
            if (it == cur->children.end()) {
                return result; // 没有匹配的前缀
            }
            TrieNode* child = it->second.get();
            int match_len = matchPrefix(child, prefix.substr(pos));
            if (match_len < child->compressed_str.size()) {
                // 前缀没有完全匹配节点的压缩字符串，说明没有完整的前缀匹配
                if (match_len == prefix.size() - pos) {
                    // 前缀刚好匹配到节点压缩字符串的一部分，收集该节点下的所有字符串
                    matched_str += child->compressed_str.substr(0, match_len);
                    if (child->is_end) {
                        result.push_back(matched_str);
                    }
                    // 继续收集子节点
                    std::string temp = matched_str;
                    for (auto& pair : child->children) {
                        collectWords(pair.second.get(), temp, result);
                    }
                }
                return result;
            }
            // 完全匹配当前节点的压缩字符串
            matched_str += child->compressed_str;
            pos += match_len;
            cur = child;
        }

        // 前缀完全匹配，收集该节点下的所有字符串
        if (cur->is_end) {
            result.push_back(matched_str);
        }
        for (auto& pair : cur->children) {
            collectWords(pair.second.get(), matched_str, result);
        }
        return result;
    }
};

测试验证

编写简单的测试代码验证前缀树的功能和性能：

#include <iostream>
#include <chrono>

int main() {
    CompressedTrie trie;
    // 插入测试数据
    std::vector<std::string> test_strs = {"apple", "app", "application", "banana", "band", "bat", "cat"};
    for (const auto& str : test_strs) {
        trie.insert(str);
    }

    // 测试前缀搜索
    auto result = trie.searchPrefix("app");
    std::cout << "前缀app的搜索结果：" << std::endl;
    for (const auto& s : result) {
        std::cout << s << std::endl;
    }

    // 简单性能测试
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100000; ++i) {
        trie.insert("test" + std::to_string(i));
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "插入10万条数据耗时：" << duration.count() << "ms" << std::endl;

    return 0;
}

性能对比

和传统前缀树相比，优化后的实现有以下几个优势：

• 内存占用更低：字典压缩减少了单分支节点的数量，整体节点数最多为传统前缀树的几分之一，内存占用明显下降。
• 查询速度更快：减少了节点跳转次数，同时string_view避免了字符串拷贝，查询时的开销更低。
• 插入效率更高：插入时不需要拷贝完整字符串，仅处理必要的字符串片段，插入性能提升明显。

该实现适合处理大规模字符串集合的前缀匹配场景，比如搜索框的自动补全、敏感词过滤、路由匹配等场景，能够有效提升系统的整体性能。

C++string_view前缀树字典压缩修改时间：2026-07-07 05:27:42