設計搜尋自動補全 — Trie、Top-K 排序與分散式即時建議系統 | 資料結構與演算法

// ============================================================
// Autocomplete Service — TypeScript 完整實作
// 包含：Trie + Top-K 快取 + 熱度排序 + 最近搜尋 + 模糊搜尋
// ============================================================

// ─── 型別定義 ───────────────────────────────────────────────

interface SearchSuggestion {
  query: string;
  score: number;        // 熱度分數（搜尋頻率）
  source: "trie" | "recent" | "personalized";
}

interface TrieNode {
  children: Map<string, TrieNode>;
  isEnd: boolean;
  topK: SearchSuggestion[];  // 快取此節點前綴的 Top-K 結果
}

// ─── MinHeap（用於 Top-K 選取）───────────────────────────────

class MinHeap<T> {
  private heap: T[] = [];
  constructor(private comparator: (a: T, b: T) => number) {}

  push(item: T): void {
    this.heap.push(item);
    this.bubbleUp(this.heap.length - 1);
  }

  pop(): T | undefined {
    if (this.heap.length === 0) return undefined;
    const top = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return top;
  }

  peek(): T | undefined { return this.heap[0]; }
  get size(): number { return this.heap.length; }

  private bubbleUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.comparator(this.heap[i], this.heap[parent]) < 0) {
        [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
        i = parent;
      } else break;
    }
  }

  private sinkDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < n && this.comparator(this.heap[left], this.heap[smallest]) < 0)
        smallest = left;
      if (right < n && this.comparator(this.heap[right], this.heap[smallest]) < 0)
        smallest = right;
      if (smallest !== i) {
        [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
        i = smallest;
      } else break;
    }
  }
}

// ─── AutocompleteTrie 核心 ──────────────────────────────────

class AutocompleteTrie {
  private root: TrieNode;
  private readonly K: number;

  constructor(k: number = 10) {
    this.K = k;
    this.root = this.createNode();
  }

  private createNode(): TrieNode {
    return { children: new Map(), isEnd: false, topK: [] };
  }

  /**
   * 插入查詢字串並更新沿路所有節點的 Top-K 快取
   * 時間複雜度：O(L × K log K)，L = 字串長度
   */
  insert(query: string, score: number): void {
    const suggestion: SearchSuggestion = {
      query,
      score,
      source: "trie",
    };

    let node = this.root;
    this.updateTopK(node, suggestion); // 更新根節點

    for (const char of query.toLowerCase()) {
      if (!node.children.has(char)) {
        node.children.set(char, this.createNode());
      }
      node = node.children.get(char)!;
      this.updateTopK(node, suggestion); // 更新沿路每個節點
    }
    node.isEnd = true;
  }

  /**
   * 維護節點的 Top-K 列表
   * 若新項目 score 超過當前最小值則替換
   */
  private updateTopK(node: TrieNode, suggestion: SearchSuggestion): void {
    // 去重：若同查詢已存在則更新分數
    const existingIdx = node.topK.findIndex(s => s.query === suggestion.query);
    if (existingIdx >= 0) {
      node.topK[existingIdx].score = Math.max(
        node.topK[existingIdx].score,
        suggestion.score
      );
      node.topK.sort((a, b) => b.score - a.score);
      return;
    }

    // 未滿 K 個則直接加入
    if (node.topK.length < this.K) {
      node.topK.push({ ...suggestion });
      node.topK.sort((a, b) => b.score - a.score);
    }
    // 分數高於當前最低者則替換
    else if (suggestion.score > node.topK[node.topK.length - 1].score) {
      node.topK[node.topK.length - 1] = { ...suggestion };
      node.topK.sort((a, b) => b.score - a.score);
    }
  }

  /**
   * 查詢前綴對應的 Top-K 建議
   * 時間複雜度：O(P)——P = 前綴長度（因為節點已快取 Top-K）
   */
  search(prefix: string): SearchSuggestion[] {
    let node = this.root;
    for (const char of prefix.toLowerCase()) {
      if (!node.children.has(char)) return [];
      node = node.children.get(char)!;
    }
    return [...node.topK];
  }

  /**
   * 序列化 Trie 以便持久化存儲至 S3/GCS
   */
  serialize(): string {
    const serializeNode = (node: TrieNode): object => ({
      isEnd: node.isEnd,
      topK: node.topK,
      children: Object.fromEntries(
        [...node.children.entries()].map(([k, v]) => [k, serializeNode(v)])
      ),
    });
    return JSON.stringify(serializeNode(this.root));
  }
}

