贝叶斯推断及其互联网应用（三）拼写检查

贝叶斯推断及其互联网应用（三）拼写检查2014-10-20 阮一峰（这个系列的第一部分介绍了贝叶斯定理，第二部分介绍了如何过滤垃圾邮件，今天是第三部分。）

使用Google的时候，如果你拼错一个单词，它会提醒你正确的拼法。

比如，你不小心输入了seperate。

Google告诉你，这个词是不存在的，正确的拼法是separate。

这就叫做"拼写检查"（spelling corrector）。有好几种方法可以实现这个功能，Google使用的是基于贝叶斯推断的统计学方法。这种方法的特点就是快，很短的时间内处理大量文本，并且有很高的精确度（90%以上）。Google的研发总监Peter Norvig，写过一篇著名的文章，解释这种方法的原理。

下面我们就来看看，怎么利用贝叶斯推断，实现"拼写检查"。其实很简单，一小段代码就够了。

一、原理

用户输入了一个单词。这时分成两种情况：拼写正确，或者拼写不正确。我们把拼写正确的情况记做c（代表correct），拼写错误的情况记做w（代表wrong）。

所谓"拼写检查"，就是在发生w的情况下，试图推断出c。从概率论的角度看，就是已知w，然后在若干个备选方案中，找出可能性最大的那个c，也就是求下面这个式子的最大值。

P（c|w）

根据贝叶斯定理：

P（c|w） = P（w|c） * P（c） / P（w）

对于所有备选的c来说，对应的都是同一个w，所以它们的P（w）是相同的，因此我们求的其实是

P（w|c） * P（c）

的最大值。

P（c）的含义是，某个正确的词的出现"概率"，它可以用"频率"代替。如果我们有一个足够大的文本库，那么这个文本库中每个单词的出现频率，就相当于它的发生概率。某个词的出现频率越高，P（c）就越大。

P（w|c）的含义是，在试图拼写c的情况下，出现拼写错误w的概率。这需要统计数据的支持，但是为了简化问题，我们假设两个单词在字形上越接近，就有越可能拼错，P（w|C）就越大。举例来说，相差一个字母的拼法，就比相差两个字母的拼法，发生概率更高。你想拼写单词hello，那么错误拼成hallo（相差一个字母）的可能性，就比拼成haallo高（相差两个字母）。

所以，我们只要找到与输入单词在字形上最相近的那些词，再在其中挑出出现频率最高的一个，就能实现 P（w|c） * P（c）的最大值。

URL：http://www.bianceng.cn/Programming/sjjg/201410/46034.htm