7.1 英文分詞與詞幹化#

概念說明#

分詞（tokenization）是把字元串切成「詞」的過程，看似簡單卻到處是坑：don't 要不要切成 do + n't？New York 是一個詞還是兩個？state-of-the-art 的連字號？URL、Email、小數 3.14 顯然不能按空格切？正規表示式（1.3 節）是解決這些問題的基礎工具。

為什麼需要詞幹化（stemming）與詞形還原（lemmatization）？ 搜尋 "running" 時，使用者期望也找到 "run"、"runs"、"ran"——同一概念的多種屈折形式應該歸併。兩種歸併策略：

詞幹化：用規則粗暴砍詞尾，快但可能過頭（"university" → "univers"？Porter 算法其實輸出 "univers"）。代表是 Porter 演算法（1980）與改良版 Porter2/Snowball。
詞形還原：用詞典＋詞性找出真正的原形（ lemma），正確但需要詞典與 NLP 管線（如 WordNet Lemmatizer）。

Porter 演算法是規則系統的教科書範例：把詞尾分成五級（step 1a: sses→ss, ies→i, s→""；step 1b: ed/ing 前有母音則刪並觸發 at→ate, bl→ble, iz→ize…；step 2~4 依「詞幹長度 m」決定是否刪除 longer 詞尾如 ational→ate、ousness→ous；step 5 去尾 e 與雙寫輔音）。判斷的核心量是 measure m：一個詞幹 = 輔音串(C)(母音串V)…(C) 的形式，m = VC 對的數目。例如 TREE 的 m=0、OAT 的 m=1、TROUBLE 的 m=2。規則形如「條件 m > 1 時刪除」——短詞保護（"hopping"→"hop" 而非 "hop"→"hop" 誤砍）。

進一步的規格化（normalization）還包括：轉小寫、Unicode 正規化（1.2 節）、停用詞（stop words：the、a、is 等高頻無區別力的詞）過濾。這些前處理共同構成搜尋引擎與分類器的「清洗管線」。現代 NLP 中，神經模型多用子詞分詞（BPE、WordPiece，9.3 節會遇到），它取代了部分詞幹化的功能——把 "transformers" 切成 "transform" + "ers"，讓模型自己學詞形變化。

演算法步驟#

分詞：正規表示式 r"\w+(?:[-.']\w+)*" 抓「字串＋可選連字/撇號延續」，或更簡單的 r"[A-Za-z0-9']+"。
規格化：lowercase、NFC 正規化。
停用詞過濾：對照停用詞表刪除。
Porter 詞幹化（簡化版，示範 step 1 與 measure 概念）：
計算詞幹的 m 值。
step1a：sses→ss、ies→i、ss 不變、s→""。
step1b：含母音的 ed/ing 刪除；刪後若詞尾 at/bl/iz 則補 e，雙寫輔音去一個，m=1 且 CVC 結尾補 e。
（完整版還有 step 2–5，此處示範精神即可，實務用 NLTK。）

Python 程式碼範例#

import re

TOKEN_RE = re.compile(r"[A-Za-z0-9]+(?:['-][A-Za-z0-9]+)*")

def tokenize(text):
    return TOKEN_RE.findall(text)

STOP = {"the", "a", "an", "is", "are", "was", "of", "to", "in", "and", "with"}

def normalize(text, stopwords=True):
    toks = [t.lower() for t in tokenize(text)]
    return [t for t in toks if not (stopwords and t in STOP)]

VOWELS = "aeiou"

def _measure(stem):
    """Porter 的 m 值：VC 對的數目"""
    form = "".join("V" if c in VOWELS else "C" for c in stem)
    return len(re.findall("V+C+", form))

def simple_porter(w):
    """Porter 演算法的 step 1 示範（完整版見 NLTK PorterStemmer）"""
    if w.endswith("sses"): w = w[:-2]
    elif w.endswith("ies"): w = w[:-2]
    elif w.endswith("ss"): pass
    elif w.endswith("s") and len(w) > 2: w = w[:-1]

    m3 = _measure(w[:-3])
    if w.endswith("ing") and m3 > 0:
        w = w[:-3]
        if w.endswith(("at", "bl", "iz")): w += "e"
        elif len(w) > 2 and w[-1] == w[-2] and w[-1] not in VOWELS: w = w[:-1]
        elif _measure(w) == 1 and w[-3:-2] not in VOWELS and \
             w[-2] in VOWELS and w[-1] not in VOWELS: w += "e"
    elif w.endswith("ed") and _measure(w[:-2]) > 0:
        w = w[:-2]
    return w

text = "The algorithms were processing strings; the processed strings are running fast."
print(normalize(text))
# ['algorithms', 'processing', 'strings', 'processed', 'strings', 'running', 'fast']
print([simple_porter(t) for t in ["processing", "processed", "running", "strings", "algorithms"]])
# ['process', 'process', 'run', 'string', 'algorithm']

try:
    from nltk.stem import PorterStemmer
    ps = PorterStemmer()
    print([ps.stem(t) for t in ["university", "hopping", "caresses", "ponies"]])
    # ['univers', 'hop', 'caress', 'poni']
except ImportError:
    print("（安裝 nltk 可看完整 Porter 版本）")

複雜度分析#

分詞：正規表示式掃描 O(n)；停用詞過濾用 set 查詢 O(1) 每詞，總 O(n)。
Porter：規則有限（約 60 條），每條 O(詞長)，總 O(詞長)；整體對 n 個詞 O(n)。
詞形還原（詞典法）：每詞 O(1) 雜湊查詢，但需要詞典資源。
工程注意：過度詞幹化會傷害精確率（"university"→"univers" 讓搜尋「宇宙」不相干的詞也被召回）——搜尋系統常用「索引原詞＋查詢詞幹化」的折衷。

練習#

擴充 simple_porter 實作 step 4（刪除 m>1 詞尾的 -al、-ance、-ence、-er、-ic、-able、-ible、-ant、-ent、-ion（其前須為 s/t）…），對照 NLTK 的輸出檢驗 20 個詞。
建一個 3 萬詞的英文詞表，比較「詞幹化歸併後的詞數」與原詞數，找出 5 個「歸併過頭」的例子（不同原詞被併成同一詞幹）與 5 個「歸併不足」的例子。
實作 BPE 子詞學習（入門版）：從字元詞表開始，反覆統計相鄰 pair 頻率、合併最高頻 pair 共 k 次；對 1000 詞的語料學 k=50 次合併後，觀察 "transformers"、"running" 被切成什麼。