// ─── AutocompleteService（對外 API 層）────────────────────────

interface AutocompleteConfig {
  maxSuggestions: number;     // 最終回傳數量（通常 5~10）
  maxRecentSearches: number;  // 保存最近搜尋數量
  recentSearchBoost: number;  // 最近搜尋的分數加成
  debounceMs: number;         // 前端 Debounce 毫秒數
}

class AutocompleteService {
  private trie: AutocompleteTrie;
  private recentSearches: Map<string, string[]>;  // userId → 最近搜尋
  private searchFrequency: Map<string, number>;    // 全域搜尋頻率計數
  private config: AutocompleteConfig;

  // 簡易記憶體快取（生產環境應替換為 Redis）
  private cache: Map<string, { results: SearchSuggestion[]; timestamp: number }>;
  private readonly CACHE_TTL = 300_000; // 5 分鐘

  constructor(config: Partial<AutocompleteConfig> = {}) {
    this.config = {
      maxSuggestions: 10,
      maxRecentSearches: 20,
      recentSearchBoost: 500,
      debounceMs: 150,
      ...config,
    };
    this.trie = new AutocompleteTrie(this.config.maxSuggestions * 2);
    this.recentSearches = new Map();
    this.searchFrequency = new Map();
    this.cache = new Map();
  }

  /**
   * 建立索引——批量插入查詢字串與頻率
   * 通常離線執行，每小時更新一次
   */
  buildIndex(queries: Array<{ query: string; frequency: number }>): void {
    console.log(`[Autocomplete] 建立索引，共 ${queries.length} 筆...`);
    const start = Date.now();

    for (const { query, frequency } of queries) {
      this.trie.insert(query, frequency);
      this.searchFrequency.set(query, frequency);
    }

    console.log(`[Autocomplete] 索引完成，耗時 ${Date.now() - start}ms`);
  }

  /**
   * 查詢補全建議（主要 API）
   * 合併 Trie 結果、最近搜尋、個人化排序
   */
  getSuggestions(prefix: string, userId?: string): SearchSuggestion[] {
    // 空白輸入回傳最近搜尋
    if (!prefix || prefix.length === 0) {
      return userId ? this.getRecentSearches(userId) : [];
    }

    const cacheKey = `${userId ?? "anon"}:${prefix.toLowerCase()}`;

    // 1. 檢查快取
    const cached = this.cache.get(cacheKey);
    if (cached && Date.now() - cached.timestamp < this.CACHE_TTL) {
      return cached.results;
    }

    // 2. Trie 查詢——O(P)
    const trieSuggestions = this.trie.search(prefix);

    // 3. 混合最近搜尋（個人化）
    let results = this.mergeWithRecentSearches(trieSuggestions, prefix, userId);

    // 4. 截取 Top-K
    results = results.slice(0, this.config.maxSuggestions);

    // 5. 寫入快取
    this.cache.set(cacheKey, { results, timestamp: Date.now() });

    return results;
  }

  /**
   * 記錄使用者搜尋（更新頻率與最近搜尋）
   */
  recordSearch(query: string, userId?: string): void {
    // 更新全域頻率（生產環境應發送至 Kafka 非同步處理）
    const currentFreq = this.searchFrequency.get(query) ?? 0;
    this.searchFrequency.set(query, currentFreq + 1);

    // 更新使用者最近搜尋
    if (userId) {
      const recent = this.recentSearches.get(userId) ?? [];
      const filtered = recent.filter(q => q !== query);
      this.recentSearches.set(
        userId,
        [query, ...filtered].slice(0, this.config.maxRecentSearches)
      );
    }
  }

  private getRecentSearches(userId: string): SearchSuggestion[] {
    const recent = this.recentSearches.get(userId) ?? [];
    return recent.map(query => ({
      query,
      score: this.config.recentSearchBoost,
      source: "recent" as const,
    }));
  }

  private mergeWithRecentSearches(
    trieSuggestions: SearchSuggestion[],
    prefix: string,
    userId?: string
  ): SearchSuggestion[] {
    if (!userId) return trieSuggestions;

    // 篩選出匹配前綴的最近搜尋
    const recentMatches = this.getRecentSearches(userId)
      .filter(s => s.query.toLowerCase().startsWith(prefix.toLowerCase()));

    // 合併並去重——最近搜尋因 boost 加成會排在前面
    const seen = new Set<string>();
    const merged: SearchSuggestion[] = [];

    for (const suggestion of [...recentMatches, ...trieSuggestions]) {
      if (!seen.has(suggestion.query)) {
        seen.add(suggestion.query);
        merged.push(suggestion);
      }
    }

    return merged.sort((a, b) => b.score - a.score);
  }
}

