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

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

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

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

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

拼寫檢查器的原理, 一些簡(jiǎn)單的概率知識(shí)

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

argmaxc P(c |w )

按照 貝葉斯理論 上面的式子等價(jià)于:

argmaxc P(w |c ) P(c ) / P(w )

因?yàn)橛脩艨梢暂斿e(cuò)任何詞, 因此對(duì)于任何 c 來講, 出現(xiàn) w 的概率 P(w) 都是一樣的, 從而我們?cè)谏鲜街泻雎运? 寫成:

argmaxc P(w |c ) P(c )

這個(gè)式子有三個(gè)部分, 從右到左, 分別是:

1. P(c), 文章中出現(xiàn)一個(gè)正確拼寫詞 c 的概率, 也就是說, 在英語(yǔ)文章中, c 出現(xiàn)的概率有多大呢? 因?yàn)檫@個(gè)概率完全由英語(yǔ)這種語(yǔ)言決定, 我們稱之為做語(yǔ)言模型 . 好比說, 英語(yǔ)中出現(xiàn) the 的概率 P('the') 就相對(duì)高, 而出現(xiàn) P('zxzxzxzyy') 的概率接近0( 假設(shè)后者也是一個(gè)詞的話).

2. P(w|c), 在用戶想鍵入 c 的情況下敲成 w 的概率. 因?yàn)檫@個(gè)是代表用戶會(huì)以多大的概率把 c 敲錯(cuò)成 w, 因此這個(gè)被稱為誤差模型 .

3. argmaxc , 用來枚舉所有可能的 c 并且選取概率最大的, 因?yàn)槲覀冇欣碛上嘈? 一個(gè)( 正確的) 單詞出現(xiàn)的頻率高, 用戶又容易把它敲成另一個(gè)錯(cuò)誤的單詞, 那么, 那個(gè)敲錯(cuò)的單詞應(yīng)該被更正為這個(gè)正確的.

有人肯定要問, 你笨啊, 為什么把最簡(jiǎn)單的一個(gè) P(c |w ) 變成兩項(xiàng)復(fù)雜的式子來計(jì)算? 答案是本質(zhì)上 P(c|w) 就是和這兩項(xiàng)同時(shí)相關(guān)的, 因此拆成兩項(xiàng)反而容易處理. 舉個(gè)例子, 比如一個(gè)單詞 thew 拼錯(cuò)了. 看上去 thaw 應(yīng)該是正確的, 因?yàn)榫褪前?a 打成 e 了. 然而, 也有可能用戶想要的是 the, 因?yàn)?the 是英語(yǔ)中常見的一個(gè)詞, 并且很有可能打字時(shí)候手不小心從 e 滑到 w 了. 因此, 在這種情況下, 我們想要計(jì)算 P(c |w ), 就必須同時(shí)考慮 c 出現(xiàn)的概率和從 c 到 w 的概率. 把一項(xiàng)拆成兩項(xiàng)反而讓這個(gè)問題更加容易更加清晰.

現(xiàn)在, 讓我們看看程序究竟是怎么一回事. 首先是計(jì)算 P(c), 我們可以讀入一個(gè)巨大的文本文件, big.txt , 這個(gè)里面大約有幾百萬(wàn)個(gè)詞( 相當(dāng)于是語(yǔ)料庫(kù)了). 這個(gè)文件是由Gutenberg 計(jì)劃 中可以獲取的一些書, Wiktionary 和 British National Corpus 語(yǔ)料庫(kù)構(gòu)成. ( 當(dāng)時(shí)在飛機(jī)上我只有福爾摩斯全集, 我后來又加入了一些, 直到效果不再顯著提高為止).

然后, 我們利用一個(gè)叫 words 的函數(shù)把語(yǔ)料中的單詞全部抽取出來, 轉(zhuǎn)成小寫, 并且去除單詞中間的特殊符號(hào). 這樣, 單詞就會(huì)成為字母序列, don't 就變成 don 和 t 了.1 接著我們訓(xùn)練一個(gè)概率模型, 別被這個(gè)術(shù)語(yǔ)嚇倒, 實(shí)際上就是數(shù)一數(shù)每個(gè)單詞出現(xiàn)幾次. 在 train 函數(shù)中, 我們就做這個(gè)事情.

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

實(shí)際上, NWORDS[w] 存儲(chǔ)了單詞 w 在語(yǔ)料中出現(xiàn)了多少次. 不過一個(gè)問題是要是遇到我們從來沒有過見過的新詞怎么辦. 假如說一個(gè)詞拼寫完全正確, 但是語(yǔ)料庫(kù)中沒有包含這個(gè)詞, 從而這個(gè)詞也永遠(yuǎn)不會(huì)出現(xiàn)在訓(xùn)練集中. 于是, 我們就要返回出現(xiàn)這個(gè)詞的概率是0. 這個(gè)情況不太妙, 因?yàn)楦怕蕿? 這個(gè)代表了這個(gè)事件絕對(duì)不可能發(fā)生, 而在我們的概率模型中, 我們期望用一個(gè)很小的概率來代表這種情況. 實(shí)際上處理這個(gè)問題有很多成型的標(biāo)準(zhǔn)方法, 我們選取一個(gè)最簡(jiǎn)單的方法: 從來沒有過見過的新詞一律假設(shè)出現(xiàn)過一次. 這個(gè)過程一般成為” 平滑化”, 因?yàn)槲覀儼迅怕史植紴? 的設(shè)置為一個(gè)小的概率值. 在語(yǔ)言實(shí)現(xiàn)上, 我們可以使用Python collention 包中的 defaultdict 類, 這個(gè)類和 python 標(biāo)準(zhǔn)的 dict ( 其他語(yǔ)言中可能稱之為 hash 表) 一樣, 唯一的不同就是可以給任意的鍵設(shè)置一個(gè)默認(rèn)值, 在我們的例子中, 我們使用一個(gè)匿名的 lambda:1 函數(shù), 設(shè)置默認(rèn)值為 1.

