Zellig Harris 與分布分析

計算詞幹提取的起源

在 1955 年，語言學家 Zellig Harris 發表了 From Phoneme to Morpheme，描述了一種方法來發現單詞中有意義單位（詞素）之間的邊界。

他的見解是分布性的：如果你查看英文單詞的大型語料庫，詞幹與後綴之間的邊界會顯示為統計信號。

後繼種類方法

對於任何單詞的前綴，計算語料庫中有多少個不同的字符跟在它後面。Harris 稱這為後繼種類。

考慮語料庫中的前綴 "work" 包含：worked, worker, working, works, workshop。

在 "work" 之後，四個不同的字符可以跟在後面：種類的峰值。那個峰值標記一個詞素邊界。詞幹是 work 而它之後的所有內容都是後綴。

這在 1955 年是激進的。沒有語言規則，沒有字典：只是計數。Harris 表明語言的結構通過分布顯示自己。

理解後繼種類

Harris 的方法適用於任何語言。你不需要知道語法：統計數據顯示詞素邊界。

實際上，純後繼種類需要大型語料庫與仔細的峰值檢測。後來的研究人員：Lovins (1968)、Porter (1980) 將方法簡化為基於規則的後綴剝離：與其從語料庫計算後繼種類，他們直接編碼後綴規則。

今天你將構建一個受 Harris 見解啟發的基於規則的後綴剝離器。你將明確定義後綴，然後從單詞中剝離它們。這是大多數生產詞幹提取器的工作方式。

你的第一個後綴剝離器

讓我們編碼

從簡單開始。編寫一個名為 stem 的函數，它接受一個單詞 & 剝離這些後綴（按此順序）：

1. -ing (running → runn)

2. -ed (walked → walk)

3. -ly (quickly → quick)

4. -s (cats → cat)

規則：

- 首先將單詞轉換為小寫

- 只剝離一個後綴（上面順序中的第一個匹配）

- 只有在剩餘的詞幹至少 3 個字符長的情況下才剝離

- 返回詞幹

範例：

def stem(word):
    word = word.lower()
    # your suffix stripping logic here
    return word

處理邊界情況

讓詞幹提取器更聰明

你的基本剝離器有一個問題：running → runn & hoping → hop。我們需要兩項改進：

1. 雙輔音清理：如果剝離 -ing 或 -ed 在末尾留下雙輔音（如 runn），移除最後一個字母 → run

2. 無聲 e 還原：如果剝離 -ing 留下一個以輔音結尾的詞幹（不是元音），& 原始詞可能有無聲的 e（如來自 hoping 的 hop），加回 e → hope

對於無聲 e 規則，保持簡單：如果在剝離 -ing 後，詞幹是 3+ 個字符，以輔音結尾，& 倒數第二個字符是元音（如 hop、mak、tak 的模式），加回 e。

也添加這些新後綴（在 -ing、-ed、-ly、-s 之前檢查它們）：

5. -tion (organization → organiza)

6. -ness (happiness → happi)

7. -ment (movement → move)

8. -able (readable → read)

9. -ible (sensible → sens)

更新的後綴優先級：-tion、-ness、-ment、-able、-ible、-ing、-ed、-ly、-s

保持最小詞幹長度規則：只有在剩餘詞幹為 3+ 個字符時才剝離。

-ies & -ier 規則

更多形態學

英文有另一個常見的模式：以 -y 結尾的單詞在詞形變化時變為 -ies、-ied 或 -ier。

在 -s & -ed 檢查之前添加這些規則：

- -ies → 剝離 & 添加 i (babies → babi)

- -ied → 剝離 & 添加 i (carried → carri)

- -ier → 剝離 & 添加 i (earlier → earli)

相同的最小詞幹長度規則：只有在結果為 3+ 個字符時才轉換。

為什麼測試？

測試不是可選的

你有一個有效的詞幹提取器。你怎麼知道它實際上有效？現在，你正在手動運行幾個例子。這不會擴展。

專業軟件使用三個級別的測試：

單元測試：用已知輸入和預期輸出隔離測試一個函數。快速、眾多、具體。

集成測試：測試多個組件能否協同工作。對於詞幹提取器，這意味著根據一批單詞進行測試，並驗證結果是一致的。

功能測試：從外部測試系統，就像用戶會做的那樣。對於詞幹提取器，這意味著輸入真實文本並驗證輸出對實際用例（如搜索）是否有意義。

你將編寫全部三個。

編寫單元測試

單元測試

