Norvig 拼写检查器

拼写检查器使用概率理论来确定应建议哪个词作为纠正。它会选择使条件概率 $P(c|w)$ 最大的候选词 $c$，其中 $w$ 是原始词。数学上可表示为：

$$\underset{c \ \in \ \text{candidates}} { \text{arg\ max}} \ P(c|w)$$

对于所有候选词，我们计算将词 $w$ 纠正为 $c$ 的概率。在对所有候选词进行计算后，返回具有最高概率的候选词 $c$。

如果我们应用贝叶斯定理（Bayes' Theorem），其表达式为：

$$P(A|B) = \frac{P(A)P(B|A)}{P(B)}$$

那么，我们可以将上述条件概率重写为：

$$\underset{c \ \in \ \text{candidates}} { \text{arg\ max}} \ P(c) P(w|c)$$

我们可以将这一过程分解为四个模型，并系统地分别编程实现，从而构建一个拼写检查器。

• 候选模型（Candidate model）：考虑作为正确拼写的合法候选词，即 $c \ \in \ \text{candidates}$

• 语言模型（Language model）：候选词 $c$ 在英文文本中出现的概率 $P(c)$。例如，“the”约占英文文本的 $7\%$，因此 $P(\text{the}) = 0.07$

• 错误模型（Error model）：当作者本意是 $c$ 时，在文本中实际输入为 $w$ 的概率 $P(w|c)$

• 选择机制（Selection mechanism）：选择使条件概率最大的候选词，即 $\text{arg\ max}$ 所对应的 $c$