Trie树（字典树）的高效模糊搜索与自动补全实现

1. 问题背景

Trie树（字典树）是一种专门用于处理字符串匹配的树形数据结构，其核心思想是利用字符串的公共前缀来减少查询时间。在模糊搜索（如支持通配符*或?）和自动补全场景中，Trie树可以通过优化遍历方式快速找到所有匹配的字符串。例如，当用户在搜索框输入"app*"时，系统需要返回所有以"app"开头的单词（如"apple"、"application"）。

2. Trie树的基本结构

Trie树的每个节点包含以下部分：

• 子节点指针数组（或哈希表）：用于存储当前字符到下一个节点的映射。
• 结束标志：标记当前节点是否为一个单词的结尾。
• 可选优化：节点可存储词频或缓存热门结果以提升自动补全效率。

示例：插入单词"apple"、"app"后的Trie树结构

根节点
  └─ a ─ p ─ p ─ (结束标志为True, 因"app"是一个单词)
          └─ l ─ e ─ (结束标志为True)

3. 模糊搜索的实现步骤

场景：支持通配符*（匹配任意多个字符）和?（匹配单个字符）。
以模式"app*e"为例，需要匹配所有以"app"开头、以"e"结尾的单词。

步骤1：定义递归搜索函数

函数参数包括当前节点、模式字符串、当前匹配位置和临时结果。

def fuzzy_search(node, pattern, index, path, results):
    if index == len(pattern):
        if node.is_end:  # 匹配完成且当前节点是单词结尾
            results.append("".join(path))
        return
    
    char = pattern[index]
    if char == '*':
        # 情况1: '*'匹配0个字符，直接跳过
        fuzzy_search(node, pattern, index+1, path, results)
        # 情况2: '*'匹配1个或多个字符，继续当前节点向下递归
        for child_char, child_node in node.children.items():
            fuzzy_search(child_node, pattern, index, path + [child_char], results)
    elif char == '?':
        # 匹配任意单个字符
        for child_char, child_node in node.children.items():
            fuzzy_search(child_node, pattern, index+1, path + [child_char], results)
    else:
        # 普通字符匹配
        if char in node.children:
            fuzzy_search(node.children[char], pattern, index+1, path + [char], results)

步骤2：处理通配符优化

• 问题：*可能导致指数级递归（如模式"**a"）。
• 优化：记忆化搜索（Memoization）。
  定义缓存键(节点, 模式索引)，避免重复计算相同状态。

4. 自动补全的高效实现

目标：输入前缀"app"，返回按词频排序的Top-K补全结果（如["apple", "application", "apply"]）。

步骤1：预存储词频

在插入单词时，在每个节点记录以当前路径为前缀的单词词频：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.freq = 0  # 以当前节点结尾的单词词频

def insert(root, word, freq=1):
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end = True
    node.freq += freq

步骤2：收集所有候选词

通过DFS遍历前缀下的所有分支，收集单词及其词频：

def collect_words(node, path, results):
    if node.is_end:
        results.append(("".join(path), node.freq))
    for char, child_node in node.children.items():
        collect_words(child_node, path + [char], results)

步骤3：返回Top-K结果

对收集到的单词按词频排序，取前K个：

def autocomplete(root, prefix, k=10):
    node = root
    # 定位到前缀的最后一个节点
    for char in prefix:
        if char not in node.children:
            return []
        node = node.children[char]
    
    results = []
    collect_words(node, list(prefix), results)
    results.sort(key=lambda x: x[1], reverse=True)  # 按词频降序排序
    return [word for word, _ in results[:k]]

5. 复杂度分析

• 时间复杂度：
  • 模糊搜索：最坏情况O(m * Σ^L)（m为模式长度，L为Trie深度，Σ为字符集大小），优化后可通过剪枝降低。
  • 自动补全：O(P + C log C)，P为前缀长度，C为候选词数量。
• 空间复杂度：O(N * Σ)，N为总节点数，Σ为字符集大小（可通过哈希表压缩）。

6. 实际应用优化

1. 压缩Trie（Radix Tree）：合并单分支节点，减少内存占用。
2. 前缀缓存：为热门查询缓存自动补全结果。
3. 分布式Trie：将Trie按前缀划分到不同机器上（如Elasticsearch的倒排索引优化）。

通过以上步骤，Trie树能够高效支持模糊搜索和自动补全，结合优化策略后可应对大规模数据场景。