拼寫(xiě)更正有很多算法，我們將重點(diǎn)研究貝葉斯算法，因?yàn)檫@種算法具有普遍性，本文只重點(diǎn)討論非詞拼寫(xiě)錯(cuò)誤。

Kernighan et al.(1990)首先提出把噪聲信道方法應(yīng)用于拼寫(xiě)更正，所用的correct程序把UNIX spell 程序拒絕的單詞生成潛在地可能正確的單詞表，并按式1排序，從中挑選出序號(hào)最高的單詞作為真正正確的單詞。

式1

讓我們以Kernighan et al. (1990) 的錯(cuò)拼單詞acress為例，將其使用的算法走一遍。這個(gè)算法分為兩步：第一步是提出候選更正表（proposing candidate correction）,第二步是對(duì)候選進(jìn)行打分(scoring the candidate )。

為了提出候選更正表，Kernighan等簡(jiǎn)單地假設(shè)：正確單詞與錯(cuò)拼單詞的差別只表現(xiàn)為插入、脫落、替代和換位這四種方式中的一種。Damerau(1964）的結(jié)果說(shuō)明，盡管這個(gè)假設(shè)可能漏掉某些更正，但它可以對(duì)付在人的打字文本中的大多數(shù)拼寫(xiě)錯(cuò)誤。這個(gè)候選單詞表可以從錯(cuò)拼單詞生成，而把在單詞中引起的任何一個(gè)單獨(dú)的轉(zhuǎn)換方式應(yīng)用于一個(gè)大型的聯(lián)機(jī)詞典就可以得到錯(cuò)拼單詞（typo）。把所有的轉(zhuǎn)換方式應(yīng)用于acress，就可以得到圖2中的候選單詞表。

式2

算法的第二步是使用式2來(lái)給候選更正打分。令t表示錯(cuò)拼單詞（typo），c表示候選更正集合C上的元素c。這樣，最佳的更正為式3

式3

圖2 

錯(cuò)拼詞acress的候選更正表以及產(chǎn)生錯(cuò)誤的轉(zhuǎn)換方式（Kernighan et al.,1990）,“-”表示零字母正如在式1中一樣，我們?cè)谑?中省略了分母，因?yàn)殄e(cuò)拼詞為t，所以對(duì)于所有的c，t的概率P(t)是一個(gè)常數(shù)。每個(gè)更正的先驗(yàn)概率P(c)，可以根據(jù)單詞c在某個(gè)語(yǔ)料庫(kù)中出現(xiàn)的頻繁程度次數(shù)來(lái)計(jì)算。然后，用所有單詞的總出現(xiàn)次數(shù)來(lái)歸一化（normalizing）這個(gè)頻繁程度次數(shù)。所以，一個(gè)更正單詞c的概率就等于c的出現(xiàn)次數(shù)除以語(yǔ)料庫(kù)中的詞數(shù)N。零次數(shù)可能會(huì)引起問(wèn)題，所以我們給所有出現(xiàn)次數(shù)都加0.5。這種做法稱(chēng)為“平滑”（smoothing）。注意，在式4中不能只用單詞總數(shù)N來(lái)除，因?yàn)槲覀儗?duì)每個(gè)更正單詞的出現(xiàn)次數(shù)都加了0.5，所以也要給詞匯中的單詞V加0.5。