原文地址：http://blog.csdn.net/deadspace/archive/2011/02/17/6190810.aspx
上個星期, 我的兩個朋友 Dean 和 Bill 分別告訴我說他們對 Google 的快速高質(zhì)量的拼寫檢查工具感到驚奇. 比如說在搜索的時候鍵入 [speling], 在不到 0.1 秒的時間內(nèi), Google 會返回: 你要找的是不是 [spelling]. (Yahoo! 和微軟也有類似的功能). 讓我感到有點奇怪的是我原想 Dean 和 Bill 這兩個很牛的工程師和數(shù)學(xué)家應(yīng)該對于使用統(tǒng)計語言模型構(gòu)建拼寫檢查器有職業(yè)的敏感. 但是他們似乎沒有這個想法. 我后來想了想, 他們的確沒什么理由很熟悉統(tǒng)計語言模型. 不是他們的知識有問題, 而是我預(yù)想的本來就是不對的.

我覺得, 如果對這方面的工作做個解釋, 他們和其他人肯定會受益. 然而像Google 的那樣工業(yè)強度的拼寫檢查器的全部細節(jié)只會讓人感到迷惑而不是受到啟迪. 前幾天我乘飛機回家的時候, 順便寫了幾十行程序, 作為一個玩具性質(zhì)的拼寫檢查器. 這個拼寫檢查器大約1 秒能處理10 多個單詞, 并且達到 80% -90% 的準確率. 下面就是我的代碼, 用Python 2.5 寫成, 一共21 行, 是一個功能完備的拼寫檢查器.

import re, collections

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 model

NWORDS = train( words( file( 'big.txt' ). read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'

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

def known_edits2( word):
    return set( e2 for e1 in edits1( word) for e2 in edits1( e1) if e2 in NWORDS)

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])

這段代碼定義了一個函數(shù)叫 correct , 它以一個單詞作為輸入?yún)?shù), 返回最可能的拼寫建議結(jié)果. 比如說:

>>> correct( 'speling' )
'spelling'
>>> correct( 'korrecter' )
'corrector'

拼寫檢查器的原理, 一些簡單的概率知識

我簡單的介紹一下它的工作原理. 給定一個單詞, 我們的任務(wù)是選擇和它最相似的拼寫正確的單詞. ( 如果這個單詞本身拼寫就是正確的, 那么最相近的就是它自己啦). 當然, 不可能絕對的找到相近的單詞, 比如說給定 lates 這個單詞, 它應(yīng)該別更正為 late 呢還是 latest 呢? 這些困難指示我們, 需要使用概率論, 而不是基于規(guī)則的判斷. 我們說, 給定一個詞 w, 在所有正確的拼寫詞中, 我們想要找一個正確的詞 c, 使得對于 w 的條件概率最大, 也就是說:

argmaxc P(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 接著我們訓(xùn)練一個概率模型, 別被這個術(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 model

NWORDS = train( words( file( 'big.txt' ). read()))

實際上, NWORDS[w] 存儲了單詞 w 在語料中出現(xiàn)了多少次. 不過一個問題是要是遇到我們從來沒有過見過的新詞怎么辦. 假如說一個詞拼寫完全正確, 但是語料庫中沒有包含這個詞, 從而這個詞也永遠不會出現(xiàn)在訓(xù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)中.

效果

現(xiàn)在我們看看算法效果怎么樣. 在飛機上我嘗試了好幾個例子, 效果還行. 飛機著陸后, 我從牛津文本檔案庫 (Oxford Text Archive) 下載了 Roger Mitton 的 Birkbeck 拼寫錯誤語料庫 . 從這個庫中, 我取出了兩個集合, 作為我要做拼寫檢查的目標. 第一個集合用來作為在開發(fā)中作為參考, 第二個作為最后的結(jié)果測試. 也就是說, 我程序完成之前不參考它, 而把程序在其上的測試結(jié)果作為最后的效果. 用兩個集合一個訓(xùn)練一個對照是一種良好的實踐, 至少這樣可以避免我通過對特定數(shù)據(jù)集合進行特殊調(diào)整從而自欺欺人. 這里我給出了一個測試的例子和一個運行測試的例子. 實際的完整測試例子和程序可以參見 spell.py .

代碼下載：
本文來自CSDN博客，轉(zhuǎn)載請標明出處：http://blog.csdn.net/deadspace/archive/2011/02/17/6190810.aspx