// ─── BK-Tree — 模糊搜尋 ────────────────────────────────────

class BKTree {
  private root: { word: string; children: Map<number, any> } | null = null;

  /**
   * 計算 Levenshtein Edit Distance（動態規劃）
   * 時間複雜度：O(m × n)
   */
  static editDistance(a: string, b: string): number {
    const m = a.length;
    const n = b.length;
    const dp: number[][] = Array.from({ length: m + 1 }, (_, i) =>
      Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
    );

    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        if (a[i - 1] === b[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = 1 + Math.min(
            dp[i - 1][j],     // 刪除
            dp[i][j - 1],     // 插入
            dp[i - 1][j - 1]  // 替換
          );
        }
      }
    }
    return dp[m][n];
  }

  insert(word: string): void {
    if (!this.root) {
      this.root = { word, children: new Map() };
      return;
    }

    let current = this.root;
    while (true) {
      const dist = BKTree.editDistance(word, current.word);
      if (dist === 0) return; // 已存在

      if (!current.children.has(dist)) {
        current.children.set(dist, { word, children: new Map() });
        return;
      }
      current = current.children.get(dist);
    }
  }

  /**
   * 查詢所有與 target Edit Distance ≤ maxDist 的字串
   * BK-Tree 剪枝率通常達 75~90%，遠優於線性掃描
   */
  search(target: string, maxDist: number): string[] {
    if (!this.root) return [];

    const results: string[] = [];
    const stack = [this.root];

    while (stack.length > 0) {
      const node = stack.pop()!;
      const dist = BKTree.editDistance(target, node.word);

      if (dist <= maxDist) results.push(node.word);

      // 剪枝：只探索距離在 [dist-maxDist, dist+maxDist] 範圍的子節點
      for (const [childDist, childNode] of node.children) {
        if (Math.abs(childDist - dist) <= maxDist) {
          stack.push(childNode);
        }
      }
    }

    return results.sort();
  }
}

// ─── 使用示範 ──────────────────────────────────────────────

function demo(): void {
  console.log("=== 搜尋自動補全系統 Demo ===\n");

  const service = new AutocompleteService({
    maxSuggestions: 5,
    recentSearchBoost: 800,
  });

  // 1. 建立索引
  service.buildIndex([
    { query: "apple", frequency: 1000 },
    { query: "apple watch", frequency: 850 },
    { query: "apple store", frequency: 720 },
    { query: "apple iphone", frequency: 680 },
    { query: "application", frequency: 600 },
    { query: "apply for job", frequency: 450 },
    { query: "apt-get install", frequency: 300 },
    { query: "apartment", frequency: 280 },
    { query: "amazon", frequency: 950 },
    { query: "amazon prime", frequency: 800 },
    { query: "appetizer", frequency: 200 },
  ]);

  // 2. 記錄使用者最近搜尋
  service.recordSearch("apple store", "user_001");
  service.recordSearch("apple watch", "user_001");

  // 3. 匿名用戶查詢
  console.log('\n--- 前綴 "app" 的建議（匿名用戶）---');
  const anonResults = service.getSuggestions("app");
  anonResults.forEach((s, i) =>
    console.log(`  ${i + 1}. ${s.query} (score: ${s.score}, source: ${s.source})`)
  );
  // 輸出：
  //   1. apple (score: 1000, source: trie)
  //   2. apple watch (score: 850, source: trie)
  //   3. apple store (score: 720, source: trie)
  //   4. apple iphone (score: 680, source: trie)
  //   5. application (score: 600, source: trie)

  // 4. 個人化查詢——最近搜尋有 boost 加成
  console.log('\n--- 前綴 "app" 的建議（user_001，有個人化）---');
  const personalResults = service.getSuggestions("app", "user_001");
  personalResults.forEach((s, i) =>
    console.log(`  ${i + 1}. ${s.query} (score: ${s.score}, source: ${s.source})`)
  );
  // 輸出：
  //   1. apple (score: 1000, source: trie)
  //   2. apple watch (score: 800, source: recent) ← boost 加成
  //   3. apple store (score: 800, source: recent) ← boost 加成
  //   4. apple iphone (score: 680, source: trie)
  //   5. application (score: 600, source: trie)

  // 5. 模糊搜尋 Demo
  console.log("\n--- 模糊搜尋 BK-Tree Demo ---");
  const bkTree = new BKTree();
  ["apple", "application", "apply", "appetizer", "apartment"].forEach(w =>
    bkTree.insert(w)
  );

  const typo = "aple";
  const fuzzyResults = bkTree.search(typo, 1);
  console.log(`  輸入 "${typo}"（容忍距離=1）：${fuzzyResults.join(", ")}`);
  // 輸出：輸入 "aple"（容忍距離=1）：apple

  const typo2 = "appel";
  const fuzzyResults2 = bkTree.search(typo2, 2);
  console.log(`  輸入 "${typo2}"（容忍距離=2）：${fuzzyResults2.join(", ")}`);
  // 輸出：輸入 "appel"（容忍距離=2）：apple, apply
}

