作者：Peter Norvig，譯者：ringocat 來源：https://segmentfault.com/a/1190000009826061
2007 年的某個星期，我的兩個朋友(Dean 和 Bill) 分別向我傳達(dá)了他們對 Google 的拼寫自動糾錯能力的贊嘆。例如輸入'speling'，Google 會立即顯示'spelling'的檢索結(jié)果。我原以為這兩位才智卓越的工程師、數(shù)學(xué)家，會對其工作原理有準(zhǔn)確的推測，事實(shí)上他們沒有。后來我意識到，他們怎么會對離自身專業(yè)領(lǐng)域如此遠(yuǎn)的東西認(rèn)知清晰呢？ 我覺得他們還有其他人，也許能從拼寫糾錯原理的解釋中獲益。工業(yè)級的完整拼寫糾錯相當(dāng)復(fù)雜(詳細(xì)參見 1和 2)，在橫貫大陸的航空旅途中，我用約半頁代碼寫了一個迷你拼寫糾錯器，其性能已經(jīng)達(dá)到對句子以 10 詞/秒的速度處理，且糾錯準(zhǔn)確率達(dá)到 80%~90%。 代碼如下： # coding:utf-8
import re
from collections import Counter
def words(text):
return re.findall(r'w ', text.lower())
# 統(tǒng)計詞頻
WORDS = Counter(words(open('big.txt').read()))
def P(word, N=sum(WORDS.values())):
'''詞'word'的概率'''
return float(WORDS[word]) / N
def correction(word):
'''最有可能的糾正候選詞'''
return max(candidates(word), key=P)
def candidates(word):
'''生成拼寫糾正詞的候選集合'''
return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])
def known(words):
''''words'中出現(xiàn)在 WORDS 集合的元素子集'''
return set(w for w in words if w in WORDS)
def edits1(word):
'''與'word'的編輯距離為 1 的全部結(jié)果'''
letters = 'abcdefghijklmnopqrstuvwxyz'
splits = [(word[:i], word[i:]) for i in range(len(word) 1)]
deletes = [L R[1:] for L, R in splits if R]
transposes = [L R[1] R[0] R[2:] for L, R in splits if len(R) > 1]
replaces = [L c R[1:] for L, R in splits for c in letters]
inserts = [L c R for L, R in splits for c in letters]
return set(deletes transposes replaces inserts)
def edits2(word):
'''與'word'的編輯距離為 2 的全部結(jié)果'''
return (e2 for e1 in edits1(word) for e2 in edits1(e1))
函數(shù) correction(word) 返回一個最有可能的糾錯還原單詞： >>>correction('speling')
'spelling'
>>>correction('korrectud')
'corrected'
它是如何工作的：概率理論調(diào)用 correction(w) 函數(shù)將試圖選出對于詞 w 最有可能的拼寫糾正單詞，概率學(xué)上我們是無法預(yù)知應(yīng)該選擇哪一個的（例如，'lates'應(yīng)該被糾正為'late'還是'latest'或'latters'...？）。對于給定的原始詞 w，我們試圖在所有可能的候選集合中，找出一個概率最大的修正結(jié)果 c。 $$argmax_c in candidatesP(c|w)$ 根據(jù) 貝葉斯原理，它等價于： argmaxcincandidatesfracP(c)P(w|c)P(w) 由于對 w 的每個候選單詞 c，其 P(w) 均相等，因此剔除后公式如下： argmaxcincandidatesP(c)P(w|c) 該式分為 4 個部分：
1.選擇機(jī)制：argmax
選擇候選集中概率最高的單詞。
2.候選模型：cincandidates
有哪些候選單詞可供考慮。
3.語言模型：P(c)
c 在英語文本中出現(xiàn)的概率。例如：在英語文本出現(xiàn)的單詞中，約 7%是'the'，那么 P(the)=0.07
4.錯誤模型：P(w|c)
當(dāng)作者本意是 c 結(jié)果打成 w 的概率。例如:概率 P(the|the) 相當(dāng)高，而 P(theeexyz|the) 將非常低。 一個顯而易見的問題是：為什么將簡單的表達(dá) P(c|w) 引入兩個模型使得其變得更復(fù)雜？答案是 P(c|w) 本身就是兩個部分的合并，將二者分開能更明確地進(jìn)行處理?？紤]對錯誤拼寫'thew'進(jìn)行還原，兩個候選單詞分別是'the'和'thaw'，二者誰的 P(c|w) 更高呢？'thaw'的優(yōu)點(diǎn)在于它只對原詞做了細(xì)小的改變：將'e'換成'a'。而另一方面，'the'似乎是一個更常見的詞，盡管增加'w'似乎變化更大，可能性更小，也許是打字者在敲'e'后手滑呢？問題的核心在于：為了計算 P(c|w) 我們必須同時考慮 c 出現(xiàn)的概率，以及從 c 變成 w 的可能性。因此顯式地分為兩部分，思路上會更清晰。 它是如何工作的：Python 部分該程序的 4 個部分：
1.選擇機(jī)制：在 Python 中，帶 key 的 max() 函數(shù)即可實(shí)現(xiàn) argmax 的功能。
2.候選模型：先介紹一個新概念：對一個單詞的簡單編輯是指：刪除(移除一個字母)、置換(單詞內(nèi)兩字母互換)、替換(單詞內(nèi)一個字母改變)、插入(增加一個字母)。函數(shù) edits1(word) 返回一個單詞的所有簡單編輯（譯者：稱其編輯距離為 1）的集合，不考慮編輯后是否是合法單詞: def edits1(word):
'''與'word'的編輯距離為 1 的全部結(jié)果'''
letters = 'abcdefghijklmnopqrstuvwxyz'
splits = [(word[:i], word[i:]) for i in range(len(word) 1)]
deletes = [L R[1:] for L, R in splits if R]
transposes = [L R[1] R[0] R[2:] for L, R in splits if len(R) > 1]
replaces = [L c R[1:] for L, R in splits for c in letters]
inserts = [L c R for L, R in splits for c in letters]
return set(deletes transposes replaces inserts)
這個集合可能非常大。一個長度為 n 的單詞，有 n 個刪除編輯，n?1 個置換編輯，26n 個替換編輯，26(n 1) 的插入編輯，總共 54n 25 個簡單編輯（其中存在重復(fù)）。例如： >>>len(edits1('something'))
442
然而，如果我們限制單詞為已知( known，譯者：即存在于 WORDS 字典中的單詞)，那么這個單詞集合將顯著縮?。?/p> def known(words):
''''words'中出現(xiàn)在 WORDS 集合的元素子集'''
return set(w for w in words if w in WORDS)
>>>known(edits1('something'))
['something', 'soothing']
我們也需要考慮經(jīng)過二次編輯得到的單詞（譯者：'二次編輯'即編輯距離為 2，此處作者巧妙運(yùn)用遞歸思想，將函數(shù) edits1 返回集合里的每個元素再次經(jīng)過 edits1 處理即可得到），這個集合更大，但仍然只有很少一部分是已知單詞： def edits2(word):
'''與'word'的編輯距離為 2 的全部結(jié)果'''
return (e2 for e1 in edits1(word) for e2 in edits1(e1))
>>> len(set(edits2('something'))
90902
>>> known(edits2('something'))
{'seething', 'smoothing', 'something', 'soothing'}
>>> known(edits2('somthing'))
{'loathing', 'nothing', 'scathing', 'seething', 'smoothing', 'something', 'soothing', 'sorting'}
我們稱 edits2(w) 結(jié)果中的每個單詞與 w 的距離為 2。 3.語言模型：我們通過統(tǒng)計一個百萬級詞條的文本 big.txt中各單詞出現(xiàn)的頻率來估計 P(w)，它的數(shù)據(jù)來源于 古騰堡項(xiàng)目中公共領(lǐng)域的書摘，以及 維基詞典中頻率最高的詞匯，還有 英國國家語料庫，函數(shù) words(text) 將文本分割為詞組，并統(tǒng)計每個詞出現(xiàn)的頻率保存在變量 WORDS 中， P 基于該統(tǒng)計評估每個詞的概率： def words(text):
return re.findall(r'w ', text.lower())
# 統(tǒng)計詞頻
WORDS = Counter(words(open('big.txt').read()))
def P(word, N=sum(WORDS.values())):
'''詞'word'的概率'''
return float(WORDS[word]) / N
可以看到，去重后有 32,192 個單詞，它們一共出現(xiàn) 1,115,504 次，'the'是出現(xiàn)頻率最高的單詞，共出現(xiàn) 79,808 次(約占 7%)，其他詞概率低一些。 >>> len(WORDS)
32192
>>> sum(WORDS.values())
1115504
>>> WORDS.most_common(10)
[('the', 79808),
('of', 40024),
('and', 38311),
('to', 28765),
('in', 22020),
('a', 21124),
('that', 12512),
('he', 12401),
('was', 11410),
('it', 10681),
('his', 10034),
('is', 9773),
('with', 9739),
('as', 8064),
('i', 7679),
('had', 7383),
('for', 6938),
('at', 6789),
('by', 6735),
('on', 6639)]
>>> max(WORDS, key=P)
'the'
>>> P('the')
0.07154434228832886
>>> P('outrivaled')
8.9645577245801e-07
>>> P('unmentioned')
0.0
4.錯誤模型：2007 年坐在機(jī)艙內(nèi)寫這個程序時，我沒有拼寫錯誤的相關(guān)數(shù)據(jù)，也沒有網(wǎng)絡(luò)連接(我知道這在今天可能難以想象)。沒有數(shù)據(jù)就不能構(gòu)建拼寫錯誤模型，因此我采用了一個捷徑，定義了這么一個簡單的、有缺陷的模型：認(rèn)定對所有已知詞距離為 1 的編輯必定比距離為 2 的編輯概率更高，且概率一定低于距離為 0 的單詞（即原單詞）。因此函數(shù) candidates(word) 的優(yōu)先級如下：
1. 原始單詞（如果已知），否則到 2。
2. 所有距離為 1 的單詞，如果為空到 3。
3. 所有距離為 2 的單詞，如果為空到 4。
4. 原始單詞，即使它不是已知單詞。 效果評估現(xiàn)在我們看看程序效果如何。下飛機(jī)后，我從牛津文本檔案庫下載了 Roger Mitton 的 伯克貝克拼寫錯誤語料庫，從中抽取了兩個錯誤修正測試集，前者在開發(fā)中作為參考，調(diào)整程序以適應(yīng)其結(jié)果；后者用于最終測試，因此我不能偷看，也無法在評估時修改程序。取兩個集合分別用于開發(fā)和測試是個好習(xí)慣，它讓我不至于自欺欺人地調(diào)整程序以適應(yīng)結(jié)果，然后覺得程序效果有提升。我還寫了單元測試： def unit_tests():
'''開發(fā)的單元測試'''
assert correction('speling') == 'spelling' # insert
assert correction('korrectud') == 'corrected' # replace 2
assert correction('bycycle') == 'bicycle' # replace
assert correction('inconvient') == 'inconvenient' # insert 2
assert correction('arrainged') == 'arranged' # delete
assert correction('peotry') =='poetry' # transpose
assert correction('peotryy') =='poetry' # transpose delete
assert correction('word') == 'word' # known
assert correction('quintessential') == 'quintessential' # unknown
assert words('This is a TEST.') == ['this', 'is', 'a', 'test']
assert Counter(words('This is a test. 123; A TEST this is.')) == (
Counter({'123': 1, 'a': 2, 'is': 2, 'test': 2, 'this': 2}))
assert len(WORDS) == 32192
assert sum(WORDS.values()) == 1115504
assert WORDS.most_common(10) == [
('the', 79808),
('of', 40024),
('and', 38311),
('to', 28765),
('in', 22020),
('a', 21124),
('that', 12512),
('he', 12401),
('was', 11410),
('it', 10681)]
assert WORDS['the'] == 79808
assert P('quintessential') == 0
assert 0.07 P('the') 0.08
return 'unit_tests pass'
def spelltest(tests, verbose=False):
'''對測試集合 1 中的(right, wrong) 詞條，運(yùn)行 correction(wrong) 并統(tǒng)計結(jié)果的正確性'''
import time
start = time.clock()
good, unknown = 0, 0
n = len(tests)
for right, wrong in tests:
w = correction(wrong)
good = (w == right)
if w != right:
unknown = (right not in WORDS)
if verbose:
print('correction({}) => {} ({}); expected {} ({})'
.format(wrong, w, WORDS[w], right, WORDS[right]))
dt = time.clock() - start
print('{:.0%} of {} correct ({:.0%} unknown) at {:.0f} words per second '
.format(good / n, n, unknown / n, n / dt))
def Testset(lines):
'''對測試集合 2 中的錯誤樣本，將'wrong1 wrong2'修正為 [('right', 'wrong1'), ('right', 'wrong2')]'''
return [(right, wrong)
for (right, wrongs) in (line.split(':') for line in lines)
for wrong in wrongs.split()]
print(unit_tests())
spelltest(Testset(open('spell-testset1.txt'))) # Development set
spelltest(Testset(open('spell-testset2.txt'))) # Final test set
結(jié)果如下： unit_tests pass
75% of 270 correct at 41 words per second
68% of 400 correct at 35 words per second
None
可以看到，開發(fā)部分的集合準(zhǔn)確率達(dá)到了 74%（處理速度是 41 詞/秒），而在最終的測試集中準(zhǔn)確率是 68%（31 詞/秒）。結(jié)論是：我達(dá)到了簡潔，開發(fā)時間短，運(yùn)行速度快這 3 個目的，但準(zhǔn)確性不太高。也許是我的測試集太復(fù)雜，又或是模型太簡單因故而不能達(dá)到 80%~90%的準(zhǔn)確率。 后續(xù)工作考慮一下我們?nèi)绾巫龅母谩?nbsp;
1. 語言模型 P(c)。在語言模型中我們能區(qū)分兩種類型的錯誤（譯者：known 詞和 unknown 詞，前者 2 次編輯詞集合存在元素 inWORDS，后者不存在），更為嚴(yán)重的是 unknow 詞，程序會直接返回該詞的原始結(jié)果。在開發(fā)集合中，有 15 個 unknown 詞，約占 5%，而測試集中有 43 個（11%）。以下我們給出部分 spelltest 的運(yùn)行結(jié)果： correction('transportibility') => 'transportibility'(0); expected 'transportability'(0)
correction('addresable') => 'addresable' (0); expected 'addressable' (0)
correction('auxillary') => 'axillary' (31); expected 'auxiliary' (0)
我將期望輸出與實(shí)際輸出分別打印出來，計數(shù)'0'表示目標(biāo)詞匯不在詞庫字典內(nèi)，因此我們無法糾錯。如果能收集更多數(shù)據(jù)，包括使用一些語法(例如在單詞后加入'ility'或是'able')，我們能構(gòu)建一個更好的語言模型。 處理 unknown 詞匯的另一種辦法是，允許 correction 結(jié)果中出現(xiàn)我們沒見過的詞匯。例如，如果輸入是'electroencephalographicallz'，較好的一種修正是將末尾的'z'替換成'y'，盡管'electroencephalographically'并不在詞庫里，我們可以基于詞成分，例如發(fā)音或后綴來實(shí)現(xiàn)此效果。一種更簡單的方法是基于字母序列：統(tǒng)計常見 2、3、4 個字母序列。 2. 錯誤模型 P(w|c)。目前為止我們的錯誤模型相當(dāng)簡陋：認(rèn)定編輯距離越短錯誤越小。這導(dǎo)致了許多問題，許多例子中應(yīng)該返回編輯距離為 2 的結(jié)果而不是距離為 1。如下所示： correction('reciet') => 'recite' (5); expected 'receipt' (14)
correction('adres') => 'acres' (37); expected 'address' (77)
correction('rember') => 'member' (51); expected 'remember' (162)
correction('juse') => 'just' (768); expected 'juice' (6)
correction('accesing') => 'acceding' (2); expected 'assessing' (1)
為何'adres'應(yīng)該被修正為'address'而非'acres'呢？直覺是從'd'到'dd'和從's'到'ss'的二次編輯很常見，應(yīng)該擁有更高的概率，而從'd'到'c'的簡單編輯概率很低。 顯然我們可以根據(jù)編輯開銷來改進(jìn)模型：根據(jù)直覺將疊詞的編輯開銷降低，或是改變元音字母。一種更好的做法是收集數(shù)據(jù)：收集拼寫錯誤的語料，并對照正確單詞統(tǒng)計增刪、替換操作的概率。想做好這些需要大量數(shù)據(jù)：例如給定窗口大小為 2 的兩個單詞，如果你想得到兩者間的全部修正概率，其可能的轉(zhuǎn)換有 266 種，超過 3000 萬詞匯。因此如果你想獲取每個單詞的幾個轉(zhuǎn)換實(shí)例，大約需 10 億條修正數(shù)據(jù)，如要保證質(zhì)量，大概需要 100 億之多。 注意到語言模型和錯誤模型存在聯(lián)系：目前如此簡陋（編輯距離為 1 的詞必定優(yōu)于編輯距離為 2 的詞）的錯誤模型給語言模型造成阻礙：我們不愿將相對冷僻的詞放入模型內(nèi)，因?yàn)槿绻@類詞恰好與輸入單詞的編輯距離為 1，它將被選中，即使存在一個編輯距離為 2 但很常見的詞。好的錯誤模型在添加冷僻詞時更富有侵略性，以下例子展示了冷僻詞出現(xiàn)在字典里的危害： correction('wonted') => 'wonted' (2); expected 'wanted' (214)
correction('planed') => 'planed' (2); expected 'planned' (16)
correction('forth') => 'forth' (83); expected 'fourth' (79)
correction('et') => 'et' (20); expected 'set' (325)
3. 修正集合 argmaxc。本程序會枚舉某單詞所有編劇距離 2 以內(nèi)的修正，在開發(fā)集的 270 個修正詞中只有 3 個編輯距離超過 2，然而在測試集合中，23/400 個編輯距離超過 2，它們是： purple perpul
curtains courtens
minutes muinets
successful sucssuful
hierarchy heiarky
profession preffeson
weighted wagted
inefficient ineffiect
availability avaiblity
thermawear thermawhere
nature natior
dissension desention
unnecessarily unessasarily
disappointing dissapoiting
acquaintances aquantences
thoughts thorts
criticism citisum
immediately imidatly
necessary necasery
necessary nessasary
necessary nessisary
unnecessary unessessay
night nite
minutes muiuets
assessing accesing
necessitates nessisitates
我們可以考慮擴(kuò)展一下模型，允許一些編輯距離為 3 的詞進(jìn)入修正集合。例如，允許元音之后插入元音，或元音間的替換，又或'c'和's'之間的替換。 4. 第四種（也可能是最佳）改進(jìn)方案為：將 correction 的文本窗口調(diào)大一些。當(dāng)前的 correction 只檢測單個詞，然而在許多情形下僅靠一個單詞很難做出判決。而假若這個單詞恰好出現(xiàn)在字典里，這種糾錯手段就更顯無力。例如： correction('where') => 'where' (123); expected 'were' (452)
correction('latter') => 'latter' (11); expected 'later' (116)
correction('advice') => 'advice' (64); expected 'advise' (20)
我們幾乎不可能知道 correction('where') 在某個語句內(nèi)應(yīng)該返回'were'，而在另一句返回'where'。但如果輸入語句是 correction('They where going')，我們很容易判定此處'where'應(yīng)該被糾錯為'were'。 要構(gòu)建一個能同時處理詞和上下文的模型需要大量數(shù)據(jù)。幸運(yùn)的是，Google 已經(jīng)公開了最長 5 個詞的全部序列 詞庫，該數(shù)據(jù)源于上千億的語料集。我相信要使拼寫糾錯準(zhǔn)確率達(dá)到 90%，必須依賴上下文輔助決策，關(guān)于這個以后我們再討論。 我們也可以決定以哪種方言進(jìn)行訓(xùn)練。以下糾正時產(chǎn)生的錯誤均源于英式和美式拼寫間的差異： correction('humor') => 'humor' (17); expected 'humour' (5)
correction('oranisation') => 'organisation' (8); expected 'organization' (43)
correction('oranised') => 'organised' (11); expected 'organized' (70)
5. 最后，我們可以改進(jìn)實(shí)現(xiàn)方法，使程序在不改變結(jié)果的情況下運(yùn)行速度更快。例如：將實(shí)現(xiàn)該程序的語言從解釋型語言換成編譯型語言；緩存糾錯結(jié)果從而不必重復(fù)糾錯。一句話：在進(jìn)行任何速度優(yōu)化前，先大致看看時間消耗情況再決定優(yōu)化方向。 閱讀材料Roger Mitton 關(guān)于拼寫檢測的 調(diào)研文章 Jurafsky 和 Martin 的教材中 拼寫檢測部分。 Manning 和 Schutze 在他們編撰的 Foundations of StatisticalNatural Language Processing 中很好的講述了統(tǒng)計語言模型, 但似乎沒有(至少目錄中沒有) 提及拼寫檢查。 aspell 項(xiàng)目中有大量有趣的材料，其中的一些 測試數(shù)據(jù)似乎比我使用的更好。 LinPipe 項(xiàng)目有一個 拼寫檢測教程
原文地址：How to Write a Spelling Corrector?
題圖：pexels，CC0 授權(quán)。
|
