模仿百度搜索下拉提示：Trie 樹/前綴樹 + 熱度排序實現關鍵詞聯想

核心數據結構：Trie (前綴樹)

每節點存：children[char]、isEnd、hotScore (搜索頻次/點擊率)。

構建索引 (離線/定時)

class TrieNode {
    Map children = new HashMap<>();
    boolean isEnd = false;
    long hotScore = 0;
    String word; // 終端節點存完整詞
}

void insert(String word, long score) {
    TrieNode p = root;
    for (char c : word.toCharArray()) {
        p = p.children.computeIfAbsent(c, k -> new TrieNode());
    }
    p.isEnd = true;
    p.word = word;
    p.hotScore = Math.max(p.hotScore, score);
}

前綴查詢 (在線，毫秒級)

List suggest(String prefix, int limit) {
    TrieNode p = root;
    for (char c : prefix.toCharArray()) {
        p = p.children.get(c);
        if (p == null) return Collections.emptyList();
    }
    // DFS 收集所有終端詞
    List candidates = new ArrayList<>();
    collect(p, candidates);
    // 按熱度降序
    candidates.sort((a,b) -> Long.compare(b.hotScore, a.hotScore));
    return candidates.stream().limit(limit).map(n -> n.word).collect(Collectors.toList());
}
void collect(TrieNode p, List out) {
    if (p.isEnd) out.add(p);
    p.children.values().forEach(c -> collect(c, out));
}

工程優化

• Double-Array Trie (DAT)：靜態數組存儲，極致內存效率，適合嵌入式/移動端。
• 分布式：Elasticsearch completion suggester 內置 FST (有限狀態轉換器) 實現。
• 個性化：合併用戶歷史搜索權重、地理位置、語言模型。
• 更新策略：增量構建 + 定時全量重建，熱度分數衰減 (半衰期 7~30 天)。

參考開源實現

Open-Open 關鍵詞聯想實現 (Java Trie + 熱度)。