然后的問題是: 給定一個(gè)單詞 w, 怎么能夠枚舉所有可能的正確的拼寫呢? 實(shí)際上前人已經(jīng)研究得很充分了, 這個(gè)就是一個(gè)編輯距離 的概念. 這兩個(gè)詞之間的編輯距離
定義為使用了幾次插入( 在詞中插入一個(gè)單字母), 刪除( 刪除一個(gè)單字母), 交換( 交換相鄰兩個(gè)字母), 替換( 把一個(gè)字母換成另一個(gè)) 的操作從一個(gè)詞變到另一個(gè)詞.
下面這個(gè)函數(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

顯然, 這個(gè)集合很大. 對(duì)于一個(gè)長(zhǎng)度為 n 的單詞, 可能有n 種刪除, n-1 中對(duì)換, 26n 種 ( 譯注: 實(shí)際上是 25n 種) 替換 和 26(n+1) 種插入 ( 譯注: 實(shí)際上比這個(gè)小, 因?yàn)樵谝粋€(gè)字母前后再插入這個(gè)字母構(gòu)成的詞是等價(jià)的). 這樣的話, 一共就是 54n + 25 中情況 ( 當(dāng)中還有一點(diǎn)重復(fù)). 比如說, 和 something 這個(gè)單詞的編輯距離為1 的詞按照這個(gè)算來是 511 個(gè), 而實(shí)際上是 494 個(gè).

一般講拼寫檢查的文獻(xiàn)宣稱大約80-95% 的拼寫錯(cuò)誤都是介于編譯距離 1 以內(nèi). 然而下面我們看到, 當(dāng)我對(duì)于一個(gè)有270 個(gè)拼寫錯(cuò)誤的語(yǔ)料做實(shí)驗(yàn)的時(shí)候, 我發(fā)現(xiàn)只有76% 的拼寫錯(cuò)誤是屬于編輯距離為1 的集合. 或許是我選取的例子比典型的例子難處理一點(diǎn)吧. 不管怎樣, 我覺得這個(gè)結(jié)果不夠好, 因此我開始考慮編輯距離為 2 的那些單詞了. 這個(gè)事情很簡(jiǎn)單, 遞歸的來看, 就是把 edit1 函數(shù)再作用在 edit1 函數(shù)的返回集合的每一個(gè)元素上就行了. 因此, 我們定義函數(shù) edit2:

def edits2( word):
    return set( e2 for e1 in edits1( word) for e2 in edits1( e1))

這個(gè)語(yǔ)句寫起來很簡(jiǎn)單, 實(shí)際上背后是很龐大的計(jì)算量: 與 something 編輯距離為2 的單詞居然達(dá)到了 114,324 個(gè). 不過編輯距離放寬到2 以后, 我們基本上就能覆蓋所有的情況了, 在270 個(gè)樣例中, 只有3 個(gè)的編輯距離大于2. 當(dāng)然我們可以做一些小小的優(yōu)化: 在這些編輯距離小于2 的詞中間, 只把那些正確的詞作為候選詞. 我們?nèi)匀豢紤]所有的可能性, 但是不需要構(gòu)建一個(gè)很大的集合, 因此, 我們構(gòu)建一個(gè)函數(shù)叫做 known_edits2 , 這個(gè)函數(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 個(gè)單詞: 'smoothing', 'something' 和 'soothing', 而實(shí)際上所有編輯距離為 1 或者 2 的詞一共有 114,324 個(gè). 這個(gè)優(yōu)化大約把速度提高了 10%.

最后剩下的就是誤差模型部分 P(w |c ) 了. 這個(gè)也是當(dāng)時(shí)難住我的部分. 當(dāng)時(shí)我在飛機(jī)上, 沒有網(wǎng)絡(luò), 也就沒有數(shù)據(jù)用來構(gòu)建一個(gè)拼寫錯(cuò)誤模型. 不過我有一些常識(shí)性的知識(shí): 把一個(gè)元音拼成另一個(gè)的概率要大于輔音 ( 因?yàn)槿顺３０?hello 打成 hallo 這樣); 把單詞的第一個(gè)字母拼錯(cuò)的概率會(huì)相對(duì)小, 等等. 但是我并沒有具體的數(shù)字去支撐這些證據(jù). 因此, 我選擇了一個(gè)簡(jiǎn)單的方法: 編輯距離為1 的正確單詞比編輯距離為2 的優(yōu)先級(jí)高, 而編輯距離為0 的正確單詞優(yōu)先級(jí)比編輯距離為1 的高. 因此, 用代碼寫出來就是:

( 譯注: 此處作者使用了Python 語(yǔ)言的一個(gè)巧妙性質(zhì): 短路表達(dá)式. 在下面的代碼中, 如果known(set) 非空, candidate 就會(huì)選取這個(gè)集合, 而不繼續(xù)計(jì)算后面的; 因此, 通過Python 語(yǔ)言的短路表達(dá)式, 作者很簡(jiǎn)單的實(shí)現(xiàn)了優(yōu)先級(jí))

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ù)從一個(gè)候選集合中選取最大概率的. 實(shí)際上, 就是選取有最大 P(c ) 值的那個(gè). 所有的 P(c) 值都存儲(chǔ)在 NWORDS 結(jié)構(gòu)中.

效果

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

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