綜合應用案例：搜尋引擎核心演算法（探索版）¶
本案例以「搜尋引擎開發」為場景，用**核心工程師解決問題的視角**探索演算法設計技巧。你將扮演 SearchX 的工程師，從實際問題出發，逐步發現「為什麼需要這個演算法」。
設計理念：不是「先學演算法，再找應用」，而是「遇到問題 → 需要什麼工具 → 引入演算法」。
與資料結構專題的關係：本專題專注於**演算法設計技巧**（字串、分治、貪心、NP），與資料結構專題互補。
場景背景¶
你是 SearchX（虛構搜尋引擎公司）的**核心工程師**，負責從爬蟲到排名的全流程。
什麼是搜尋引擎？
**搜尋引擎**的核心任務是：給定用戶的查詢，從數十億網頁中找出最相關的結果。
| 階段 | 任務 | 挑戰 |
|---|---|---|
| 爬蟲 | 抓取網頁 | 規模大、去重複 |
| 索引 | 建立倒排索引 | 儲存壓縮、動態更新 |
| 搜尋 | 字串匹配 | 速度要快 |
| 排名 | 相關性排序 | 品質要好 |
| 廣告 | 投放最佳化 | 收益最大化 |
本案例中的問題正是搜尋引擎工程師日常會遇到的：怎麼快速匹配字串？怎麼壓縮索引？為什麼有些問題「很難」？
SearchX 系統架構¶
用戶查詢 "機器學習"
│
▼
┌───────────────────────────────────────────────────────┐
│ SearchX 系統 │
├───────────────────────────────────────────────────────┤
│ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ 爬蟲 │───▶│ 索引 │───▶│ 搜尋 │ │
│ │ Crawler │ │ Indexer │ │ Search │ │
│ └─────────┘ └─────────┘ └────┬────┘ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │重複偵測 │ │ 壓縮 │ │字串匹配 │ │
│ │Q2 Rabin │ │Q4 Huffman│ │Q1 KMP │ │
│ └─────────┘ └─────────┘ └─────────┘ │
│ │
│ ┌─────────────────────────────────────────┐ │
│ │ 系統基礎建設 │ │
│ │ Q3 分治法 │ Q5 平攤分析 │ Q6-8 NP 問題 │ │
│ └─────────────────────────────────────────┘ │
│ │
└───────────────────────────────────────────────────────┘
│
▼
搜尋結果
你的日常挑戰¶
| 情境 | 你的問題 | 對應技術 |
|---|---|---|
| 用戶搜尋關鍵字 | 「怎麼在網頁中快速找到這個詞？」 | KMP 演算法 |
| 偵測抄襲內容 | 「怎麼判斷兩篇文章相似？」 | Rabin-Karp |
| 合併爬蟲結果 | 「多個排序列表怎麼高效合併？」 | 分治法 |
| 壓縮索引檔案 | 「怎麼用最少空間儲存？」 | Huffman 編碼 |
| 索引動態更新 | 「頻繁插入的效能保證？」 | 平攤分析 |
| 查詢太慢 | 「為什麼這個問題這麼難？」 | NP 完備性 |
| 廣告投放 | 「怎麼證明沒有快速解法？」 | NP-Complete 證明 |
| 伺服器選址 | 「找不到最佳解，近似解呢？」 | 近似演算法 |