本章探討計算機處理各種問題的底層邏輯。計算機雖然最初用於科學計算，但其所處理的對象很快涵蓋了現實世界的一切事物。對這些事物的操作，大部分其實不是計算，而是分類、組織、查找和重組。本章圍繞這兩座橋梁——從實際問題到分類，再從分類到計算機算法——展開討論。

4.1 這是選擇分類問題#

很多被冠以高大上名稱的事情，本質上都是模式分類的問題。無論是語音識別、手寫體識別、人臉識別，甚至計算機自動翻譯，都屬於分類問題。

• 下棋問題的本質：計算機下棋本質上是一個 N 選 1 的問題，可以用博弈樹（Game Tree）來建模，將實際問題和信息處理之間建立橋梁
• 手寫體識別：將各種漢字形狀的圖形分類到國家標準漢字類別中。手寫體識別比印刷體識別更難，因為前者各類別之間的邊界比較模糊
• 模式識別的本質：在多維空間中劃出不同的區域，將所有不同寫法都歸入相應的類別。要分的類別越多，準確分類就越難
• 選擇與分類的關係：二者在很多場合下是相關的，比如網頁搜索既涉及選擇（從文獻中挑選符合條件的），也涉及分類（將網頁分為相關和不相關的兩大類）

要點：很多智能問題都是模式分類的問題，計算機科學家的任務就是將現實生活中的這些問題變成分類問題。

4.2 組織信息：集合與判定#

智能操作的底層邏輯是選擇和分類，而要在計算機中實現這些操作，需要借助集合論來建立橋梁。

集合的三個基本性質#

• 判定性：給定一個事物，能判斷它是否屬於某個集合，結果是二值的（是或否），沒有模糊的中間情況
• 外延公理：兩個集合相同，當且僅當它們的所有元素都相同
• 無重複與無序：集合中不能有重複的元素，元素沒有次序關係

二叉決策樹#

• 利用「是」和「非」的二值邏輯，可以用二叉樹表示分類邏輯
• 二叉決策樹的三大優勢：
  • 操作簡單，每一步只是一個簡單的判定
  • 能高效表示大量事物（N 層可表示 2^N 種信息）
  • 具有自相似性，局部操作可擴展到所有情況
• 從數學上講，一到多的分類和一到二的分類是等價的，二叉樹和 N 叉樹也完全等價

哈希表#

• 當集合的特徵不明確時，無法用決策樹進行判定；但如果能枚舉集合內的所有元素，就可以用哈希表來實現判定
• 應用場景：手機通訊錄的騷擾電話過濾、網站黑名單/白名單
• 三種實現方式：
  • 直接存儲整個哈希表（空間換時間）
  • 使用布隆過濾器（Bloom Filter），可能有少量假陽性
  • 二叉決策樹和哈希表結合：先用規則分類，規則無法涵蓋的再用哈希表處理

集合概念在語音識別中的應用#

• 語音識別分兩步：從物理聲波到讀音符號，再從讀音到語句
• 利用 N 叉樹根據讀音查找對應的詞，再根據上下文構建最可能的語句
• 計算機在做語音識別時會考慮常見錯誤，將常見的白字放到哈希表中進行糾錯

要點：對於邊界不可描述、但所包含的元素可以枚舉的集合，可以通過哈希表來判定一個元素是否屬於該集合。

4.3 B+ 樹、B* 樹：數據庫中的數據組織方式#

本節討論如何有效地組織和查找數據，核心概念是鍵（Key）和值（Value）的二元組。

樹狀結構的優勢#

• 二分（或 N 分）的直接結果就是一層層地將事物分門別類，形成集合的層次結構
• 不過對於很多問題，直接採用 N 叉樹可能比二叉樹更有效率

B 樹#

• 由魯道夫·拜爾和愛德華·麥克科雷特提出的一種受限制的 N 叉樹
• 每個節點可以有多個鍵，鍵的數量被限制在 d 和 2d 之間
• B 樹的三個特別要求：根節點要有 2~2d 個子節點；節點內的鍵按順序排列；子節點的鍵值範圍由父節點的鍵劃定

B+ 樹#

• B+ 樹是 B 樹在數據庫系統中最常用的變種，有兩個關鍵改進：
  • 非葉節點只保留鍵（用於確定區間），所有內容都保留在葉節點
  • 用指針將所有葉節點從頭到尾穿起來
• 優點：結構乾淨、方便區間查詢、兼具二叉樹的高效和 N 叉樹的靈活

B* 樹#

• B* 樹是 B+ 樹的進一步改進，在內部節點之間增加了指向兄弟節點的指針
• 對合併小節點和分裂大節點的機制做了調整，使得空間浪費更少
• Oracle 數據庫就採用了 B* 樹的存儲結構

等價性原則#

• 各種樹在計算機科學上都是等價的，研究清楚一種樹的算法，就能在做適當變通之後解決各種具體問題
• 這是計算機科學的精髓所在

要點：通過 B 樹、B+ 樹和 B* 樹，了解如何實現一個 N 叉樹，了解它們的時間複雜度和實現技巧。

4.4 卡特蘭數#

本節討論一個經典的組合數學問題：有多少種 N 個葉節點的滿二叉樹（Full Binary Tree）？

滿二叉樹的計數#

• 滿二叉樹：所有節點的子樹棵數要麼是 2，要麼是 0（即葉節點）
• 使用遞歸的思路自頂向下解決：假定 N 個葉節點的滿二叉樹數量為 S(N)，任何一棵二叉樹都可以分為左子樹（k 個葉節點）和右子樹（N-k 個葉節點）
• 遞推公式：S(N) = ΣS(k)·S(N-k)，其中 k 從 1 到 N-1
• 解析解：S(N) = C(2N-2, N-1) / N
• 發現這個遞推公式的是數學家歐仁·卡特蘭（Eugene Catalan），因此這個數字被稱為卡特蘭數

卡特蘭數的等價問題#

• 凸多邊形的三角劃分：將凸 N 邊形劃分為 N-2 個不重疊的三角形的方法數，等於卡特蘭數 C(N-2)
• N 個字符的字符串合併：N 個字符的字符串中，相鄰字符可以合併為新字符，合併方法的數量是卡特蘭數 C(N-1)
• 卡特蘭數也是語法分析樹數量的上限，這是句法分析非常難的原因

面試中的考察重點#

• 能否建立遞歸的思維方式
• 能否看出不同問題之間的等價性
• 高明的計算機科學家能通過研究一個問題解決一大批問題，做到「一通百通」

要點：卡特蘭數、句法分析的多種可能性。很多計算機科學中的問題都是等價的，能看出等價性並舉一反三，是需要不斷培養的能力。