拼写纠错概述

拼写错误介绍

在输入过程中，会存在拼写错误。拼写错误分为两类：

非单词拼写错误（non-word spelling error），即需要纠错的单词不在现有词典中，如把success 输错成succest 。
实单词拼写错误（real word spelling error），即需要纠错的单词存在现有词典中，如把there 输错成three 。

拼写错误一般由字母增删改、字母调换顺序等错误造成。在手机输入中，由于键盘小，手指大(fat fingure problem)而造成多、错、漏输入等情况。另一方面，由于发音相同或相似，容易造成实单词拼写错误。在汉语中表现为n、l不分，f、h不分，前后鼻音不分，平翘舌音不分等。

拼写纠错通用框架

拼写纠错一般分为三大步：

拼写错误检测（检测）
纠错候选生成（召回）
纠错候选排序（排序）

对于非单词拼写错误，可以通过字典进行检测。如果待纠错词不在字典中，那么这个词是需要纠错的。而对于实单词错误，无法通过字典形式检测。

正确单词和待纠错单词通常有着相似的字符序列。所以使用编辑距离来产生纠错候选。对待纠错单词，通过变换可以得到编辑距离为$n$ 的单词候选，判断新单词候选是否在字典中，若在则成为带纠错单词的纠错候选，添加到候选集合$C$ 中。$n$ 通常取1-2 。

最后，如何排序上一步生成的纠错候选。已知用户错误拼写记为$x$ ，第$i$ 个纠错候选单词为$w_i$ ，那么$p(w_i|x)$ 为$w_i$错输成$x$ 的概率，作为各个$w_i$ 的权重。对于同一个$x$ ，$p(w_i|x)$ 越大， $w_i$ 越有可能是$x$ 的正确单词。所以有：

\begin{aligned} \hat{w}=\arg\max_{w \in C}p(x|w)p(w) \end{aligned}

噪声信道模型(Noisy Channel Model)

根据贝叶斯公式：

\begin{aligned} p(w|x) = \frac{p(x|w) * p(w)}{p(x)} \end{aligned}

对于所有的纠错候选词$w$ ，$x$ 是一样的。所以$p(x)$ 可以去掉。得：

\begin{aligned} p(w|x) = p(x|w) * p(w) \end{aligned}

$p(x|w)$ 为$w$ 错输成$x$ 的概率，亦称作似然或者$w$ 转化成$x$ 的信道模型。$p(w)$ 为纠错候选的先验概率，从语料中统计得到，p(w) 可以是unigram 、bigram 或者trigram 。

影响$p(x|w)$ 的因素有很多。一般我们转化为字符错误类型。错误类型分为：增、删、改以及交换（Damerau-Levenshtein)。通过统计字符四种错误类型的混淆矩阵来近似$p(x|w)$ 。举个例子：$p(acress|across)$ 可以使用大语料中字符o 被e 替换的概率$p(e|o)$ 代替。

实单词拼写错误

实单词拼写错误依然遵循通用框架的后两步。首先，通过编辑距离召回候选，然后根据先验概率和信道噪声模型进行排序。在召回候选时，一般编辑距离小于等于1，这里和非单词错误不一样，需要纠错单词本身也是候选词之一。信道噪声模型首先要考虑需要纠错的单词其实是没有错误，即$p(w|w)$ 的概率$\alpha$ 会根据不同任务设定不同的值。通常为$.95$。那么，剩下的候选词分摊$1-\alpha$ 。

\begin{aligned} p(x|w) = \begin{cases} \alpha & \text{if } x=w \\ \frac{1-\alpha}{\left | C(x) \right |} & \text{if } x\subset C(x) \\ 0 & \text{otherwise } \end{cases} \end{aligned}

除了使用均匀分布，更精确的做法是：按照字符混淆矩阵的概率分配。先验概率$p(w)$ 依然采用语言模型，bigram 或者trigram。

改进点

不再假设一句话只有一处错误。对每个单词进行检查。如果仅使用简单的纠错模型，会造成很多误纠错。特别是不常见的单词。
- 使用不纠错白名单
- 使用$logP(w|x) - log(x|x) > \theta$ 代替$logP(w|x) - log(x|x) > 0$
- 使用额外分类器决定是否纠错是否可靠
使用更大的词表，特别是在互联网场景下。
改进纠错模型：使用加权方式平衡似然和先验概率。
$\begin{aligned} \hat{w}=\arg\max_{w \in C}p(x|w){p(w)}^{\lambda} \end{aligned}$
对于实单词拼写错误中的固定错误形式，考虑监督算法

参考资料：

Speech and Language Processing