一个简单的拼写检查器

原作者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，如需转载请自行联系原作者