使用google的時候，如果你拼錯一個單詞，它會提醒你正确的拼法。
比如，你不小心輸入了seperate。
下面我們就來看看，怎麼利用貝葉斯推斷，實作"拼寫檢查"。其實很簡單，一小段代碼就夠了。
一、原理
使用者輸入了一個單詞。這時分成兩種情況：拼寫正确，或者拼寫不正确。我們把拼寫正确的情況記做c（代表correct），拼寫錯誤的情況記做w（代表wrong）。
所謂"拼寫檢查"，就是在發生w的情況下，試圖推斷出c。從機率論的角度看，就是已知w，然後在若幹個備選方案中，找出可能性最大的那個c，也就是求下面這個式子的最大值。
p(c|w)
根據貝葉斯定理：
p(c|w) = p(w|c) * p(c) / p(w)
對于所有備選的c來說，對應的都是同一個w，是以它們的p(w)是相同的，是以我們求的其實是
p(w|c) * p(c)
的最大值。
p(c)的含義是，某個正确的詞的出現"機率"，它可以用"頻率"代替。如果我們有一個足夠大的文本庫，那麼這個文本庫中每個單詞的出現頻率，就相當于它的發生機率。某個詞的出現頻率越高，p(c)就越大。
p(w|c)的含義是，在試圖拼寫c的情況下，出現拼寫錯誤w的機率。這需要統計資料的支援，但是為了簡化問題，我們假設兩個單詞在字形上越接近，就有越可能拼錯，p(w|c)就越大。舉例來說，相差一個字母的拼法，就比相差兩個字母的拼法，發生機率更高。你想拼寫單詞hello，那麼錯誤拼成hallo（相差一個字母）的可能性，就比拼成haallo高（相差兩個字母）。
是以，我們隻要找到與輸入單詞在字形上最相近的那些詞，再在其中挑出出現頻率最高的一個，就能實作 p(w|c) * p(c) 的最大值。
二、算法
最簡單的算法，隻需要四步就夠了。
第一步，建立一個足夠大的文本庫。
第二步，取出文本庫的每一個單詞，統計它們的出現頻率。
第三步，根據使用者輸入的單詞，得到其所有可能的拼寫相近的形式。
所謂"拼寫相近"，指的是兩個單詞之間的"編輯距離"（edit distance）不超過2。也就是說，兩個詞隻相差1到2個字母，隻通過----删除、交換、更改和插入----這四種操作中的一種，就可以讓一個詞變成另一個詞。
第四步，比較所有拼寫相近的詞在文本庫的出現頻率。頻率最高的那個詞，就是正确的拼法。
根據peter norvig的驗證，這種算法的精确度大約為60%-70%（10個拼寫錯誤能夠檢查出6個。）雖然不令人滿意，但是能夠接受。畢竟它足夠簡單，計算速度極快。（本文的最後部分，将詳細讨論這種算法的缺陷在哪裡。）
三、代碼
我們使用python語言，實作上一節的算法。
第二步，加載python的正則語言子產品（re）和collections子產品，後面要用到。
import re, collections
第三步，定義words()函數，用來取出文本庫的每一個詞。
def words(text): return re.findall('[a-z]+', text.lower())
lower()将所有詞都轉成小寫，避免因為大小寫不同，而被算作兩個詞。
第四步，定義一個train()函數，用來建立一個"字典"結構。文本庫的每一個詞，都是這個"字典"的鍵；它們所對應的值，就是這個詞在文本庫的出現頻率。
def train(features): model = collections.defaultdict(lambda: 1) for f in features: model[f] += 1 return model
collections.defaultdict(lambda: 1)的意思是，每一個詞的預設出現頻率為1。這是針對那些沒有出現在文本庫的詞。如果一個詞沒有在文本庫出現，我們并不能認定它就是一個不存在的詞，是以将每個詞出現的預設頻率設為1。以後每出現一次，頻率就增加1。
第五步，使用words()和train()函數，生成上一步的"詞頻字典"，放入變量nwords。
nwords = train(words(file('big.txt').read()))
第六步，定義edits1()函數，用來生成所有與輸入參數word的"編輯距離"為1的詞。
alphabet = 'abcdefghijklmnopqrstuvwxyz' def edits1(word): splits = [(word[:i], word[i:]) for i in range(len(word) + 1)] deletes = [a + b[1:] for a, b in splits if b] transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1] replaces = [a + c + b[1:] for a, b in splits for c in alphabet if b] inserts = [a + c + b for a, b in splits for c in alphabet] return set(deletes + transposes + replaces + inserts)
edit1()函數中的幾個變量的含義如下：
（1）splits：将word依次按照每一位分割成前後兩半。比如，'abc'會被分割成 [('', 'abc'), ('a', 'bc'), ('ab', 'c'), ('abc', '')] 。 （2）beletes：依次删除word的每一位後、所形成的所有新詞。比如，'abc'對應的deletes就是 ['bc', 'ac', 'ab'] 。 （3）transposes：依次交換word的鄰近兩位，所形成的所有新詞。比如，'abc'對應的transposes就是 ['bac', 'acb'] 。 （4）replaces：将word的每一位依次替換成其他25個字母，所形成的所有新詞。比如，'abc'對應的replaces就是 ['abc', 'bbc', 'cbc', ... , 'abx', ' aby', 'abz' ] ，一共包含78個詞（26 × 3）。 （5）inserts：在word的鄰近兩位之間依次插入一個字母，所形成的所有新詞。比如，'abc' 對應的inserts就是['aabc', 'babc', 'cabc', ..., 'abcx', 'abcy', 'abcz']，一共包含104個詞（26 × 4）。
最後，edit1()傳回deletes、transposes、replaces、inserts的合集，這就是與word"編輯距離"等于1的所有詞。對于一個n位的詞，會傳回54n+25個詞。
第七步，定義edit2()函數，用來生成所有與word的"編輯距離"為2的詞語。
def edits2(word): return set(e2 for e1 in edits1(word) for e2 in edits1(e1))
但是這樣的話，會傳回一個 (54n+25) * (54n+25) 的數組，實在是太大了。是以，我們将edit2()改為known_edits2()函數，将傳回的詞限定為在文本庫中出現過的詞。
def known_edits2(word): return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in nwords)
第八步，定義correct()函數，用來從所有備選的詞中，選出使用者最可能想要拼寫的詞。
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=nwords.get)
我們采用的規則為：
（1）如果word是文本庫現有的詞，說明該詞拼寫正确，直接傳回這個詞； （2）如果word不是現有的詞，則傳回"編輯距離"為1的詞之中，在文本庫出現頻率最高的那個詞； （3）如果"編輯距離"為1的詞，都不是文本庫現有的詞，則傳回"編輯距離"為2的詞中，出現頻率最高的那個詞； （4）如果上述三條規則，都無法得到結果，則直接傳回word。
使用方法如下：
>>> correct('speling') 'spelling' >>> correct('korrecter') 'corrector'
四、缺陷
我們使用的這種算法，有一些缺陷，如果投入生産環境，必須在這些方面加入改進。
（1）文本庫必須有很高的精确性，不能包含拼寫錯誤的詞。
如果使用者輸入一個錯誤的拼法，文本庫恰好包含了這種拼法，它就會被當成正确的拼法。
（2）對于不包含在文本庫中的新詞，沒有提出解決辦法。
如果使用者輸入一個新詞，這個詞不在文本庫之中，就會被當作錯誤的拼寫進行糾正。
（3）程式傳回的是"編輯距離"為1的詞，但某些情況下，正确的詞的"編輯距離"為2。
比如，使用者輸入reciet，會被糾正為recite（編輯距離為1）,但使用者真正想要輸入的詞是receipt（編輯距離為2）。也就是說，"編輯距離"越短越正确的規則，并非所有情況下都成立。
（4）有些常見拼寫錯誤的"編輯距離"大于2。
這樣的錯誤，程式無法發現。下面就是一些例子，每一行前面那個詞是正确的拼法，後面那個則是常見的錯誤拼法。
purple perpul curtains courtens minutes muinets successful sucssuful inefficient ineffiect availability avaiblity dissension desention unnecessarily unessasarily necessary nessasary unnecessary unessessay night nite assessing accesing necessitates nessisitates
（5）使用者輸入的詞的拼寫正确，但是其實想輸入的是另一個詞。
比如，使用者輸入是where，這個詞拼寫正确，程式不會糾正。但是，使用者真正想輸入的其實是were，不小心多打了一個h。
（6）程式傳回的是出現頻率最高的詞，但使用者真正想輸入的是另一個詞。
比如，使用者輸入ther，程式會傳回the，因為它的出現頻率最高。但是，使用者真正想輸入的其實是their，少打了一個i。也就是說，出現頻率最高的詞，不一定就是使用者想輸入的詞。
（7）某些詞有不同的拼法，程式無法辨識。
比如，英國英語和美國英語的拼法不一緻。英國使用者輸入'humur'，應該被糾正為'humour'；美國使用者輸入'humur'，應該被糾正為'humor'。但是，我們的程式會統一糾正為'humor'。
（完）