假設 a = {a-z, A-Z, ...} 是英語所有可能構成單詞的字母集合, a* 為由這個字母表所構成的任意有限長度的字符串集合。 其中所有有效的單詞構成的集合D是a*的壹個子集。而noise channel 是指從目的詞(即字典)與實際接收到的字符串x所構成的矩陣。
對於所捕獲到的,存在拼寫錯誤的字符串x, 目標是在字典中找到壹個詞w,使這壹情況出現的概率最大。 即:
由於用戶實際想拼寫的單詞是不確定的,因此需要生成壹個修正候選列表(candidate corrections),這個列表基於兩個規則:
因此, noisy channel 實際上可以理解為,用戶所輸入的壹個錯誤的字符串,經過怎樣的變換過程可以得到若幹個正確的單詞。變換的過程越多,相當於channel越長, 而找候選列表的過程也就是找channel最短的過程。
最我輯距離(minimum edit distance)是指從壹個string到另壹個string所需的最我輯步驟,包括:插入、刪除、替換。而采用這三種編輯手段計算所得的距離又稱為 Levenshtein distance 。這壹距離將所有操作的cost都記為1.
但嚴格來說,替換這壹操作等於先刪除再插入。因此這壹操作的cost可當成是2(更接近實際操作的cost)。 此外,對於 Damerau–Levenshtein distance ,這壹距離還新增了transposition of two adjacent characters 這壹操作。
統計概率的計算方法如下:
首先對錯誤統計的方式:
顯然,用戶想輸入across的概率最大,這樣候選詞列表就有了排序和過濾的依據(大概率的排在前面,概率過低的可以不顯示)。另壹方面,P(word) 也可以使用bigram,這樣就與上下文取得了聯系,能更好的預測用戶想要輸入的單詞。
有25%-40%的錯誤屬於 real-word error
這壹部分是language model與noisy channel model的結合。假設用戶輸入的所有單詞都沒有non-word error
舉個例子,用戶輸入 "two of thew":
僅考慮 two off thew, two of the, too of thew 的概率,取最大值。
Peter Norvig’s list of errors
Wikipedia’s list of common misspelllings
GNU Aspell
Hunspell
How to Write a Spelling Corrector