demo();

// ============================================================
// 搜尋自動補全 — C++ 高效實作
// 策略一：陣列版 Trie（固定字母表，cache-friendly）
// ============================================================

#include <array>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <chrono>

constexpr int ALPHABET_SIZE = 26;

struct ArrayTrieNode {
    std::array<int, ALPHABET_SIZE> children; // 索引代替指標
    bool isEnd = false;
    int score = 0;
    std::vector<std::pair<int, std::string>> topK; // {score, query}

    ArrayTrieNode() { children.fill(-1); }
};

class ArrayTrie {
public:
    explicit ArrayTrie(int k = 10) : K_(k) {
        nodes_.reserve(1'000'000); // 預分配節點池
        nodes_.emplace_back();     // root = 節點 0
    }

    void insert(const std::string& query, int score) {
        int cur = 0;
        updateTopK(0, query, score);

        for (char ch : query) {
            if (ch < 'a' || ch > 'z') continue;
            int idx = ch - 'a';
            if (nodes_[cur].children[idx] == -1) {
                nodes_[cur].children[idx] = static_cast<int>(nodes_.size());
                nodes_.emplace_back();
            }
            cur = nodes_[cur].children[idx];
            updateTopK(cur, query, score);
        }
        nodes_[cur].isEnd = true;
        nodes_[cur].score = score;
    }

    std::vector<std::pair<int, std::string>> search(
        const std::string& prefix
    ) const {
        int cur = 0;
        for (char ch : prefix) {
            if (ch < 'a' || ch > 'z') return {};
            int idx = ch - 'a';
            if (nodes_[cur].children[idx] == -1) return {};
            cur = nodes_[cur].children[idx];
        }
        return nodes_[cur].topK;
    }

    size_t nodeCount() const { return nodes_.size(); }

private:
    void updateTopK(
        int nodeIdx, const std::string& query, int score
    ) {
        auto& topK = nodes_[nodeIdx].topK;

        // 去重
        for (auto& [s, q] : topK) {
            if (q == query) {
                s = std::max(s, score);
                std::sort(topK.begin(), topK.end(),
                    [](const auto& a, const auto& b) {
                        return a.first > b.first;
                    });
                return;
            }
        }

        if (static_cast<int>(topK.size()) < K_) {
            topK.emplace_back(score, query);
        } else if (score > topK.back().first) {
            topK.back() = {score, query};
        } else {
            return;
        }

        std::sort(topK.begin(), topK.end(),
            [](const auto& a, const auto& b) {
                return a.first > b.first;
            });
    }

    std::vector<ArrayTrieNode> nodes_;
    int K_;
};

// 策略二：HashMap 版 Trie（支援任意字元集）

#include <unordered_map>
#include <memory>

struct HashTrieNode {
    std::unordered_map<char, std::unique_ptr<HashTrieNode>> children;
    bool isEnd = false;
    int score = 0;
    std::vector<std::pair<int, std::string>> topK;
};

class HashTrie {
public:
    explicit HashTrie(int k = 10)
        : K_(k), root_(std::make_unique<HashTrieNode>()) {}

    void insert(const std::string& query, int score) {
        HashTrieNode* cur = root_.get();
        updateTopK(cur, query, score);

        for (char ch : query) {
            if (!cur->children.count(ch)) {
                cur->children[ch] = std::make_unique<HashTrieNode>();
            }
            cur = cur->children[ch].get();
            updateTopK(cur, query, score);
        }
        cur->isEnd = true;
        cur->score = score;
    }

