跳轉到

10.3 總結與進階閱讀#

全書主題回顧#

本書沿著一條主線走過文字演算法的世界：表示 → 比對 → 索引 → 相似度 → 壓縮 → 語言 → 系統。

  • 表示與規格化（第1章）：字串的編碼本質，中英混合的正確處理，正規表示式。一切文字工作的地基。
  • 單一比對（第2章）：樸素比對 → Rabin-Karp（雜湊）→ KMP（失敗函數）→ Boyer-Moore（跳躍比對）。核心教訓：預處理換查詢。
  • 多樣式與索引（第3章）：Trie、Aho-Corasick、後綴陣列/後綴樹。核心教訓：樣式多就建樣式索引，文字大就建文字索引。
  • 相似度（第4章）：編輯距離、LCS、最長共同子字串、模糊比對。核心教訓：先定義「距離」，再依查詢量決定是否建索引。
  • 壓縮（第5、6章）：熵極限 → Huffman → 算術編碼；LZ77/LZ78 → LZW/GIF → DEFLATE。核心教訓：統計冗餘與重複冗餘由不同機制吃掉，兩層合體最強。
  • 語言處理（第7章）：分詞、詞幹化、詞向量。核心教訓：表示決定上限。
  • 搜尋（第8章）：倒排索引、TF-IDF/BM25、PageRank。核心教訓：相關性與重要性正交互補，重活離線做。
  • 語言建模（第9章）：貝氏分類、N-gram 到神經語言模型、Transformer/LLM。核心教訓：預測文字的機率分布是語言智能的統一框架。
  • 實戰（第10章）：敏感詞過濾、抄襲偵測——真實系統是演算法、工程與對抗的三角平衡。

一個貫穿全書的元原則值得銘記：文字演算法的歷史就是不斷「把線上貴的活搬到線下」的歷史——KMP 的失敗函數、AC 的失敗連結、後綴陣列的排序、倒排索引、PageRank 的冪迭代，都是「預先花力氣建結構，換來查詢時的飛快」。

進階閱讀路線#

經典書籍：

  • Dan Gusfield, Algorithms on Strings, Trees and Sequences（1997）——後綴樹與字串演算法的聖經。
  • Max Crochemore & Wojciech Rytter, Jewels of Stringology——字串演算法精選。
  • David Salomon, Data Compression: The Complete Reference——壓縮技術大全。
  • Christopher Manning 等人， Introduction to Information Retrieval（2008，免費電子版）——第8章的完整版。
  • Dan Jurafsky & James Martin, Speech and Language Processing（第3版草案，免費）——第7、9章的完整版。
  • Sejnowski,《深度學習的深度學習》與《Attention Is All You Need》原始論文（2017）——Transformer 起點。

開源程式庫（讀源碼是最好的進階）：

  • rapidfuzz（編輯距離極速版）、pyahocorasick、pysuffixarray。
  • jieba、ckip-transformers（中文分詞）；NLTK、spaCy（英文管線）。
  • zlib、zstandard、lz4（壓縮）；gensim（詞向量/主題模型）。
  • Whoosh、Tantivy、Lucene（搜尋引擎）；Elasticsearch 文件。
  • FAISS、HNSWlib（向量近鄰搜尋——詞向量時代的倒排索引）。

開放課程與實作：

  • CMU 15-721 / Stanford CS276（資訊檢索）、MIT 6.006 字串章節。
  • minisat-style：自己寫一個 gzip 相容的 DEFLATE 壓縮器是絕佳練習專案。
  • 實戰資料集：SIGHAN 分詞 Bakeoff、TREC/MARCO 檢索、WMT 翻譯、LongEval。

下一步#

學完本書後的進階方向有三條：（1）理論線——字串演算法的隨機化（後綴陣列 SA-IS、Karp-Rabin 的多樣式推廣）、序列比對的下界與 Four Russians 技巧；（2）系統線——分散式索引（Elasticsearch 叢集）、流式文字處理、向量資料庫；（3）智能線——RAG 系統工程、LLM 微調與對齊、多模態文字理解。無論走哪條，本書建立的地基——比對、索引、壓縮、表示——都會反覆出現。

文字是電腦最早的朋友，也仍是 AI 時代最核心的介質。願這本書讓你在下一次面對一串字元時，看到的不只是文字，而是演算法的舞台。

練習#

  1. 畫一張「全書演算法地圖」：把 30 個小節的演算法標在「預處理成本 × 查詢成本」的平面上，標出 KMP、AC、後綴陣列、倒排索引、MinHash 各自的位置，寫 300 字總結「何時該建索引」的決策法則。
  2. 綜合實作：把第3章的 AC 自動機、第8章的 TF-IDF、第10章的指紋比對組成一個「文章查重＋敏感詞檢查」的 CLI 工具，接受一個目錄，輸出報告；這也是一份好的課程期末作品。
  3. 選一個你感興趣的現實系統（輸入法、git diff、瀏覽器查找、防毒軟體），用本書的語言寫 500 字分析它背後的文字演算法設計，指出它用了哪些章節的技術、又做了哪些本書未涵蓋的工程取捨。