Python 如何編寫一個拼寫糾錯器？

2007 年的某個星期，我的兩個朋友(Dean 和 Bill) 分別向我傳達了他們對 Google 的拼寫自動糾錯能力的讚歎。例如輸入"speling"，Google 會立即顯示"spelling"的檢索結果。我原以為這兩位才智卓越的工程師、數學家，會對其工作原理有準確的推測，事實上他們沒有。後來我意識到，他們怎麼會對離自身專業領域如此遠的東西認知清晰呢？

我覺得他們還有其他人，也許能從拼寫糾錯原理的解釋中獲益。工業級的完整拼寫糾錯相當複雜(詳細參見 1和 2)，在橫貫大陸的航空旅途中，我用約半頁代碼寫了一個迷你拼寫糾錯器，其性能已經達到對句子以 10 詞/秒的速度處理，且糾錯準確率達到 80%~90%。

代碼如下：

函數 返回一個最有可能的糾錯還原單詞：

它是如何工作的：概率理論

調用 函數將試圖選出對於詞 w 最有可能的拼寫糾正單詞，概率學上我們是無法預知應該選擇哪一個的（例如，"lates"應該被糾正為"late"還是"latest"或"latters"...？）。對於給定的原始詞 w，我們試圖在所有可能的候選集合中，找出一個概率最大的修正結果 c。

$$argmax_c in candidatesP(c|w)$

根據 貝葉斯原理，它等價於：

argmaxcincandidatesfracP(c)P(w|c)P(w)

由於對 w 的每個候選單詞 c，其 P(w) 均相等，因此剔除後公式如下：

argmaxcincandidatesP(c)P(w|c)

該式分為 4 個部分：

1.選擇機制：argmax

選擇候選集中概率最高的單詞。

2.候選模型：cincandidates

有哪些候選單詞可供考慮。

3.語言模型：P(c)

c 在英語文本中出現的概率。例如：在英語文本出現的單詞中，約 7%是"the"，那麼 P(the)=0.07

4.錯誤模型：P(w|c)

當作者本意是 c 結果打成 w 的概率。例如:概率 P(the|the) 相當高，而 P(theeexyz|the) 將非常低。

一個顯而易見的問題是：為什麼將簡單的表達 P(c|w) 引入兩個模型使得其變得更複雜？答案是 P(c|w) 本身就是兩個部分的合并，將二者分開能更明確地進行處理。考慮對錯誤拼寫"thew"進行還原，兩個候選單詞分別是"the"和"thaw"，二者誰的 P(c|w) 更高呢？"thaw"的優點在於它只對原詞做了細小的改變：將 e 換成 a 。而另一方面，"the"似乎是一個更常見的詞，儘管增加 w 似乎變化更大，可能性更小，也許是打字者在敲"e 後手滑呢？問題的核心在於：為了計算 P(c|w) 我們必須同時考慮 c 出現的概率，以及從 c 變成 w 的可能性。因此顯式地分為兩部分，思路上會更清晰。

它是如何工作的：Python 部分

該程序的 4 個部分：

1.選擇機制：在 Python 中，帶 的 函數即可實現 argmax 的功能。

2.候選模型：先介紹一個新概念：對一個單詞的簡單編輯是指：刪除(移除一個字母)、置換(單詞內兩字母互換)、替換(單詞內一個字母改變)、插入(增加一個字母)。函數 返回一個單詞的所有簡單編輯（譯者：稱其編輯距離為 1）的集合，不考慮編輯後是否是合法單詞:

這個集合可能非常大。一個長度為 n 的單詞，有 n 個刪除編輯，n?1 個置換編輯，26n 個替換編輯，26(n 1) 的插入編輯，總共 54n 25 個簡單編輯（其中存在重複）。例如：

然而，如果我們限制單詞為已知( ，譯者：即存在於 WORDS 字典中的單詞)，那麼這個單詞集合將顯著縮小：

我們也需要考慮經過二次編輯得到的單詞（譯者："二次編輯"即編輯距離為 2，此處作者巧妙運用遞歸思想，將函數 返回集合里的每個元素再次經過 處理即可得到），這個集合更大，但仍然只有很少一部分是已知單詞：

我們稱 結果中的每個單詞與 w 的距離為 2。

3.語言模型：我們通過統計一個百萬級詞條的文本 big.txt中各單詞出現的頻率來估計 P(w)，它的數據來源於 古騰堡項目中公共領域的書摘，以及 維基詞典中頻率最高的辭彙，還有 英國國家語料庫，函數 將文本分割為片語，並統計每個詞出現的頻率保存在變數 中， 基於該統計評估每個詞的概率：

可以看到，去重後有 32,192 個單詞，它們一共出現 1,115,504 次，"the"是出現頻率最高的單詞，共出現 79,808 次(約佔 7%)，其他詞概率低一些。

4.錯誤模型：2007 年坐在機艙內寫這個程序時，我沒有拼寫錯誤的相關數據，也沒有網路連接(我知道這在今天可能難以想像)。沒有數據就不能構建拼寫錯誤模型，因此我採用了一個捷徑，定義了這麼一個簡單的、有缺陷的模型：認定對所有已知詞距離為 1 的編輯必定比距離為 2 的編輯概率更高，且概率一定低於距離為 0 的單詞（即原單詞）。因此函數 的優先順序如下：

1. 原始單詞（如果已知），否則到 2。

2. 所有距離為 1 的單詞，如果為空到 3。

3. 所有距離為 2 的單詞，如果為空到 4。

4. 原始單詞，即使它不是已知單詞。

效果評估

