设计一个基于哈希的自动完成系统（支持模糊匹配和频率排序）

题目描述：
设计一个支持模糊匹配和频率排序的自动完成系统。系统需要存储一组字符串，并能够根据用户输入的前缀，返回所有匹配该前缀的字符串，同时结果需要按照字符串的历史查询频率（或自定义权重）降序排序。如果多个字符串频率相同，则按字典序升序排列。系统需要支持两种操作：

1. 插入/更新字符串及其频率（如每次查询后增加频率）。
2. 给定前缀，返回频率最高的前k个匹配结果。

解题过程：

第一步：理解核心需求

• 需要快速根据前缀匹配字符串 -> 可以使用前缀树（Trie）来存储所有字符串，实现高效前缀搜索。
• 需要记录每个字符串的频率（或权重） -> 可以在前缀树节点中维护频率信息，但一个字符串可能对应多个节点（如不同位置），因此通常在字符串终点节点存储频率。
• 需要按频率排序返回结果 -> 在搜索时，需要收集所有匹配前缀的字符串，然后排序。但为了优化，可以在每个节点提前存储该节点下所有字符串的频率排序，但这会增加插入开销。更常见的做法是搜索时遍历子树，收集所有候选字符串，再排序取前k个。
• 模糊匹配：本题目中“模糊匹配”通常指前缀匹配（即输入"app"可匹配"apple"），非编辑距离模糊。因此用前缀树即可。

第二步：数据结构设计

• 使用前缀树节点结构：
  • children: 字典（哈希表），映射字符到子节点。
  • is_end: 布尔值，标记是否为某个字符串的终点。
  • frequency: 整数，如果is_end为True，存储该字符串的累计频率。
• 额外维护一个全局哈希表 word_freq: 键为完整字符串，值为当前频率。这样更新和查找频率只需O(1)。
• 在搜索时，先找到前缀对应的节点，然后遍历该节点的子树，收集所有字符串及其频率（从word_freq中取），最后排序。

第三步：插入操作

• 输入：一个字符串 word 和可选频率增量（默认为1）。
• 步骤：
  1. 遍历 word 的每个字符，在前缀树中创建或移动到对应子节点。
  2. 在最后一个节点，标记 is_end = True，但不在节点中存储频率，因为频率会变化，维护成本高。节点中只需要知道这是一个单词终点即可。
  3. 在全局哈希表 word_freq 中更新频率：word_freq[word] = word_freq.get(word, 0) + increment。

第四步：搜索操作

• 输入：前缀 prefix 和整数 k。
• 步骤：
  1. 从前缀树根节点开始，逐个字符匹配 prefix，如果中途遇到缺失字符，说明没有匹配，返回空列表。
  2. 到达前缀最后一个字符对应的节点，记为 node。
  3. 遍历 node 的整个子树，收集所有 is_end 为 True 的节点对应的字符串。如何得到字符串？遍历时维护当前路径字符串即可。
  4. 对于收集到的每个字符串，从全局哈希表 word_freq 中取出其频率。
  5. 将所有（字符串，频率）对按照频率降序、频率相同时字典序升序排序。
  6. 返回前k个字符串（只返回字符串，不包含频率）。

第五步：优化考虑

• 如果每次搜索都遍历整个子树，在子树很大时会很慢。可优化：
  • 在每个节点存储该节点下所有可能的字符串终点，并按频率排序。但插入时需要更新所有祖先节点的列表，插入成本高。
  • 折中方案：在每个节点缓存其子树中最热门的k个字符串（例如k=3），但搜索时如果需求k大于缓存值，仍需要遍历。
• 本题假设数据量中等，采用简单遍历即可，重点在于哈希表和前缀树的结合。

第六步：实现细节示例

• 定义前缀树节点：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

• 定义自动完成系统：

class AutocompleteSystem:
    def __init__(self):
        self.root = TrieNode()
        self.word_freq = {}  # 哈希表存储频率
    
    def insert(self, word, increment=1):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
        self.word_freq[word] = self.word_freq.get(word, 0) + increment
    
    def search(self, prefix, k):
        # 1. 找到前缀节点
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        # 2. 收集所有候选单词
        candidates = []
        self._dfs(node, prefix, candidates)
        # 3. 根据频率和字典序排序
        candidates.sort(key=lambda x: (-self.word_freq[x], x))
        # 4. 返回前k个
        return candidates[:k]
    
    def _dfs(self, node, cur_word, candidates):
        if node.is_end:
            candidates.append(cur_word)
        for ch, child in node.children.items():
            self._dfs(child, cur_word + ch, candidates)

第七步：复杂度分析

• 插入：O(m)，m为字符串长度，哈希表更新O(1)。
• 搜索：O(L + N log N)，其中L是遍历子树的节点数，N是匹配的字符串数量，排序需要O(N log N)。实际中如果子树很大，可考虑用堆只维护前k个，优化到O(L + N log k)。

第八步：扩展模糊匹配

• 如果要支持更复杂的模糊匹配（如错字、编辑距离），可以在遍历时允许容错，但会大幅增加搜索空间。通常这类需求需要更高级的数据结构如有限状态自动机。

这个系统结合了哈希表（快速频率存取）和前缀树（高效前缀搜索），是自动完成的经典实现。