本文翻译自 Peter Norvig 的 How to Write a Spelling Corrector
2007年的某一个星期，我的两位老朋友 (Dean 和 Bill) 不约而同地告诉我，他们觉得谷歌的拼写校正功能很棒。在搜索栏中输入 [speling] 之后谷歌会立即返回 你是不是要找: spelling。我原本以为 Dean 和 Bill，作为卓越的工程师和数学家，会对这个拼写校正过程的工作原理有着很好的直觉。然而他们并没有，想想也是，他们为什么要了解距离自己的专长领域十万八千里的东西呢？
如果我写一篇解释拼写校正原理的文章，我想他们二位，以及其他人，肯定能够从中获益。一个具备工业能力 (industrial-strength) 的拼写校正器的细节是相当复杂的 (你可以从这或者这来了解一二)。但是我想在一趟横贯大洲的飞机旅程中我能够用半页代码写出一个玩具拼写校正器，并让她达到80%甚至90%的准确率和每秒至少处理10个单词的速度。
代码如下：
1 | import re |
函数 correction(word) 返回一个可能性最大的拼写校正结果：
1 | correction('speling') |
原理：一些概率论
函数 correction(w) 返回错别字 $w$ 最有可能的拼写修正项。 没有方法能够让我们明确地知道哪个词才是完美的拼写修正项 (举个例子，”lates” 是应该被修正为 “late” 还是 “latest” 还是 “lattes” 还是 …?)，这意味着我们需要用到概率 (probabilities). 给定一个错别字 $w$，我们试图从它的所有可能的候选修正项中找到一个概率最高的修正项 $c$ 作为选中的修正项：
$argmax_{c \in candidates}P(c|w)$
根据贝叶斯定理，上式等价于：
$argmax_{c \in candidates} \frac{P(c)P(w|c)}{P(w)}$
因为 $P(w)$ 对于每个可能的候选修正项 $c$ 都是一样的，我们可以把它忽略，所以上式变为：
$argmax_{c \in candidates} P(c)P(w|c)$
这个表达式的4个部分为：
选择机制 (Selection Mechanism): $argmax$
我们选择拥有最高的组合概率 (combined probability) 的候选项。
候选模型 (Candidate Model): $c \in candidates$
候选模型告诉我们应该考虑哪些候选修正项。
语言模型 (Language Model): $P(c)$
$P(c)$ 表示 $c$ 作为一个单词在英语文本中出现的概率。举个例子，单词 “the” 在英语文本中的出现的频率大概是7%，那么 $P(the)=0.07$。
误差模型 (Error Model): $P(w|c)$
$P(w|c)$ 表示当作者想要打的字是 $c$ 却输入了错别字 $w$ 的概率。打个比方说，$P(teh|the)$ 比较高而 $P(theeexyz|the)$ 会很低。
可能很多人会有一个疑问：为什么把一个简单的表达式 $P(c|w)$ 替换成一个更加复杂的表达式，并且这个表达式还涉及了两个模型而不是一个？答案就是 $P(c|w)$ 已经结合了两个因素，并且将两者分开处理更加简单清晰。现在我们假定有拼写错误的单词 $w$=”thew” 和两个候选修正项 $c$=”the” 和 $c$=”thaw”，那么哪个候选项拥有更高的 $P(c|w)$ 呢？显然，”thaw” 看起来概率挺高的因为它跟错别字只有一个很小的改变，就是把 “e” 写成了 “a”。另一个单词，”the” 看起来概率也挺高因为 “the” 是一个非常常见的单词，尽管多写了一个 “w” 似乎是一个更大的、不太可能的改变，或许打字者在打 “e” 的时候手滑了呢 (在 QWERTY 键盘上 “w” 在 “e” 的左边，还是有可能手滑多按了一个 “w” 的)。重点在于为了估计 $P(c|w)$ 我们需要考虑 $c$ 的概率以及从 $c$ 改变到 $w$ 的概率，总之，在形式上将两个因素分开更加清晰。
原理：一些 Python
程序分为4个部分：
选择机制 (Selection Mechanism):
在 Python 中，在 max() 函数中设定参数 key 就可以做到 ‘argmax’。
候选模型 (Candidate Model):
首先提出一个新的概念：对一个单词的一次简单编辑操作包括删除一个字符 (deletion)，交换两个相邻的字符 (transposition)，将一个字符替换为另一个字符 (replacement)，插入一个字符 (insertion)。函数 edits1(word) 返回与单词 word 简单编辑距离为 1的所有字符串 (不管它是不是一个英语单词) 的集合。
1
2
3
4
5
6
7
8
9def edits1(word):
"All edits that are one edit away from `word`."
letters = 'abcdefghijklmnopqrstuvwxyz'
splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
deletes = [L + R[1:] for L, R in splits if R]
transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
replaces = [L + c + R[1:] for L, R in splits if R for c in letters]
inserts = [L + c + R for L, R in splits for c in letters]
return set(deletes + transposes + replaces + inserts)edits1(word) 返回的可能是一个很大的集合。对于一个长度为 $n$ 的单词，有 $n$ 种 deletion 可能，$n-1$ 种 transposition 可能，$26n$ 种 replacement 可能和 $26(n+1)$ 种 insertion 可能，总计 $54n+25$ 种组合 (其中可能有一小部分重复)。例如，
1
2len(edits1('somthing'))
442如果我们把单词限定为已知的单词 (known，在词表中的单词)，那么这个集合就会小很多：
1
2
3
4def known(words): return set(w for w in words if w in WORDS)
known(edits1('somthing'))
{'something', 'soothing'}我们也考虑了与错别字的简单编辑距离为2的候选项。这会生成一个相当大的候选项集合，但是往往其中只有一小部分是已知的单词：
1
2
3
4
5
6
7
8
9
10def edits2(word): return (e2 for e1 in edits1(word) for e2 in edits1(e1))
len(set(edits2('something'))
90902
known(edits2('something'))
{'seething', 'smoothing', 'something', 'soothing'}
known(edits2('somthing'))
{'loathing', 'nothing', 'scathing', 'seething', 'smoothing', 'something', 'soothing', 'sorting'}我们说 edits2(w) 的返回结果 (候选项集合中的“单词”) 与 w 的简单编辑距离为2。
语言模型 (Language Model):
我们可以通过统计每个单词在语料 (一个包含大约一百万单词的文本文件，big.txt) 中出现的次数，来估计这个单词的概率，$P(word)$。语料包含了来自 Project Gutenberg 的公共领域书籍摘要，Wiktionary 和 British National Corpus 中的高频词列表。函数 words() 将文本拆分为单词，变量 WORDS 维护了一个 Counter 来记录每个单词出现的频数，基于这个 Counter，$P$ 表示每个单词的概率：
1
2
3
4
5def words(text): return re.findall(r'\w+', text.lower())
WORDS = Counter(words(open('big.txt').read()))
def P(word, N=sum(WORDS.values())): return WORDS[word] / float(N)我们可以发现语料中有 32,192 个不同的单词，它们一共出现了 1,115,504 次，’the’ 是最常见的单词，出现了 79,808 次 (概率大约为 7%)，其他单词的概率相对低一些：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39len(WORDS)
32192
sum(WORDS.values())
1115504
WORDS.most_common(10)
[('the', 79808),
('of', 40024),
('and', 38311),
('to', 28765),
('in', 22020),
('a', 21124),
('that', 12512),
('he', 12401),
('was', 11410),
('it', 10681),
('his', 10034),
('is', 9773),
('with', 9739),
('as', 8064),
('i', 7679),
('had', 7383),
('for', 6938),
('at', 6789),
('by', 6735),
('on', 6639)]
max(WORDS, key=P)
'the'
P('the')
0.07154434228832886
P('outrivaled')
8.9645577245801e-07
P('unmentioned')
0.0误差模型 (Error Model):
当我开始写这个程序的时候，那是 2007 年的某一天我坐在飞机上，当时我没有拼写错误的数据也没有网络连接 (我知道这在如今难以想象)。没有数据我就无法建立一个很好的拼写误差模型，所以我走了一条捷径：我定义了一个有瑕疵的误差模型，她认为所有编辑距离为1的已知词是肯定比编辑距离为2的已知词概率更高的，但比编辑距离为0的单词概率低。所以我们能让函数 candidates(word) 根据下列优先级返回第一个非空候选单词列表：
- 原始单词，如果是已知的则返回；否则不返回
- 与错别字编辑距离为1的已知单词列表，如果列表非空则返回；否则不返回
- 与错别字编辑距离为2的已知单词列表，如果列表非空则返回；否则不返回
- 原始单词，即使它是未知的 (不在词表中)
接下来我们都不需要乘一个 $P(w|c)$ 因子，因为根据我们有瑕疵的误差模型 (用编辑距离来表征错别字基于候选项的概率)，每个候选项在其被选中的优先级会有相同的概率。这就有了：
1
2
3
4def correction(word): return max(candidates(word), key=P)
def candidates(word):
return known([word]) or known(edits1(word)) or known(edits2(word)) or [word]
评估
现在是时候来评估一下这个程序的性能了。在我的飞机降落后，我从 Oxford Text Archive 下载了 Roger Mitton 的 Birkbeck spelling error corpus。从中我抽取出了2个错别字校正 (corrention) 的测试集。第一个是发展集，意味着我在开发程序的过程中可以来查看该数据集中的内容。第二个是最终的测试集，意味着我不能查看其中的内容，更不能用它评估完之后修改我的程序。使用2个测试集是很好的做法；它让我不能自欺欺人地以为自己会比只使用一个特定的测试集来调试程序做得更好。我也写了一些单元测试：
1 | def unit_tests(): |
这个单元测试会输出：
1 | unit_tests pass |
所以在发展集上我们的模型有 75% 的准确率 (每秒处理 41 个单词)，在最终的测试集上有 68% 的准确率 (每秒处理 35 个单词)。总的来说，我在模型的简洁度、开发时间和处理速度上达到了我的目标，但是准确率欠佳。也许是我的测试集中包含了许多很难的例子，又或许是我的模型过于简单，导致无法达到 80% 甚至 90% 的准确率。
可改进的地方
让我们来思考一下如何做得更好。(我在一本书的单独章节和一个 Jupyter notebook 中进一步描述了这些思考)
$P(c)$，语言模型。
我们可以辨别出语言模型中的2个误差来源。未知单词带来的误差更加严重。在发展集中，有 15 个未知词，占 5%，在最终的测试集中，有 43 个未知词，占 11%。下面这几个例子展示了设定 verbose=True 的 spelltest 的输出：
1
2
3correction('transportibility') => 'transportibility' (0); expected 'transportability' (0)
correction('addresable') => 'addresable' (0); expected 'addressable' (0)
correction('auxillary') => 'axillary' (31); expected 'auxiliary' (0)在这个输出结果中显示了对 correction() 函数的调用和实际结果和预期结果 (括号中是单词的计数)。括号中为 0 表示目标单词并不存在于词表中，因此我们无法校正这个错别字。我们可以创造一个更好的语言模型，通过收集更多数据，也许可以使用一些英语词法 (morphology，比如在单词的结果加上 “ility” 或者 “able”)。
另一种处理未知单词的方法是允许 correction() 返回的结果是一个我们从未见过的单词。举个例子，假如输入是 “electroencephalographicallz”，一个好的校正可能会将最后的 “z” 改为 “y”，即使 “electroencephalographically” 并不在我们的词表中。我们可以利用基于单词组成的语言模型来实现这个方法。单词组成 (components) 可以基于音节或者后缀，但有种更简单的方法是将它基于字符的序列：通常 2-，3-，4-字符的序列。
$P(w|c)$，误差模型。
目前，误差模型还很简陋：编辑距离越小，误差越小。这导致了一些问题，就像下面的例子展示的那样。首先，有些情况下 correction() 应该返回与错别字的编辑距离为 2 的校正项，然而返回了编辑距离为 1 的校正项：
1
2
3
4
5correction('reciet') => 'recite' (5); expected 'receipt' (14)
correction('adres') => 'acres' (37); expected 'address' (77)
correction('rember') => 'member' (51); expected 'remember' (162)
correction('juse') => 'just' (768); expected 'juice' (6)
correction('accesing') => 'acceding' (2); expected 'assessing' (1)为什么 “adres” 应该被修正为 “address” 而不是 “acres” 呢？直觉上从 “d” 到 “dd” 和从 “s” 到 “ss” 的两次编辑应该是相当普遍的，并且概率挺高，而从 “d” 到 “c” 的单次编辑的概率相对低。
显然，我们可以使用一个更好的编辑成本 (cost of edits) 模型。凭借直觉我们可以给字符重复和将元音改变成另一个元音 (与任意字母改变相比) 赋予更低的成本，但是更好的办法似乎是收集数据：去获取一个拼写错误的语料库，并计算在给定周围的字符条件下错别字做出每个插入，删除或替换的概率。我们需要大量的数据来做到这一点。如果我们想看看一个字符变为另一个字符的情况，给定一个两边各有两个字符的窗口，那就是 $26^6$，超过 3 亿个字符。你应该会希望每个错别字有好几个例子，平均来说，我们需要至少十亿个字符的校正数据。可能至少有 100 亿字符更安全。
请注意语言模型和误差模型之间是有联系的。当前程序中的误差模型是如此简单 (所有编辑距离为 1 的单词排在任何编辑距离为 2 的单词之前) 以至于它妨碍了语言模型：我们担心给模型中添加冷门的单词，因为如果其中一个冷门的单词碰巧与输入的单词的编辑距离为 1，那么即使有一个非常常见的单词与输入词的编辑距离为 2 ，冷门词也会被选中。如果有一个更好的错误模型，我们可以更加理直气壮地往词典 (词表) 中添加冷门的单词。下面是一些例子展示了在词典中存在冷门的单词会伤害到我们：
1
2
3
4correction('wonted') => 'wonted' (2); expected 'wanted' (214)
correction('planed') => 'planed' (2); expected 'planned' (16)
correction('forth') => 'forth' (83); expected 'fourth' (79)
correction('et') => 'et' (20); expected 'set' (325)$argmax_c$，候选修正项的选择。
我们的程序枚举了所有与错别字的编辑距离在 2 以内的修正项。在发展集中，270 个正确单词中只有 3 个和错别字的编辑距离超过 2，但是在最终的测试集中，400 个正确单词中有 23 个。它们是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27purple perpul
curtains courtens
minutes muinets
successful sucssuful
hierarchy heiarky
profession preffeson
weighted wagted
inefficient ineffiect
availability avaiblity
thermawear thermawhere
nature natior
dissension desention
unnecessarily unessasarily
disappointing dissapoiting
acquaintances aquantences
thoughts thorts
criticism citisum
immediately imidatly
necessary necasery
necessary nessasary
necessary nessisary
unnecessary unessessay
night nite
minutes muiuets
assessing accesing
necessitates nessisitates我们应该考虑扩展一下模型，通过允许一定数量的候选修正项与错别字的编辑距离能达到 3。比如，只允许在一个元音旁插入另一个元音，或是将一个元音替换成另一个元音，或是替换相近的辅音，像 “c” -> “s”，这样可以处理几乎所有情况。
其实还有第四种方法 (也是最好的方法，下一篇文章中我补充的 N-grams 语言模型就属于这种方法) 来提升校正器的性能：改变 函数 correction() 的接口来考虑更多的上下文 (context)。到目前为止，correction() 一次只看一个单词 (unigram)。而很多时候光看一个单词是很难做出决定的 (决定这个单词是不是候选单词)。当一个单词出现在词表中，但是测试结果却说它应该被校正为另一个单词时，这种情况最为明显：
1
2
3correction('where') => 'where' (123); expected 'were' (452)
correction('latter') => 'latter' (11); expected 'later' (116)
correction('advice') => 'advice' (64); expected 'advise' (20)我们不太可能知道 correction(‘where’) 在一些情况下返回的是 “were”，或是在另外一些情况下保持 “where”。但假如查询是这样的，correction(‘They where going’) 那么 “where” 似乎更应该被修正为 “were”。
单词的上下文能够在错别字有多个不错的候选修正项时帮助我们挑选最合理的修正项。
考虑：
1
2
3
4
5
6correction('hown') => 'how' (1316); expected 'shown' (114)
correction('ther') => 'the' (81031); expected 'their' (3956)
correction('quies') => 'quiet' (119); expected 'queries' (1)
correction('natior') => 'nation' (170); expected 'nature' (171)
correction('thear') => 'their' (3956); expected 'there' (4973)
correction('carrers') => 'carriers' (7); expected 'careers' (2)为什么 ‘thear’ 被校正为 ‘there’ 而不是 ‘their’？通过单独的一个单词很难说出原因，但假如查询是 correction(‘There’s no there thear) 问题就变得清晰了起来。
为了构建一个能够一次考虑多个单词的模型，我们需要大量的数据。幸运的是，Google 发布了 database of word counts 适用于最长5个词的所有单词序列，该数据库是从一万亿个单词的语料库中训练出来的。
我相信一个能够达到 90% 准确率的拼写校正器需要用到错别字的上下文信息来帮助在候选修正项中做出选择。但我们把这个思路放到日后实现… (后面的章节中我描述的 N-grams 语言模型就考虑了错别字的上下文信息)
我们也可以考虑我们的模型到底是基于哪种方言训练。下列三个错误就是由美式英语和英式英语对同一个单词的拼法不同导致的 (我们的训练数据两者都有)：
1
2
3correction('humor') => 'humor' (17); expected 'humour' (5)
correction('oranisation') => 'organisation' (8); expected 'organization' (43)
correction('oranised') => 'organised' (11); expected 'organized' (70)最终，我们能够在不改变结果的条件下重构模型的实现来让它更快。我们可以用编译型语言 (compiled language) 实现模型而不是用解释型语言 (interpreted language)。我们可以把计算的结果缓存下来来避免重复计算。最后一个小小的建议：在尝试任何速度优化之前，仔细检查到底时间是消耗在哪了。
拓展阅读
- Roger Mitton 写了一篇关于拼写检查的调查文章。
- Jurafsky 和 Martin 在他们的文章 Speech and Language Processing 中很好地讲到了拼写校正。
- Manning 和 Schutze 在他们的文章 Foundations of Statistical Natural Language Processing 中很好的讲述了静态语言模型，但他们似乎没有涉及拼写检查 (至少在目录中)。
- 项目 aspell 中有许多有趣的材料，包括看起来比我现在用的更好的测试数据。
- 项目 LingPipe 有一个拼写检查教程。
以上均为翻译，“我”绝大部分指的是 Peter Norvig。
正如 Peter Norvig 在前文指出，当前的拼写校正器并没有考虑错别字的上下文，或者说它就是利用了一个 unigram (1-gram) 模型，候选修正项的概率取决于一个单词在语料库中的词频。从结果也可以看出，unigram 模型的效果并不是非常理想。
在下一篇文章 (N-grams 语言模型与拼写校正) 中我会介绍 NLP 中一个常见的语言模型：N-grams 模型，它可以使拼写校正器拥有感知上下文的能力，能够显著得提升错别字校正的准确率。在我随机生成的错别字测试集上，编辑距离加上 N-grams 模型的校正算法的准确率超过了 90%。
References
- How to Write a Spelling Corrector, Peter Norvig
