原理介紹：
簡單的介紹一下它的工作原理. 給定一個單詞, 我們的任務(wù)是選擇和它最相似的拼寫正確的單詞. (如果這個單詞本身拼寫就是正確的, 那么最相近的就是它自己啦). 當然, 不可能絕對的找到相近的單詞, 比如說給定 lates 這個單詞, 它應(yīng)該別更正為 late 呢 還是 latest 呢? 這些困難指示我們, 需要使用概率論, 而不是基于規(guī)則的判斷. 我們說, 給定一個詞 w, 在所有正確的拼寫詞中, 我們想要找一個正確的詞 c, 使得對于 w 的條件概率最大, 也就是說:
argmaxcP(c|w)按照 貝葉斯理論 上面的式子等價于:
argmaxc P(w|c) P(c) / P(w)因為用戶可以輸錯任何詞, 因此對于任何 c 來講, 出現(xiàn) w 的概率 P(w) 都是一樣的, 從而我們在上式中忽略它, 寫成:
argmaxc P(w|c) P(c)這個式子有三個部分, 從右到左, 分別是:
1. P(c), 文章中出現(xiàn)一個正確拼寫詞 c 的概率, 也就是說, 在英語文章中, c 出現(xiàn)的概率有多大呢? 因為這個概率完全由英語這種語言決定, 我們稱之為做語言模型. 好比說, 英語中出現(xiàn) the 的概率 P('the') 就相對高, 而出現(xiàn) P('zxzxzxzyy') 的概率接近0(假設(shè)后者也是一個詞的話).2. P(w|c), 在用戶想鍵入 c 的情況下敲成 w 的概率. 因為這個是代表用戶會以多大的概率把 c 敲錯成 w, 因此這個被稱為誤 差模型.3. argmaxc, 用來枚舉所有可能的 c 并且選取概率最大的, 因為我們有理由相信, 一個(正確的)單詞出現(xiàn)的頻率高, 用戶又容易把它敲成另一個錯誤的單詞, 那么, 那個敲錯的單詞應(yīng)該被更正為這個正確的.為什么把最簡單的一個 P(c|w) 變成兩項復(fù)雜的式子來計算? 答案是本質(zhì)上 P(c|w) 就是和這兩項同時相關(guān)的, 因此拆成兩項反而容易處理. 舉個例子, 比如一個單詞 thew 拼錯了. 看上去 thaw 應(yīng)該是正確的, 因為就是把 a 打成 e 了. 然而, 也有可能用戶想要的是 the, 因為 the 是英語中常見的一個詞, 并且很有可能打字時候手不小心從 e 滑到 w 了. 因此, 在這種情況下, 我們想要計算 P(c|w), 就必須同時考慮 c 出現(xiàn)的概率和從 c 到 w 的概率. 把一項拆成兩項反而讓這個問題更加容易更加清晰.
現(xiàn)在, 讓我們看看程序究竟是怎么一回事. 首先是計算 P(c), 我們可以讀入一個巨大的文本文件, big.txt, 這個里面大約有幾百萬個詞(相當于是語料庫了). 這個文件是由Gutenberg 計劃中可以獲取的一些書, Wiktionary 和 British National Corpus 語料庫構(gòu)成。
然后, 我們利用一個叫 Words 的函數(shù)把語料中的單詞全部抽取出來, 轉(zhuǎn)成小寫, 并且去除單詞中間的特殊符號. 這樣, 單詞就會成為字母序列, don’t 就變成 don 和 t 了.1 接著我們訓練一個概率模型, 別被這個術(shù)語嚇倒, 實際上就是數(shù)一數(shù)每個單詞出現(xiàn)幾次. 在 train 函數(shù)中, 我們就做這個事情。
def words(text): return re.findall('[a-z]+', text.lower()) def train(features): model = collections.defaultdict(lambda: 1) for f in features: model[f] += 1 return modelNWORDS = train(words(file('big.txt').read()))實際上, NWORDS[w] 存儲了單詞 w 在語料中出現(xiàn)了多少次. 不過一個問題是要是遇到我們從來沒有過見過的新詞怎么辦. 假如說一個詞拼寫完全正確, 但是語料庫中沒有包含這個詞, 從而這個詞也永遠不會出現(xiàn)在訓練集中. 于是, 我們就要返回出現(xiàn)這個詞的概率是0. 這個情況不太妙, 因為概率為0這個代表了這個事件絕對不可能發(fā)生, 而在我們的概率模型中, 我們期望用一個很小的概率來代表這種情況. 實際上處理這個問題有很多成型的標準方法, 我們選取一個最簡單的方法: 從來沒有過見過的新詞一律假設(shè)出現(xiàn)過一次. 這個過程一般成為”平滑化”, 因為我們把概率分布為0的設(shè)置為一個小的概率值. 在語言實現(xiàn)上, 我們可以使用Python collention 包中的 defaultdict 類, 這個類和 python 標準的 dict (其他語言中可能稱之為 hash 表) 一樣, 唯一的不同就是可以給任意的鍵設(shè)置一個默認值, 在我們的例子中, 我們使用一個匿名的 lambda:1 函數(shù), 設(shè)置默認值為 1.
然后的問題是: 給定一個單詞 w, 怎么能夠枚舉所有可能的正確的拼寫呢? 實際上前人已經(jīng)研究得很充分了, 這個就是一個編輯距離的概 念. 這兩個詞之間的編輯距離 定義為使用了幾次插入(在詞中插入一個單字母), 刪除(刪除一個單字母), 交換(交換相鄰兩個字母), 替換(把一個字母換成另一個)的操作從一個詞變到另一個詞. 下面這個函數(shù)可以返回所有與單詞 w 編輯距離為 1 的集合.
def edits1(word): n = len(word) return set([word[0:i]+word[i+1:] for i in range(n)] + # deletion [word[0:i]+word[i+1]+word[i]+word[i+2:] for i in range(n-1)] + # transposition [word[0:i]+c+word[i+1:] for i in range(n) for c in alphabet] + # alteration [word[0:i]+c+word[i:] for i in range(n+1) for c in alphabet]) # insertion顯然, 這個集合很大. 對于一個長度為 n 的單詞, 可能有n種刪除, n-1中對換, 26n 種 (譯注: 實際上是 25n 種)替換 和 26(n+1) 種插入 (譯注: 實際上比這個小, 因為在一個字母前后再插入這個字母構(gòu)成的詞是等價的). 這樣的話, 一共就是 54n + 25 中情況 (當中還有一點重復(fù)). 比如說, 和 something 這個單詞的編輯距離為1 的詞按照這個算來是 511 個, 而實際上是 494 個.
一般講拼寫檢查的文獻宣稱大約80-95%的拼寫錯誤都是介于編譯距離 1 以內(nèi). 然而下面我們看到, 當我對于一個有270個拼寫錯誤的語料做實驗的時候, 我發(fā)現(xiàn)只有76%的拼寫錯誤是屬于編輯距離為1的集合. 或許是我選取的例子比典型的例子難處理一點吧. 不管怎樣, 我覺得這個結(jié)果不夠好, 因此我開始考慮編輯距離為 2 的那些單詞了. 這個事情很簡單, 遞歸的來看, 就是把 edit1 函數(shù)再作用在 edit1 函數(shù)的返回集合的每一個元素上就行了. 因此, 我們定義函數(shù) edit2:
def edits2(word): return set(e2 for e1 in edits1(word) for e2 in edits1(e1)) 這個語句寫起來很簡單, 實際上背后是很龐大的計算量: 與 something 編輯距離為2的單詞居然達到了 114,324 個. 不過編輯距離放寬到2以后, 我們基本上就能覆蓋所有的情況了, 在270個樣例中, 只有3個的編輯距離大于2. 當然我們可以做一些小小的優(yōu)化: 在這些編輯距離小于2的詞中間, 只把那些正確的詞作為候選詞. 我們?nèi)匀豢紤]所有的可能性, 但是不需要構(gòu)建一個很大的集合, 因此, 我們構(gòu)建一個函數(shù)叫做 known_edits2, 這個函數(shù)只返回那些正確的并且與 w 編輯距離小于2 的詞的集合:
def known_edits2(word): return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)現(xiàn)在, 在剛才的 something 例子中, known_edits2(‘something’) 只能返回 3 個單詞: ‘smoothing’, ‘something’ 和 ‘soothing’, 而實際上所有編輯距離為 1 或者 2 的詞一共有 114,324 個. 這個優(yōu)化大約把速度提高了 10%.
最后剩下的就是誤差模型部分 P(w|c) 了. 這個也是當時難住我的部分. 當時我在飛機上, 沒有網(wǎng)絡(luò), 也就沒有數(shù)據(jù)用來構(gòu)建一個拼寫錯誤模型. 不過我有一些常識性的知識: 把一個元音拼成另一個的概率要大于輔音 (因為人常常把 hello 打成 hallo 這樣); 把單詞的第一個字母拼錯的概率會相對小, 等等. 但是我并沒有具體的數(shù)字去支撐這些證據(jù). 因此, 我選擇了一個簡單的方法: 編輯距離為1的正確單詞比編輯距離為2的優(yōu)先級高, 而編輯距離為0的正確單詞優(yōu)先級比編輯距離為1的高. 因此, 用代碼寫出來就是:
(譯注: 此處作者使用了Python語言的一個巧妙性質(zhì): 短路表達式. 在下面的代碼中, 如果known(set)非空, candidate 就會選取這個集合, 而不繼續(xù)計算后面的; 因此, 通過Python語言的短路表達式, 作者很簡單的實現(xiàn)了優(yōu)先級)
def known(words): return set(w for w in words if w in NWORDS)def correct(word): candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word] return max(candidates, key=lambda w: NWORDS[w])correct 函數(shù)從一個候選集合中選取最大概率的. 實際上, 就是選取有最大 P(c) 值的那個. 所有的 P(c) 值都存儲在 NWORDS 結(jié)構(gòu)中.
從牛津文本檔案庫 (Oxford Text Archive)下載了 Roger Mitton 的 Birkbeck 拼寫錯誤語料庫.注意讀取里面的說明文檔. 從這個庫中, 我取出了兩個集合, 作為我要做拼寫檢查的目標. 第一個集合用來作為在開發(fā)中作為參考, 第二個作為最后的結(jié)果測試. 也就是說, 我程序完成之前不參考它, 而把程序在其上的測試結(jié)果作為最后的效果. 用兩個集合一個訓練一個對照是一種良好的實踐, 至少這樣可以避免我通過對特定數(shù)據(jù)集合進行特殊調(diào)整從而自欺欺人. 這里我給出了一個測試的例子和一個運行測試的例子. 實際的完整測試例子和程序可以參見 spell.py.
代碼：
# -*- coding: utf-8 -*-__author__ = 'jason'import reimport collectionsfrom collections import Counter'''mytext = "i dont' t"a = re.findall('/w+', mytext.lower())PRint a'''def words(text): return re.findall(r'/w+', text.lower())def train(features): model = collections.defaultdict(lambda: 1) #使用Python collention 包中的 defaultdict 類, #這個類和 python 標準的 dict (其他語言中可能稱之為 hash 表) 一樣, #唯一的不同就是可以給任意的鍵設(shè)置一個默認值, 在我們的例子中, 我們使用一個匿名的 lambda:1 函數(shù), 設(shè)置默認值為 1. for f in features: model[f] += 1 return modelWORDS = Counter(words(open('big.txt').read()))#相當于是訓練# WORDS = train(words(file('big.txt').read()))# print WORDS['hello']# NWORDS[w] 存儲了單詞 w 在語料中出現(xiàn)了多少次# print 'temp stop'# NWORDS = train(words(file('big.txt').read()))#相當于是訓練def P(word, N=sum(WORDS.values())): "Probability of `word`." return WORDS[word] / N#correct函數(shù)從一個候選集合中選取最大概率的。實際上, 就是選取有最大 P(c) 值的那個。所有的 P(c) 值都存儲在 NWORDS 結(jié)構(gòu)中.def correction(word):#它以一個單詞作為輸入?yún)?shù), 返回最可能的拼寫建議結(jié)果 "Most probable spelling correction for word." return max(candidates(word), key=P)#在下面的代碼中,通過Python語言的短路表達式實現(xiàn)。 如果known(set)非空, candidate 就會選取這個集合, 而不繼續(xù)計算后面的; 因此,def candidates(word): "Generate possible spelling corrections for word." return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])#傳入的是一個words集合def known(words): "The subset of `words` that appear in the dictionary of WORDS." # print words return set(w for w in words if w in WORDS)#只返回那些正確的并且與 w 編輯距離小于2 的詞的集合:def known_edits2(word): return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in WORDS)#返回所有與單詞 w 編輯距離為 1 的集合.def edits1(word): "All edits that are one edit away from `word`." 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 if R for c in letters] inserts = [L + c + R for L, R in splits for c in letters] return set(deletes + transposes + replaces + inserts)#遞歸的來看, 就是把 edit1 函數(shù)再作用在 edit1 函數(shù)的返回集合的每一個元素上就行了#生成器方式def edits2(word): "All edits that are two edits away from `word`." return (e2 for e1 in edits1(word) for e2 in edits1(e1))#正常寫法def editsV2(word): e2 = [] for e1 in edits1(word): temp2 = edits1(e1) for temp in temp2: e2.append(temp) # print e2 return e2def Testset(lines): "Parse 'right: wrong1 wrong2' lines into [('right', 'wrong1'), ('right', 'wrong2')] pairs." return [(right, wrong) for (right, wrongs) in (line.split(':') for line in lines) for wrong in wrongs.split()]'''tests1 = { 'access': 'acess', 'accessing': 'accesing', 'accommodation': 'accomodation acommodation acomodation', 'account': 'acount', ...}tests2 = {'forbidden': 'forbiden', 'decisions': 'deciscions descisions', 'supposedly': 'supposidly', 'embellishing': 'embelishing', ...}'''def unit_tests(): 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): "Run correction(wrong) on all (right, wrong) pairs; report results." import time start = time.clock() good, unknown = 0, 0 n = len(tests) for right, wrong in tests: w1 = correction(wrong) # print("right=%s,wrong=%s,correct=%s" % (right, wrong, w1)) good += (w1 == right) # print(good) if w1 != right: unknown += (right not in WORDS) if verbose: print('correction({}) => {} ({}); expected {} ({})' .format(wrong, w1, WORDS[w1], right, WORDS[right])) dt = time.clock() - start print("result=%.2f" % (good*1.0 / n)) print('{:.0%} of {} correct ({:.0%} unknown) at {:.0f} words per second ' .format(good*1.0 / n, n, unknown / n, n / dt))def spelltestV2(tests, verbose=False): "Run correction(wrong) on all (right, wrong) pairs; report results." import time print tests start = time.clock() good, unknown = 0, 0 n = len(tests) for right, wrong in tests: w = correction(wrong) print "right=%s,wrong=%s,correction=%s" % (right, wrong, w) 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*1.0 / n, n, unknown / n, n / dt))w = correction("youll")print(correction('korrectud'))print(len(edits1('somthing')))print(known(edits1('somthing')))print(len(set(edits2('something'))))#和原文不同？？是因為數(shù)據(jù)發(fā)生了變化嗎？？print(correction('contenpted'))# print spelltest(tests1)# print spelltest(tests2) ## only do this after everything is debugged# print(unit_tests())spelltest(Testset(open('spell-testset1.txt'))) # Development setspelltest(Testset(open('spell-testset2.txt'))) # Final test setprint "process end!"運行結(jié)果如下： 
參考資料：
參考： https://www.zybuluo.com/mdeditor?url=https://www.zybuluo.com/static/editor/md-help.markdown https://www.zybuluo.com/codeep/note/163962#cmd-markdown-公式指導手冊 http://norvig.com/spell-correct.html http://blog.csdn.net/nirendao/article/details/50640139
