檢查和更正拼寫錯誤的算法至少從Blair（1960）開始就有了。大多數(shù)早期算法都是基于關(guān)鍵相似度的，例如Soundex算法（Odell and Russell, 1922;Knuth,1973）。Damerau（1964）給出了一個基于詞典的算法來進行拼寫錯誤的檢查；從此以后，大多數(shù)錯誤檢查算法都是基于詞典的。Damerau還提出了一種單一錯誤的更正算法。從Wagner and Fischer(1974)開始，大多數(shù)算法都依賴于動態(tài)規(guī)劃。Kukich（1992）是一篇關(guān)于拼寫錯誤檢查和更正的綜述文章。對于非OCR文本拼寫錯誤，更正的概率算法流行得比較晚，例如Kashyap and Oommen(1983)和Kernighan et al.(1990)。

相比之下，光學(xué)字符識別領(lǐng)域中的概率算法發(fā)展得比較早；Bledsoe and Browning(1959）研制了用于OCR錯拼更正的一種概率算法，這種算法使用一部大型詞典，把單詞中的每個字母的似然度相乘，計算出在詞典中給定的每個單詞和所觀察字符序列之間的似然度。在這個意義上，Bledsoe和Browning已經(jīng)預(yù)見到現(xiàn)代貝葉斯方法應(yīng)該與語音識別相結(jié)合了。Shinghal and Toussaint(1979)以及Hull and Srihari(1982)使用二元語法的字母轉(zhuǎn)移概率和Viterbi算法，在錯誤拼寫的OCR輸入中選擇可能性最大的正確形式。

把動態(tài)規(guī)劃應(yīng)用于序列比較，就出現(xiàn)了Kruskal（1983）指出的“多重獨立發(fā)現(xiàn)和發(fā)表的值得注意的歷史現(xiàn)象”。

Kruskal等給出了這種算法在四個不同領(lǐng)域中獨立發(fā)表的事例，如下所示：

根據(jù)語音和語言處理術(shù)語的標(biāo)準(zhǔn)用法，當(dāng)把動態(tài)規(guī)劃應(yīng)用于任何種類的概率最大化問題時，使用Viterbi這個術(shù)語；對于非概率問題，經(jīng)常使用動態(tài)規(guī)劃這5個普通的術(shù)語。向前算法是從隱馬爾可夫模型推導(dǎo)出來的，關(guān)于向前算法的歷史將在第7章中進行總結(jié)性的介紹。Sankoff and Kruskal（1983）收集了不同領(lǐng)域中關(guān)于序列比較研究的理論和應(yīng)用的探索情況。Formey（1973）是一篇綜述文章，在信息和通信理論的背景下介紹了Viterbi算法的來龍去脈。

加權(quán)有限狀態(tài)自動機是首先由Pereira et al.(1994)進行描述的，這種描述來自Booth and Thompson(1973)把有限狀態(tài)轉(zhuǎn)錄機的工作和概率語言的工作結(jié)合起來的研究。

責(zé)任編輯：admin