一個簡單的拼寫檢查器

原作者python代碼：

讀完整篇文章，感歎數學的美妙之外，也很喜歡類似這樣的文章，将一個問題的原理講清楚，再配上一些代碼執行個體做說明，從小見大，從淺入深，對人很有啟發。

這裡簡單的介紹下基于貝葉斯原理的拼寫檢查原理，再給出一個java版和C#版的實作。

拼寫檢查器的原理：給定一個單詞，選擇和它最相似的拼寫正确的單詞，需要使用機率論，而不是基于規則的判斷。給定一個詞 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 并且選取機率最大的, 因為我們有理由相信, 一個(正确的)單詞出現的頻率高, 使用者又容易把它敲成另一個錯誤的單詞, 那麼, 那個敲錯的單詞應該被更正為這個正确的.

最終計算的就是argmaxc P(w|c) P(c)，在原文中，以“編輯距離”的大小來确定求最大機率的優先級： 編輯距離為1的正确單詞比編輯距離為2的優先級高, 而編輯距離為0的正确單詞優先級比編輯距離為1的高。

java版實作：

C#版實作：

兩個版本的實作都參考了網上其他人的代碼，略有修改。

參考：

http://norvig.com/spell-correct.html

http://blog.youxu.info/spell-correct.html

    本文轉自阿凡盧部落格園部落格，原文連結：http://www.cnblogs.com/luxiaoxun/p/4099567.html，如需轉載請自行聯系原作者