支持通配符和词频统计的字典树设计

题目

支持通配符和词频统计的字典树设计

信息

• 类型：问答
• 难度：⭐⭐⭐

考点

字典树设计,通配符搜索,DFS优化,词频统计,空间优化

快速回答

设计一个支持通配符搜索和词频统计的字典树需要：

• 在TrieNode中添加词频统计字段
• 使用DFS处理通配符'.'的所有可能分支
• 实现层级压缩优化减少内存占用
• 添加缓存机制优化重复查询性能
• 正确处理边界条件和空模式

问题描述

设计一个增强型字典树，支持：1) 插入单词并统计词频；2) 支持包含通配符'.'的搜索（每个'.'匹配任意字符）；3) 实现层级压缩优化；4) 添加查询缓存。要求处理百万级词汇量时保持高效。

原理说明

字典树核心原理：

• 节点结构：每个节点包含子节点指针数组和词频计数器
• 通配符处理：遇到'.'时DFS遍历所有子节点分支
• 层级压缩：合并单分支路径减少节点数量
• 缓存机制：存储常见搜索模式的结果

代码实现

from collections import defaultdict
import functools

class TrieNode:
    __slots__ = ['children', 'freq', 'compressed']
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.freq = 0  # 单词出现频率
        self.compressed = None  # 压缩后的字符串

class EnhancedTrie:
    def __init__(self):
        self.root = TrieNode()
        self.cache = {}  # 模式搜索缓存

    def insert(self, word):
        node = self.root
        for char in word:
            node = node.children[char]
        node.freq += 1

    def _compress_paths(self, node, current_path):
        # 递归压缩单分支路径
        while len(node.children) == 1 and node.freq == 0:
            char, next_node = next(iter(node.children.items()))
            current_path += char
            node = next_node

        node.compressed = current_path
        for char, child in node.children.items():
            self._compress_paths(child, '')

    def compress(self):
        self._compress_paths(self.root, '')

    @functools.lru_cache(maxsize=1000)
    def search_with_wildcards(self, pattern):
        results = []
        self._dfs_search(self.root, pattern, 0, '', results)
        return results

    def _dfs_search(self, node, pattern, idx, current_word, results):
        # 处理压缩节点
        if node.compressed:
            if pattern.startswith(node.compressed, idx):
                return self._dfs_search(node, pattern, idx + len(node.compressed), 
                                       current_word + node.compressed, results)
            return

        # 终止条件
        if idx == len(pattern):
            if node.freq > 0:
                results.append((current_word, node.freq))
            return

        char = pattern[idx]
        # 通配符处理
        if char == '.':
            for child_char, child_node in node.children.items():
                self._dfs_search(child_node, pattern, idx+1, 
                                current_word + child_char, results)
        # 常规字符处理
        elif char in node.children:
            self._dfs_search(node.children[char], pattern, idx+1, 
                            current_word + char, results)

最佳实践

• 内存优化：使用__slots__减少对象内存开销
• 缓存机制：LRU缓存避免重复计算通配符搜索
• 延迟压缩：在插入完成后批量执行压缩
• 通配符限制：实际场景可限制连续通配符数量

常见错误

• 未处理压缩节点：DFS中必须特殊处理压缩的字符串序列
• 缓存污染：插入新词后未清除缓存导致脏数据
• 频率遗漏：中间节点可能也是单词结尾（需检查freq>0）
• 超长模式：未限制通配符数量导致指数级搜索

扩展知识

• 双数组字典树：DAT结构进一步压缩空间
• 编辑距离搜索：结合动态规划实现模糊搜索
• 分布式字典树：使用分片机制处理超大规模数据
• AC自动机：扩展支持多模式匹配

复杂度分析

L=单词长度, K=通配符数, M=结果数, N=节点数, C=缓存大小