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

我覺得, 如果對這方面的工作做個解釋, 他們和其他人肯定會受益. 然而像Google 的那樣工業強度的拼寫檢查器的全部細節只會讓人感到迷惑而不是受到啟迪. 前幾天我乘飛機回家的時候, 順便寫了幾十行程序, 作為一個玩具性質的拼寫檢查器. 這個拼寫檢查器大約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])

這段代碼定義了一個函數叫 correct , 它以一個單詞作為輸入參數, 返回最可能的拼寫建議結果. 比如說:

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

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

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

argmaxc P(c |w )

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

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

因為用戶可以輸錯任何詞, 因此對于任何 c 來講, 出現 w 的概率 P(w) 都是一樣的, 從而我們在上式中忽略它, 寫成:

argmaxc P(w |c ) P(c )

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

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

2. P(w|c), 在用戶想鍵入 c 的情況下敲成 w 的概率. 因為這個是代表用戶會以多大的概率把 c 敲錯成 w, 因此這個被稱為誤差模型 .

3. argmaxc , 用來枚舉所有可能的 c 并且選取概率最大的, 因為我們有理由相信, 一個( 正確的) 單詞出現的頻率高, 用戶又容易把它敲成另一個錯誤的單詞, 那么, 那個敲錯的單詞應該被更正為這個正確的.

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

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

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

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 在語料中出現了多少次. 不過一個問題是要是遇到我們從來沒有過見過的新詞怎么辦. 假如說一個詞拼寫完全正確, 但是語料庫中沒有包含這個詞, 從而這個詞也永遠不會出現在訓練集中. 于是, 我們就要返回出現這個詞的概率是0. 這個情況不太妙, 因為概率為0 這個代表了這個事件絕對不可能發生, 而在我們的概率模型中, 我們期望用一個很小的概率來代表這種情況. 實際上處理這個問題有很多成型的標準方法, 我們選取一個最簡單的方法: 從來沒有過見過的新詞一律假設出現過一次. 這個過程一般成為” 平滑化”, 因為我們把概率分布為0 的設置為一個小的概率值. 在語言實現上, 我們可以使用Python collention 包中的 defaultdict 類, 這個類和 python 標準的 dict ( 其他語言中可能稱之為 hash 表) 一樣, 唯一的不同就是可以給任意的鍵設置一個默認值, 在我們的例子中, 我們使用一個匿名的 lambda:1 函數, 設置默認值為 1.

然后的問題是: 給定一個單詞 w, 怎么能夠枚舉所有可能的正確的拼寫呢? 實際上前人已經研究得很充分了, 這個就是一個編輯距離 的概念. 這兩個詞之間的編輯距離
定義為使用了幾次插入( 在詞中插入一個單字母), 刪除( 刪除一個單字母), 交換( 交換相鄰兩個字母), 替換( 把一個字母換成另一個) 的操作從一個詞變到另一個詞.
下面這個函數可以返回所有與單詞 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) 種插入 ( 譯注: 實際上比這個小, 因為在一個字母前后再插入這個字母構成的詞是等價的). 這樣的話, 一共就是 54n + 25 中情況 ( 當中還有一點重復). 比如說, 和 something 這個單詞的編輯距離為1 的詞按照這個算來是 511 個, 而實際上是 494 個.

一般講拼寫檢查的文獻宣稱大約80-95% 的拼寫錯誤都是介于編譯距離 1 以內. 然而下面我們看到, 當我對于一個有270 個拼寫錯誤的語料做實驗的時候, 我發現只有76% 的拼寫錯誤是屬于編輯距離為1 的集合. 或許是我選取的例子比典型的例子難處理一點吧. 不管怎樣, 我覺得這個結果不夠好, 因此我開始考慮編輯距離為 2 的那些單詞了. 這個事情很簡單, 遞歸的來看, 就是把 edit1 函數再作用在 edit1 函數的返回集合的每一個元素上就行了. 因此, 我們定義函數 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. 當然我們可以做一些小小的優化: 在這些編輯距離小于2 的詞中間, 只把那些正確的詞作為候選詞. 我們仍然考慮所有的可能性, 但是不需要構建一個很大的集合, 因此, 我們構建一個函數叫做 known_edits2 , 這個函數只返回那些正確的并且與 w 編輯距離小于2 的詞的集合:

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

現在, 在剛才的 something 例子中, known_edits2('something') 只能返回 3 個單詞: 'smoothing', 'something' 和 'soothing', 而實際上所有編輯距離為 1 或者 2 的詞一共有 114,324 個. 這個優化大約把速度提高了 10%.

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

( 譯注: 此處作者使用了Python 語言的一個巧妙性質: 短路表達式. 在下面的代碼中, 如果known(set) 非空, candidate 就會選取這個集合, 而不繼續計算后面的; 因此, 通過Python 語言的短路表達式, 作者很簡單的實現了優先級)

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 函數從一個候選集合中選取最大概率的. 實際上, 就是選取有最大 P(c ) 值的那個. 所有的 P(c) 值都存儲在 NWORDS 結構中.

效果

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

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