核心概念#

本章將有限狀態機（Finite State Machine）和動態規劃（Dynamic Programming）兩個重要的計算機科學概念結合起來，說明它們在地圖服務和本地搜索中的核心應用。

1. 地址分析和有限狀態機#

  • 智能手機的定位和導航功能依賴三項關鍵技術：衛星定位、地址識別、最短路線規劃
  • 地址識別看似簡單，實際上涉及上下文有關的文法，用程式處理並不容易
  • 例如「北京東路」在上海是路名，在南京也是路名，需要根據上下文（城市名）判斷

有限狀態機的結構#

  • 有限狀態機是一種特殊的有向圖，包含若干狀態（節點）和連接狀態的有向弧
  • 每個有限狀態機有一個開始狀態和一個終止狀態，以及若干中間狀態
  • 以中國地址識別為例：開始 → 省 → 市 → 區縣 → 街道 → 號 → 終止
  • 如果一條地址能從開始狀態走到終止狀態，則該地址有效

有限狀態機的用途遠不止地址識別。Google Now 的核心就是一個有限狀態機，它根據用戶的地理位置、日曆和其他資訊，提供個人化的服務（導航、撥打電話等）。

  • 使用有限狀態機識別地址的兩個關鍵問題：建立狀態機、設計匹配算法——兩者都有現成的解決方案
  • 當用戶輸入不標準或有錯別字時，基於概率的有限狀態機和馬爾可夫鏈可以進行模糊匹配

2. 全球導航和動態規劃#

  • 全球導航的核心算法是動態規劃（Dynamic Programming, DP）
  • 在加權圖（Weighted Graph）中，尋找兩點之間的最短路徑（Shortest Path）是常見問題
  • 窮舉法的複雜度隨節點數呈指數級增長，完全不可行

動態規劃的原理#

  • 以從北京到廣州為例：假設最短路線經過鄭州，那麼北京到鄭州的這段路必然也是所有北京到鄭州路線中最短的
  • 否則就能找到更短的替代路線，與「全程最短」矛盾
  • 因此可以將「全程最短路線」分解為多個「局部最短路線」的小問題
  • 具體做法：在圖上畫一條橫切線，從北京到廣州的路線必經切線上的某個城市，只需找到切線上每個城市的局部最短路徑，再逐步推進至終點

動態規劃的精髓：正確的數學模型可以將一個看似計算量巨大的問題，大幅降低計算複雜度。例如從北京到廣州，動態規劃的計算量約為 $10 \times 10 \times 15 = 1500$，而窮舉法則是 $10^{15}$，相差萬億倍。

3. 延伸閱讀：有限狀態傳感器#

  • 有限狀態機在語音識別和自然語言處理中極為重要，其中常用的是加權的有限狀態傳感器（Weighted Finite State Transducer, WFST）
  • WFST 的特殊性：每個狀態由輸入和輸出符號定義，並且可以有不同的概率權重

嚴格定義#

有限狀態機是一個五元組 $(\Sigma, S, s_0, \delta, f)$：

  • $\Sigma$：輸入符號的集合

  • $S$：有限狀態集合

  • $s_0$：起始狀態

  • $\delta$：從 $S \times \Sigma$ 到 $S$ 的映射函數

  • $f$：終止狀態

  • 在語音識別中，每個被識別的句子都可以用一個 WFST 表示，其中概率最大的路徑就是識別結果，而找最佳路徑的算法正是動態規劃

  • AT&T 實驗室的三位科學家莫瑞（Mehryar Mohri）、皮耶爾（Fernando Pereira）和瑞利（Michael Riley）花了很多年編寫了通用的基於概率的有限狀態機 C 語言工具庫

本章小結#

有限狀態機和動態規劃的應用非常廣泛，遠不止地址識別和導航。它們在語音識別、拼寫和語法糾錯、拼音輸入法、工業控制和生物序列分析等領域都有極其重要的應用。

Backward Tf Idf Relevance Google Ak47 Designer Forward