姓名：唐來賓? 學號：17101223417
轉載http://mp.weixin.qq.com/s/Czn9YiP06wOEcnO8dtjPWQ
【嵌牛導讀】拼寫自動糾錯能力芒澜，例如輸入”speling”汁尺，Google會立即顯示”spelling”的檢索結果。用correction(w)函數將試圖選出對于詞w最有可能的拼寫糾正單詞娇妓，概率學上我們是無法預知應該選擇哪一個的（例如，”lates”應該被糾正為”late”還是”latest”或”latters”…辫塌？）漏策。對于給定的原始詞w，我們試圖在所有可能的候選集合中臼氨，找出一個概率最大的修正結果c掺喻。
【嵌牛鼻子】糾錯分析，智能檢索
【嵌牛提問】如何快速的對輸入內容進行分析檢錯储矩？
【嵌牛正文】2007年的某個星期感耙，我的兩個朋友(Dean和Bill)分別向我傳達了他們對Google的拼寫自動糾錯能力的贊嘆。例如輸入”speling”持隧，Google會立即顯示”spelling”的檢索結果即硼。我原以為這兩位才智卓越的工程師、數學家屡拨，會對其工作原理有準確的推測只酥，事實上他們沒有。后來我意識到洁仗，他們怎么會對離自身專業(yè)領域如此遠的東西認知清晰呢层皱？
我覺得他們還有其他人，也許能從拼寫糾錯原理的解釋中獲益赠潦。工業(yè)級的完整拼寫糾錯相當復雜(詳細參見[1]和[2])，在橫貫大陸的航空旅途中草冈，我用約半頁代碼寫了一個迷你拼寫糾錯器她奥，其性能已經達到對句子以10詞/秒的速度處理，且糾錯準確率達到80%~90%怎棱。
代碼如下：
# coding:utf-8
importre
fromcollectionsimportCounter
defwords(text):
returnre.findall(r'w+',text.lower())
# 統(tǒng)計詞頻
WORDS=Counter(words(open('big.txt').read()))
defP(word,N=sum(WORDS.values())):
"""詞'word'的概率"""
returnfloat(WORDS[word])/N
defcorrection(word):
"""最有可能的糾正候選詞"""
returnmax(candidates(word),key=P)
defcandidates(word):
"""生成拼寫糾正詞的候選集合"""
return(known([word])orknown(edits1(word))orknown(edits2(word))or[word])
defknown(words):
"""'words'中出現(xiàn)在WORDS集合的元素子集"""
returnset(wforwinwordsifwinWORDS)
defedits1(word):
"""與'word'的編輯距離為1的全部結果"""
letters='abcdefghijklmnopqrstuvwxyz'
splits=[(word[:i],word[i:])foriinrange(len(word)+1)]
deletes=[L+R[1:]forL,RinsplitsifR]
transposes=[L+R[1]+R[0]+R[2:]forL,Rinsplitsiflen(R)>1]
replaces=[L+c+R[1:]forL,Rinsplitsforcinletters]
inserts=[L+c+RforL,Rinsplitsforcinletters]
returnset(deletes+transposes+replaces+inserts)
defedits2(word):
"""與'word'的編輯距離為2的全部結果"""
return(e2fore1inedits1(word)fore2inedits1(e1))
函數correction(word)返回一個最有可能的糾錯還原單詞：
>>>correction('speling')
'spelling'
>>>correction('korrectud')
'corrected'
它是如何工作的：概率理論
調用correction(w)函數將試圖選出對于詞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在英語文本中出現(xiàn)的概率厚掷。例如：在英語文本出現(xiàn)的單詞中弟灼，約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”的優(yōu)點在于它只對原詞做了細小的改變：將’e’換成’a’苔可。而另一方面，”the”似乎是一個更常見的詞袋狞，盡管增加’w’似乎變化更大焚辅，可能性更小，也許是打字者在敲’e’后手滑呢苟鸯？問題的核心在于：為了計算P(c|w)我們必須同時考慮c出現(xiàn)的概率同蜻，以及從c變成w的可能性。因此顯式地分為兩部分早处，思路上會更清晰湾蔓。
它是如何工作的：Python部分
該程序的4個部分：
選擇機制：在Python中，帶key的max()函數即可實現(xiàn)argmax的功能砌梆。
候選模型：先介紹一個新概念：對一個單詞的簡單編輯是指：刪除(移除一個字母)默责、置換(單詞內兩字母互換)、替換(單詞內一個字母改變)咸包、插入(增加一個字母)桃序。函數edits1(word)返回一個單詞的所有簡單編輯（譯者：稱其編輯距離為1）的集合，不考慮編輯后是否是合法單詞:
defedits1(word):
"""與'word'的編輯距離為1的全部結果"""
letters='abcdefghijklmnopqrstuvwxyz'
splits=[(word[:i],word[i:])foriinrange(len(word)+1)]
deletes=[L+R[1:]forL,RinsplitsifR]
transposes=[L+R[1]+R[0]+R[2:]forL,Rinsplitsiflen(R)>1]
replaces=[L+c+R[1:]forL,Rinsplitsforcinletters]
inserts=[L+c+RforL,Rinsplitsforcinletters]
returnset(deletes+transposes+replaces+inserts)
這個集合可能非常大烂瘫。一個長度為n的單詞媒熊，有n個刪除編輯，n?1個置換編輯坟比，26n個替換編輯芦鳍，26(n+1)的插入編輯，總共54n+25個簡單編輯（其中存在重復）温算。例如：
>>>len(edits1('something'))
442
然而怜校，如果我們限制單詞為已知(known，譯者：即存在于WORDS字典中的單詞)注竿，那么這個單詞集合將顯著縮星炎隆：
defknown(words):
"""'words'中出現(xiàn)在WORDS集合的元素子集"""
returnset(wforwinwordsifwinWORDS)
>>>known(edits1('something'))
['something','soothing']
我們也需要考慮經過二次編輯得到的單詞（譯者：“二次編輯”即編輯距離為2魂贬，此處作者巧妙運用遞歸思想，將函數edits1返回集合里的每個元素再次經過edits1處理即可得到）裙顽，這個集合更大付燥，但仍然只有很少一部分是已知單詞：
defedits2(word):
"""與'word'的編輯距離為2的全部結果"""
return(e2fore1inedits1(word)fore2inedits1(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)結果中的每個單詞與w的距離為2。
3.語言模型：我們通過統(tǒng)計一個百萬級詞條的文本big.txt中各單詞出現(xiàn)的頻率來估計P(w)愈犹，它的數據來源于古騰堡項目中公共領域的書摘键科，以及維基詞典中頻率最高的詞匯，還有英國國家語料庫漩怎，函數words(text)將文本分割為詞組勋颖，并統(tǒng)計每個詞出現(xiàn)的頻率保存在變量WORDS中，P基于該統(tǒng)計評估每個詞的概率：
defwords(text):
returnre.findall(r'w+',text.lower())
# 統(tǒng)計詞頻
WORDS=Counter(words(open('big.txt').read()))
defP(word,N=sum(WORDS.values())):
"""詞'word'的概率"""
returnfloat(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年坐在機艙內寫這個程序時谈宛，我沒有拼寫錯誤的相關數據次哈，也沒有網絡連接(我知道這在今天可能難以想象)。沒有數據就不能構建拼寫錯誤模型吆录，因此我采用了一個捷徑窑滞，定義了這么一個簡單的、有缺陷的模型：認定對所有已知詞距離為1的編輯必定比距離為2的編輯概率更高恢筝，且概率一定低于距離為0的單詞（即原單詞）葛假。因此函數candidates(word)的優(yōu)先級如下：
原始單詞（如果已知），否則到2滋恬。
所有距離為1的單詞，如果為空到3抱究。
所有距離為2的單詞恢氯，如果為空到4。
原始單詞鼓寺，即使它不是已知單詞勋拟。
效果評估
現(xiàn)在我們看看程序效果如何。下飛機后妈候，我從牛津文本檔案庫下載了Roger Mitton的伯克貝克拼寫錯誤語料庫敢靡，從中抽取了兩個錯誤修正測試集，前者在開發(fā)中作為參考苦银，調整程序以適應其結果啸胧；后者用于最終測試赶站，因此我不能偷看，也無法在評估時修改程序纺念。取兩個集合分別用于開發(fā)和測試是個好習慣贝椿，它讓我不至于自欺欺人地調整程序以適應結果，然后覺得程序效果有提升陷谱。我還寫了單元測試：
defunit_tests():
"""開發(fā)的單元測試"""
assertcorrection('speling')=='spelling'# insert
assertcorrection('korrectud')=='corrected'# replace 2
assertcorrection('bycycle')=='bicycle'# replace
assertcorrection('inconvient')=='inconvenient'# insert 2
assertcorrection('arrainged')=='arranged'# delete
assertcorrection('peotry')=='poetry'# transpose
assertcorrection('peotryy')=='poetry'# transpose + delete
assertcorrection('word')=='word'# known
assertcorrection('quintessential')=='quintessential'# unknown
assertwords('This is a TEST.')==['this','is','a','test']
assertCounter(words('This is a test. 123; A TEST this is.'))==(
Counter({'123':1,'a':2,'is':2,'test':2,'this':2}))
assertlen(WORDS)==32192
assertsum(WORDS.values())==1115504
assertWORDS.most_common(10)==[
('the',79808),
('of',40024),
('and',38311),
('to',28765),
('in',22020),
('a',21124),
('that',12512),
('he',12401),
('was',11410),
('it',10681)]
assertWORDS['the']==79808
assertP('quintessential')==0
assert0.07
return'unit_tests pass'
defspelltest(tests,verbose=False):
"""對測試集合1中的(right, wrong)詞條烙博，運行correction(wrong)并統(tǒng)計結果的正確性"""
importtime
start=time.clock()
good,unknown=0,0
n=len(tests)
forright,wrongintests:
w=correction(wrong)
good+=(w==right)
ifw!=right:
unknown+=(rightnotinWORDS)
ifverbose:
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))
defTestset(lines):
"""對測試集合2中的錯誤樣本，將'wrong1 wrong2'修正為[('right', 'wrong1'), ('right', 'wrong2')]"""
return[(right,wrong)
for(right,wrongs)in(line.split(':')forlineinlines)
forwronginwrongs.split()]
print(unit_tests())
spelltest(Testset(open('spell-testset1.txt')))# Development set
spelltest(Testset(open('spell-testset2.txt')))# Final test set
結果如下：
unit_testspass
75%of270correctat41words persecond
68%of400correctat35words per second
None
可以看到烟逊，開發(fā)部分的集合準確率達到了74%（處理速度是41詞/秒）渣窜，而在最終的測試集中準確率是68%（31詞/秒）。結論是：我達到了簡潔宪躯，開發(fā)時間短乔宿，運行速度快這3個目的，但準確性不太高眷唉。也許是我的測試集太復雜予颤，又或是模型太簡單因故而不能達到80%~90%的準確率。
后續(xù)工作
考慮一下我們如何做的更好冬阳。
1. 語言模型P(c)蛤虐。在語言模型中我們能區(qū)分兩種類型的錯誤（譯者：known詞和unknown詞，前者2次編輯詞集合存在元素inWORDS肝陪，后者不存在）驳庭，更為嚴重的是unknow詞，程序會直接返回該詞的原始結果氯窍。在開發(fā)集合中饲常，有15個unknown詞，約占5%狼讨，而測試集中有43個（11%）贝淤。以下我們給出部分spelltest的運行結果：
correction('transportibility')=>'transportibility'(0);expected'transportability'(0)
correction('addresable')=>'addresable'(0);expected'addressable'(0)
correction('auxillary')=>'axillary'(31);expected'auxiliary'(0)
我將期望輸出與實際輸出分別打印出來，計數’0’表示目標詞匯不在詞庫字典內政供，因此我們無法糾錯播聪。如果能收集更多數據，包括使用一些語法(例如在單詞后加入”ility”或是”able”)布隔，我們能構建一個更好的語言模型离陶。
處理unknown詞匯的另一種辦法是，允許correction結果中出現(xiàn)我們沒見過的詞匯衅檀。例如招刨，如果輸入是”electroencephalographicallz”，較好的一種修正是將末尾的’z’替換成’y’哀军，盡管”electroencephalographically”并不在詞庫里沉眶，我們可以基于詞成分打却，例如發(fā)音或后綴來實現(xiàn)此效果。一種更簡單的方法是基于字母序列：統(tǒng)計常見2沦寂、3学密、4個字母序列。
2. 錯誤模型P(w|c)传藏。目前為止我們的錯誤模型相當簡陋：認定編輯距離越短錯誤越小腻暮。這導致了許多問題，許多例子中應該返回編輯距離為2的結果而不是距離為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”應該被修正為”address”而非”acres”呢哭靖？直覺是從’d’到”dd”和從’s’到”ss”的二次編輯很常見，應該擁有更高的概率侈离，而從’d’到’c’的簡單編輯概率很低试幽。
顯然我們可以根據編輯開銷來改進模型：根據直覺將疊詞的編輯開銷降低，或是改變元音字母卦碾。一種更好的做法是收集數據：收集拼寫錯誤的語料铺坞，并對照正確單詞統(tǒng)計增刪、替換操作的概率洲胖。想做好這些需要大量數據：例如給定窗口大小為2的兩個單詞济榨，如果你想得到兩者間的全部修正概率，其可能的轉換有266種绿映，超過3000萬詞匯擒滑。因此如果你想獲取每個單詞的幾個轉換實例，大約需10億條修正數據叉弦，如要保證質量丐一，大概需要100億之多。
注意到語言模型和錯誤模型存在聯(lián)系：目前如此簡陋（編輯距離為1的詞必定優(yōu)于編輯距離為2的詞）的錯誤模型給語言模型造成阻礙：我們不愿將相對冷僻的詞放入模型內淹冰，因為如果這類詞恰好與輸入單詞的編輯距離為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以內的修正疹鳄，在開發(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
necessitatesnessisitates
我們可以考慮擴展一下模型，允許一些編輯距離為3的詞進入修正集合禽最。例如腺怯，允許元音之后插入元音袱饭，或元音間的替換，又或’c’和’s’之間的替換呛占。
4. 第四種（也可能是最佳）改進方案為：將correction的文本窗口調大一些虑乖。當前的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')在某個語句內應該返回”were”帜篇，而在另一句返回”where”糙捺。但如果輸入語句是correction('They where going')，我們很容易判定此處”where”應該被糾錯為”were”笙隙。
要構建一個能同時處理詞和上下文的模型需要大量數據洪灯。幸運的是，Google已經公開了最長5個詞的全部序列詞庫竟痰，該數據源于上千億的語料集签钩。我相信要使拼寫糾錯準確率達到90%，必須依賴上下文輔助決策坏快，關于這個以后我們再討論铅檩。
我們也可以決定以哪種方言進行訓練。以下糾正時產生的錯誤均源于英式和美式拼寫間的差異：
correction('humor')=>'humor'(17);expected'humour'(5)
correction('oranisation')=>'organisation'(8);expected'organization'(43)
correction('oranised')=>'organised'(11);expected'organized'(70)
5. 最后假消，我們可以改進實現(xiàn)方法柠并，使程序在不改變結果的情況下運行速度更快。例如：將實現(xiàn)該程序的語言從解釋型語言換成編譯型語言富拗；緩存糾錯結果從而不必重復糾錯臼予。一句話：在進行任何速度優(yōu)化前，先大致看看時間消耗情況再決定優(yōu)化方向啃沪。
閱讀材料
Roger Mitton關于拼寫檢測的調研文章
Jurafsky 和 Martin的教材中拼寫檢測部分粘拾。
Manning 和 Schutze 在他們編撰的 Foundations of StatisticalNatural Language Processing 中很好的講述了統(tǒng)計語言模型, 但似乎沒有(至少目錄中沒有)提及拼寫檢查。
aspell 項目中有大量有趣的材料创千，其中的一些測試數據似乎比我使用的更好缰雇。
LinPipe 項目有一個拼寫檢測教程