    std::vector<std::pair<int, std::string>> search(
        const std::string& prefix
    ) const {
        const HashTrieNode* cur = root_.get();
        for (char ch : prefix) {
            auto it = cur->children.find(ch);
            if (it == cur->children.end()) return {};
            cur = it->second.get();
        }
        return cur->topK;
    }

private:
    void updateTopK(
        HashTrieNode* node, const std::string& query, int score
    ) {
        auto& topK = node->topK;
        for (auto& [s, q] : topK) {
            if (q == query) {
                s = std::max(s, score);
                std::sort(topK.begin(), topK.end(),
                    [](const auto& a, const auto& b) {
                        return a.first > b.first;
                    });
                return;
            }
        }
        if (static_cast<int>(topK.size()) < K_) {
            topK.emplace_back(score, query);
        } else if (score > topK.back().first) {
            topK.back() = {score, query};
        } else {
            return;
        }
        std::sort(topK.begin(), topK.end(),
            [](const auto& a, const auto& b) {
                return a.first > b.first;
            });
    }

    std::unique_ptr<HashTrieNode> root_;
    int K_;
};

// ─── Edit Distance（空間優化版本）──────────────────────────

int editDistance(const std::string& a, const std::string& b) {
    int m = static_cast<int>(a.size());
    int n = static_cast<int>(b.size());
    std::vector<int> prev(n + 1), curr(n + 1);

    for (int j = 0; j <= n; ++j) prev[j] = j;

    for (int i = 1; i <= m; ++i) {
        curr[0] = i;
        for (int j = 1; j <= n; ++j) {
            if (a[i-1] == b[j-1]) {
                curr[j] = prev[j-1];
            } else {
                curr[j] = 1 + std::min({prev[j], curr[j-1], prev[j-1]});
            }
        }
        std::swap(prev, curr);
    }
    return prev[n];
}

// ─── 主程式與效能測試 ─────────────────────────────────────

int main() {
    std::cout << "=== 搜尋自動補全 C++ 效能測試 ===\n\n";

    // 功能測試
    ArrayTrie trie;
    std::vector<std::pair<std::string, int>> data = {
        {"apple", 1000}, {"apple watch", 850},
        {"application", 600}, {"apply", 450},
        {"apt", 300}, {"amazon", 950}
    };
    for (const auto& [q, s] : data) trie.insert(q, s);

    std::cout << "前綴 \"app\" 的 Top-5 建議：\n";
    auto results = trie.search("app");
    for (int i = 0; i < static_cast<int>(results.size()); ++i) {
        std::cout << "  " << (i+1) << ". " << results[i].second
                  << " (score: " << results[i].first << ")\n";
    }
    // 輸出：
    //   1. apple (score: 1000)
    //   2. apple watch (score: 850)
    //   3. application (score: 600)
    //   4. apply (score: 450)
    //   5. apt (score: 300)

    std::cout << "\nEdit Distance(\"aple\", \"apple\") = "
              << editDistance("aple", "apple") << "\n";
    // 輸出：Edit Distance("aple", "apple") = 1

    // 效能基準測試——10 萬筆資料
    using Clock = std::chrono::high_resolution_clock;
    std::vector<std::pair<std::string, int>> testData;
    const std::string chars = "abcdefghijklmnopqrstuvwxyz";
    for (int i = 0; i < 100'000; ++i) {
        std::string query;
        int len = 5 + rand() % 10;
        for (int j = 0; j < len; ++j) query += chars[rand() % 26];
        testData.emplace_back(query, rand() % 10000);
    }

    ArrayTrie benchTrie;
    auto t0 = Clock::now();
    for (const auto& [q, s] : testData) benchTrie.insert(q, s);
    auto t1 = Clock::now();

    int queries = 10000;
    for (int i = 0; i < queries; ++i) {
        auto prefix = testData[i % testData.size()].first.substr(0, 3);
        auto r = benchTrie.search(prefix);
    }
    auto t2 = Clock::now();

    auto insertMs = std::chrono::duration_cast<
        std::chrono::milliseconds>(t1 - t0).count();
    auto searchMs = std::chrono::duration_cast<
        std::chrono::milliseconds>(t2 - t1).count();

    std::cout << "\n--- 效能基準測試（ArrayTrie）---\n";
    std::cout << "插入 100,000 筆: " << insertMs << "ms\n";
    std::cout << "查詢 10,000 次: " << searchMs << "ms\n";
    std::cout << "節點數: " << benchTrie.nodeCount() << "\n";

    return 0;
}