7.2 中文分詞演算法#

概念說明#

英文以空格分詞，中文詞與詞之間沒有分隔符：「我喜歡演算法」要切成「我 / 喜歡 / 演算法」，必須靠演算法判斷。中文分詞是所有中文 NLP 任務（搜尋、翻譯、問答）的第一道工序，而且有三大難點：

歧義切分：「南京市長江大橋」可切「南京市 / 長江 / 大橋」（對）或「南京 / 市長 / 江大橋」（錯）——「市長」與「長江」共享「長」字造成交集歧義。
未登錄詞（OOV）：人名「陳時中」、店名、新詞「口罩實名制」不在任何詞典裡。
顆粒度不定：「中研院」vs「中央研究院」，視應用而定。

三大主流方法：

詞典法（機械式）：用詞典做最大匹配（Maximum Matching, MM）——正向或反向，每步貪婪切出詞典中最長的詞。快而簡，但解不了歧義。進階版用 n-最短路徑法：把句子建成詞圖（所有詞典詞是邊），切分 = 找路徑，按詞數/詞長評分取前 n 優路徑。
統計法：把分詞視為序列標註（每個字標 B/B/M/E/S：詞頭/中/尾/單字詞），用 HMM、CRF 或雙向 LSTM+CRF 從標註語料學習。HMM 用維特比演算法（Viterbi）找最優標註序列，能處理部分未登錄詞（人名常呈現特定 BME 模式）。
混合與神經法：工業級系統（jieba、CKIP、HanLP）混合詞典＋統計＋自學習新詞發現；現代 LLM 則用 BPE 類子詞切分，避開「詞」的定義本身。

評估指標：精確率 P、召回率 R、F1——切對的詞占系統輸出的比例、占標準答案的比例。SIGHAN Bakeoff 為標準競賽語料；現代系統 F1 約 96–98%，但 OOV 與領域外仍是痛點。本節實作詞典法與 HMM 思想入門，並用 3.1 節的 Trie 加速最大匹配。

演算法步驟#

正向最大匹配（FMM）： 1. 載入詞典（建 Trie），記最大詞長 L。 2. 從句首開始：嘗試最長 L 字的前綴，依 L、L−1、…、1 逐步縮短，找到第一個在詞典中的詞即輸出；都不在則輸出單字。 3. 游標移到該詞之後，重複直到句尾。

反向最大匹配（BMM）：從句尾倒著做同樣的事。雙向最大匹配：兩者都做，若結果一致則採用；不一致時依「切分數較少、單字詞較少」等啟發式選擇——多數歧義句可被此法救回。

HMM 序列標註（概念）： 1. 狀態 = {B, M, E, S}；觀察 = 字。 2. 從標註語料估計：初始機率 π、轉移機率 A（如 B→M/E、M→M/E、E→任意、S→任意）、發射機率 b(字|狀態)（未見字用平滑處理）。 3. 對輸入句跑 維特比：動態規劃求機率最大的狀態序列，再按 B/M/E 邊界輸出詞。

Python 程式碼範例#

DICT = set("我 喜歡 演算法 南京市 市長 長江 江大橋 大橋 南京 市長江 "
           "橋 愛 資料 結構 資料結構 中研院 中央研究院".split())
L = max(map(len, DICT))

def fmm(s, dic=DICT, maxlen=L):
    out, i = [], 0
    while i < len(s):
        for l in range(min(maxlen, len(s) - i), 0, -1):
            if s[i:i + l] in dic:
                out.append(s[i:i + l]); i += l; break
        else:
            out.append(s[i]); i += 1
    return out

def bmm(s, dic=DICT, maxlen=L):
    out, j = [], len(s)
    while j > 0:
        for l in range(min(maxlen, j), 0, -1):
            if s[j - l:j] in dic:
                out.append(s[j - l:j]); j -= l; break
        else:
            out.append(s[j - 1]); j -= 1
    return out[::-1]

def bidir(s):
    f, b = fmm(s), bmm(s)
    return f if f == b else min(f, b, key=lambda x: (len(x), x.count(""))) or f

tests = ["我喜歡演算法", "南京市長江大橋", "我愛資料結構", "中研院在台北"]
for t in tests:
    print(f"{t}: FMM={fmm(t)}  BMM={bmm(t)}")
# 南京市長江大橋: FMM=['南京市','長江','大橋']  BMM=['南京市','長江','大橋']
# （換成「南京市委員會」就會看到 FMM 與 BMM 分歧）

try:
    import jieba
    for t in tests:
        print(t, "jieba:", list(jieba.cut(t)))
except ImportError:
    print("（pip install jieba 可比較工業級結果）")

複雜度分析#

FMM/BMM：每位置至多 L 次詞典查詢（Trie 為 O(L) 步），總 O(n×L)；n 為句長、L 為最大詞長（通常 ≤ 8）。
詞圖＋最短路徑：邊數 O(n×L)，Dijkstra/DP O(n×L)；n-best 用 A* 或延遲展開。
HMM 維特比：O(n×|S|²)，|S|=4 極小，實務瓶頸在發射表載入。
實務數字：詞典法每秒百萬字級；jieba 的精確模式為詞典＋HMM 混合，F1 約 95%+；神經序列標註（LSTM/Transformer）F1 96–98% 但慢 10–100 倍。

練習#

實作 雙向最大匹配 完整版：對 FMM 與 BMM 結果不一致的句子，用「單字詞越少越好、總詞數越少越好」評分取勝者；找 3 個交集歧義句驗證雙向法確實勝過單向。
用 3.1 節的 Trie 取代 set 實作 FMM，並實作「n-最短路徑」：把句子建成詞圖，用 DP 求前 3 短路徑，觀察「南京市長江大橋」的多種候選切分。
實作玩具版 字級標註：手寫一個 20 句的標註語料（如「我/S 喜歡/B 演算法/E」），統計 π、A、b，寫維特比解碼，測試一句訓練外的句子，觀察發射機率缺失（未登錄字）時的行為並加平滑修正。