检查和更正拼写错误的算法至少从Blair（1960）开始就有了。大多数早期算法都是基于关键相似度的，例如Soundex算法（Odell and Russell, 1922;Knuth,1973）。Damerau（1964）给出了一个基于词典的算法来进行拼写错误的检查；从此以后，大多数错误检查算法都是基于词典的。Damerau还提出了一种单一错误的更正算法。从Wagner and Fischer(1974)开始，大多数算法都依赖于动态规划。Kukich（1992）是一篇关于拼写错误检查和更正的综述文章。对于非OCR文本拼写错误，更正的概率算法流行得比较晚，例如Kashyap and Oommen(1983)和Kernighan et al.(1990)。

相比之下，光学字符识别领域中的概率算法发展得比较早；Bledsoe and Browning(1959）研制了用于OCR错拼更正的一种概率算法，这种算法使用一部大型词典，把单词中的每个字母的似然度相乘，计算出在词典中给定的每个单词和所观察字符序列之间的似然度。在这个意义上，Bledsoe和Browning已经预见到现代贝叶斯方法应该与语音识别相结合了。Shinghal and Toussaint(1979)以及Hull and Srihari(1982)使用二元语法的字母转移概率和Viterbi算法，在错误拼写的OCR输入中选择可能性最大的正确形式。

把动态规划应用于序列比较，就出现了Kruskal（1983）指出的“多重独立发现和发表的值得注意的历史现象”。

Kruskal等给出了这种算法在四个不同领域中独立发表的事例，如下所示：

根据语音和语言处理术语的标准用法，当把动态规划应用于任何种类的概率最大化问题时，使用Viterbi这个术语；对于非概率问题，经常使用动态规划这5个普通的术语。向前算法是从隐马尔可夫模型推导出来的，关于向前算法的历史将在第7章中进行总结性的介绍。Sankoff and Kruskal（1983）收集了不同领域中关于序列比较研究的理论和应用的探索情况。Formey（1973）是一篇综述文章，在信息和通信理论的背景下介绍了Viterbi算法的来龙去脉。

加权有限状态自动机是首先由Pereira et al.(1994)进行描述的，这种描述来自Booth and Thompson(1973)把有限状态转录机的工作和概率语言的工作结合起来的研究。

责任编辑：admin