編寫一個名為 run_unit_tests 的函數，用至少 15 個測試用例測試你的 stem 函數，涵蓋：

1. 基本後綴剝離：以 -ing、-ed、-ly、-s 結尾的單詞

2. 複雜後綴：-tion、-ness、-ment、-able、-ible

3. Y-詞形變化：-ies、-ied、-ier

4. 邊界情況：不應被剝離的短單詞、沒有後綴的單詞、已經詞幹化的單詞

5. 雙輔音清理：running → run、sitting → sit

6. 無聲 e 還原：hoping → hope

7. 不區分大小寫：大寫輸入應被小寫

像這樣結構你的測試：

def run_unit_tests():
    tests = [
        ('running', 'run'),
        ('cats', 'cat'),
        # ... at least 15 test cases
    ]
    passed = 0
    failed = 0
    for word, expected in tests:
        result = stem(word)
        if result == expected:
            passed += 1
        else:
            failed += 1
            print(f'FAIL: stem({word}) = {result}, expected {expected}')
    print(f'{passed}/{passed + failed} unit tests passed')
    return failed == 0

編寫集成測試

集成測試

單元測試驗證單個輸入。集成測試驗證組件能否正確協同工作。

對於詞幹提取器，一個關鍵的集成屬性是一致性：如果你兩次詞幹化同一個單詞，你會得到相同的結果。& 應該共享詞幹的單詞應該產生相同的詞幹。

編寫一個名為 run_integration_tests 的函數，測試：

1. 冪等性：詞幹化已經詞幹化的單詞應返回相同詞幹。stem(stem(word)) == stem(word) 對所有單詞。

2. 分組：應該共享詞幹的單詞實際上這樣做。測試至少 3 個單詞家族（例如，run/runs/running/runner 應該都共享詞幹）。

3. 批量處理：處理 20+ 個單詞的列表並驗證沒有崩潰、沒有空字符串、沒有 None 值。

def run_integration_tests():
    # Test 1: idempotency
    # Test 2: word family grouping
    # Test 3: batch stability
    ...

編寫功能測試

功能測試

功能測試驗證系統是否適用於其預期使用情況。你的詞幹提取器存在以改進搜索：所以測試那個。

編寫一個名為 run_functional_tests 的函數，：

1. 搜索模擬：給定一個文檔字符串列表和一個查詢單詞，詞幹化文檔和查詢，然後檢查詞幹化的查詢詞是否出現在詞幹化的文檔中。測試搜索 'running' 是否找到包含 'run' 和 'runner' 的文檔。

2. 精度檢查：驗證詞幹化不會錯誤地將無關單詞分組。'university' 和 'universe' 可能共享詞幹：檢查你的詞幹提取器是否處理這個（如果它分組它們是可以的；記錄行為）。

3. 真實文本處理：詞幹化真實英文段落中的每個單詞。驗證輸出是合理的：沒有空字符串、沒有崩潰、輸出的單詞數與輸入相同。

def run_functional_tests():
    # Test 1: search finds related documents
    # Test 2: precision: check over-stemming
    # Test 3: real paragraph processing
    ...

你構建了什麼

你構建了什麼

你實現了一個有效的英文詞幹提取器，包括：

- 12 個後綴規則（-tion、-ness、-ment、-able、-ible、-ies、-ied、-ier、-ing、-ed、-ly、-s）

- 雙輔音清理

- 無聲 e 還原

- 單元測試、集成測試 & 功能測試

血統

你的詞幹提取器來自於從 1955 年 Zellig Harris 開始的工作線：

- Harris (1955)：發現詞素邊界顯示為統計信號（後繼種類）

- Lovins (1968)：首個發布的詞幹提取算法，294 個後綴規則

- Porter (1980)：簡化為 ~60 個規則分為 5 個步驟，成為幾十年的標準

- Snowball (2001)：Porter 的框架推廣到多種語言

- 你的詞幹提取器（今天）：12 個規則，相同的核心原理

接下來你可以做什麼

- 實現完整的 Porter 算法（它已被很好地記錄 & 是一個很好的練習）

- 將你的詞幹提取器移植到 C 以獲得 100 倍的速度改進

- 構建一個簡單的搜索引擎，使用你的詞幹提取器來索引 & 查詢文本文件

- 將你的詞幹提取器的輸出與 NLTK 的 PorterStemmer 比較以測量準確性

你今天編寫的代碼是運行在地球上每個搜索引擎內部的相同基本操作。對於一天的工作來說不錯。