現在我們看看程序效果如何。下飛機後，我從牛津文本檔案庫下載了 Roger Mitton 的 伯克貝克拼寫錯誤語料庫，從中抽取了兩個錯誤修正測試集，前者在開發中作為參考，調整程序以適應其結果；後者用於最終測試，因此我不能偷看，也無法在評估時修改程序。取兩個集合分別用於開發和測試是個好習慣，它讓我不至於自欺欺人地調整程序以適應結果，然後覺得程序效果有提升。我還寫了單元測試：

結果如下：

可以看到，開發部分的集合準確率達到了 74%（處理速度是 41 詞/秒），而在最終的測試集中準確率是 68%（31 詞/秒）。結論是：我達到了簡潔，開發時間短，運行速度快這 3 個目的，但準確性不太高。也許是我的測試集太複雜，又或是模型太簡單因故而不能達到 80%~90%的準確率。

後續工作

考慮一下我們如何做的更好。

1. 語言模型 P(c)。在語言模型中我們能區分兩種類型的錯誤（譯者：known 詞和 unknown 詞，前者 2 次編輯詞集合存在元素 inWORDS，後者不存在），更為嚴重的是 unknow 詞，程序會直接返回該詞的原始結果。在開發集合中，有 15 個 unknown 詞，約佔 5%，而測試集中有 43 個（11%）。以下我們給出部分 的運行結果：

我將期望輸出與實際輸出分別列印出來，計數"0 表示目標辭彙不在詞庫字典內，因此我們無法糾錯。如果能收集更多數據，包括使用一些語法(例如在單詞後加入"ility"或是"able")，我們能構建一個更好的語言模型。

處理 unknown 辭彙的另一種辦法是，允許 結果中出現我們沒見過的辭彙。例如，如果輸入是"electroencephalographicallz"，較好的一種修正是將末尾的 z 替換成 y ，儘管"electroencephalographically"並不在詞庫里，我們可以基於詞成分，例如發音或後綴來實現此效果。一種更簡單的方法是基於字母序列：統計常見 2、3、4 個字母序列。

2. 錯誤模型 P(w|c)。目前為止我們的錯誤模型相當簡陋：認定編輯距離越短錯誤越小。這導致了許多問題，許多例子中應該返回編輯距離為 2 的結果而不是距離為 1。如下所示：

為何"adres"應該被修正為"address"而非"acres"呢？直覺是從 d 到"dd"和從"s 到"ss"的二次編輯很常見，應該擁有更高的概率，而從"d 到"c 的簡單編輯概率很低。

顯然我們可以根據編輯開銷來改進模型：根據直覺將疊詞的編輯開銷降低，或是改變母音字母。一種更好的做法是收集數據：收集拼寫錯誤的語料，並對照正確單詞統計增刪、替換操作的概率。想做好這些需要大量數據：例如給定窗口大小為 2 的兩個單詞，如果你想得到兩者間的全部修正概率，其可能的轉換有 266 種，超過 3000 萬辭彙。因此如果你想獲取每個單詞的幾個轉換實例，大約需 10 億條修正數據，如要保證質量，大概需要 100 億之多。

注意到語言模型和錯誤模型存在聯繫：目前如此簡陋（編輯距離為 1 的詞必定優於編輯距離為 2 的詞）的錯誤模型給語言模型造成阻礙：我們不願將相對冷僻的詞放入模型內，因為如果這類詞恰好與輸入單詞的編輯距離為 1，它將被選中，即使存在一個編輯距離為 2 但很常見的詞。好的錯誤模型在添加冷僻詞時更富有侵略性，以下例子展示了冷僻詞出現在字典里的危害：

3. 修正集合 argmaxc。本程序會枚舉某單詞所有編劇距離 2 以內的修正，在開發集的 270 個修正詞中只有 3 個編輯距離超過 2，然而在測試集合中，23/400 個編輯距離超過 2，它們是：

我們可以考慮擴展一下模型，允許一些編輯距離為 3 的詞進入修正集合。例如，允許母音之後插入母音，或母音間的替換，又或 c 和 s 之間的替換。

4. 第四種（也可能是最佳）改進方案為：將 的文本窗口調大一些。當前的 只檢測單個詞，然而在許多情形下僅靠一個單詞很難做出判決。而假若這個單詞恰好出現在字典里，這種糾錯手段就更顯無力。例如：

我們幾乎不可能知道 在某個語句內應該返回"were"，而在另一句返回"where"。但如果輸入語句是 ，我們很容易判定此處"where"應該被糾錯為"were"。

要構建一個能同時處理詞和上下文的模型需要大量數據。幸運的是，Google 已經公開了最長 5 個詞的全部序列 詞庫，該數據源於上千億的語料集。我相信要使拼寫糾錯準確率達到 90%，必須依賴上下文輔助決策，關於這個以後我們再討論。

我們也可以決定以哪種方言進行訓練。以下糾正時產生的錯誤均源於英式和美式拼寫間的差異：

5. 最後，我們可以改進實現方法，使程序在不改變結果的情況下運行速度更快。例如：將實現該程序的語言從解釋型語言換成編譯型語言；緩存糾錯結果從而不必重複糾錯。一句話：在進行任何速度優化前，先大致看看時間消耗情況再決定優化方向。

閱讀材料

Roger Mitton 關於拼寫檢測的 調研文章

Jurafsky 和 Martin 的教材中 拼寫檢測部分。

Manning 和 Schutze 在他們編撰的 Foundations of StatisticalNatural Language Processing 中很好的講述了統計語言模型, 但似乎沒有(至少目錄中沒有) 提及拼寫檢查。

aspell 項目中有大量有趣的材料，其中的一些 測試數據似乎比我使用的更好。

LinPipe 項目有一個 拼寫檢測教程

原文地址：How to Write a Spelling Corrector?

題圖：pexels，CC0 授權。

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！