2007年的某个星期，我的两个朋友(Dean和Bill)分别向我传达了他们对Google的拼写自动纠错能力的赞叹。例如输入”speling”，Google会立即显示”spelling”的检索结果。我原以为这两位才智卓越的工程师、数学家，会对其工作原理有准确的推测，事实上他们没有。后来我意识到，他们怎么会对离自身专业领域如此远的东西认知清晰呢？
我觉得他们还有其他人，也许能从拼写纠错原理的解释中获益。工业级的完整拼写纠错相当复杂(详细参见[1]和[2])，在横贯大陆的航空旅途中，我用约半页代码写了一个迷你拼写纠错器，其性能已经达到对句子以10词/秒的速度处理，且纠错准确率达到80%~90%。
代码如下：
|
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
39
40
41
42
43
44
45
46
47
|
# coding:utf-8
import re
from collections import Counter
def words(text):
return re.findall(r'w+', text.lower())
# 统计词频
WORDS = Counter(words(open('big.txt').read()))
def P(word, N=sum(WORDS.values())):
"""词'word'的概率"""
return float(WORDS[word]) / N
def correction(word):
"""最有可能的纠正候选词"""
return max(candidates(word), key=P)
def candidates(word):
"""生成拼写纠正词的候选集合"""
return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])
def known(words):
"""'words'中出现在WORDS集合的元素子集"""
return set(w for w in words if w in WORDS)
def edits1(word):
"""与'word'的编辑距离为1的全部结果"""
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 for c in letters]
inserts = [L + c + R for L, R in splits for c in letters]
return set(deletes + transposes + replaces + inserts)
def edits2(word):
"""与'word'的编辑距离为2的全部结果"""
return (e2 for e1 in edits1(word) for e2 in edits1(e1))
|
函数correction(word)返回一个最有可能的纠错还原单词：
|
1
2
3
4
|
>>>correction('speling')
'spelling'
>>>correction('korrectud')
'corrected'
|
它是如何工作的：概率理论
调用correction(w)函数将试图选出对于词w最有可能的拼写纠正单词，概率学上我们是无法预知应该选择哪一个的（例如，”lates”应该被纠正为”late”还是”latest”或”latters”…？）。对于给定的原始词w，我们试图在所有可能的候选集合中，找出一个概率最大的修正结果c。
$$argmax_c in candidatesP(c|w)$
根据贝叶斯原理，它等价于：
argmaxcincandidatesfracP(c)P(w|c)P(w)
由于对w的每个候选单词c，其P(w)均相等，因此剔除后公式如下：
argmaxcincandidatesP(c)P(w|c)
该式分为4个部分：
1.选择机制：argmax
选择候选集中概率最高的单词。
2.候选模型：cincandidates
有哪些候选单词可供考虑。
3.语言模型：P(c)
c在英语文本中出现的概率。例如：在英语文本出现的单词中，约7%是”the”，那么P(the)=0.07
4.错误模型：P(w|c)
当作者本意是c结果打成w的概率。例如:概率P(the|the)相当高，而P(theeexyz|the)将非常低。
一个显而易见的问题是：为什么将简单的表达P(c|w)引入两个模型使得其变得更复杂？答案是P(c|w)本身就是两个部分的合并，将二者分开能更明确地进行处理。考虑对错误拼写”thew”进行还原，两个候选单词分别是”the”和”thaw”，二者谁的P(c|w)更高呢？”thaw”的优点在于它只对原词做了细小的改变：将’e’换成’a’。而另一方面，”the”似乎是一个更常见的词，尽管增加’w’似乎变化更大，可能性更小，也许是打字者在敲’e’后手滑呢？问题的核心在于：为了计算P(c|w)我们必须同时考虑c出现的概率，以及从c变成w的可能性。因此显式地分为两部分，思路上会更清晰。
它是如何工作的：Python部分
该程序的4个部分：
1.选择机制：在Python中，带key的max()函数即可实现argmax的功能。
2.候选模型：先介绍一个新概念：对一个单词的简单编辑是指：删除(移除一个字母)、置换(单词内两字母互换)、替换(单词内一个字母改变)、插入(增加一个字母)。函数edits1(word)返回一个单词的所有简单编辑（译者：称其编辑距离为1）的集合，不考虑编辑后是否是合法单词:
|
1
2
3
4
5
6
7
8
9
|
def edits1(word):
"""与'word'的编辑距离为1的全部结果"""
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 for c in letters]
inserts = [L + c + R for L, R in splits for c in letters]
return set(deletes + transposes + replaces + inserts)
|
这个集合可能非常大。一个长度为n的单词，有n个删除编辑，n−1个置换编辑，26n个替换编辑，26(n+1)的插入编辑，总共54n+25个简单编辑（其中存在重复）。例如：
|
1
2
|
>>>len(edits1('something'))
442
|
然而，如果我们限制单词为已知(known，译者：即存在于WORDS字典中的单词)，那么这个单词集合将显著缩小：
|
1
2
3
4
5
6
|
def known(words):
"""'words'中出现在WORDS集合的元素子集"""
return set(w for w in words if w in WORDS)
>>>known(edits1('something'))
['something', 'soothing']
|
我们也需要考虑经过二次编辑得到的单词（译者：“二次编辑”即编辑距离为2，此处作者巧妙运用递归思想，将函数edits1返回集合里的每个元素再次经过edits1处理即可得到），这个集合更大，但仍然只有很少一部分是已知单词：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
def edits2(word):
"""与'word'的编辑距离为2的全部结果"""
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。
3.语言模型：我们通过统计一个百万级词条的文本big.txt中各单词出现的频率来估计P(w)，它的数据来源于古腾堡项目中公共领域的书摘，以及维基词典中频率最高的词汇，还有英国国家语料库，函数words(text)将文本分割为词组，并统计每个词出现的频率保存在变量WORDS中，P基于该统计评估每个词的概率：
|
1
2
3
4
5
6
7
8
9
10
11
|
def words(text):
return re.findall(r'w+', text.lower())
# 统计词频
WORDS = Counter(words(open('big.txt').read()))
def P(word, N=sum(WORDS.values())):
"""词'word'的概率"""
return float(WORDS[word]) / 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
39
|
>>> len(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
|
4.错误模型：2007年坐在机舱内写这个程序时，我没有拼写错误的相关数据，也没有网络连接(我知道这在今天可能难以想象)。没有数据就不能构建拼写错误模型，因此我采用了一个捷径，定义了这么一个简单的、有缺陷的模型：认定对所有已知词距离为1的编辑必定比距离为2的编辑概率更高，且概率一定低于距离为0的单词（即原单词）。因此函数candidates(word)的优先级如下：
1. 原始单词（如果已知），否则到2。
2. 所有距离为1的单词，如果为空到3。
3. 所有距离为2的单词，如果为空到4。
4. 原始单词，即使它不是已知单词。
效果评估
现在我们看看程序效果如何。下飞机后，我从牛津文本档案库下载了Roger Mitton的伯克贝克拼写错误语料库，从中抽取了两个错误修正测试集，前者在开发中作为参考，调整程序以适应其结果；后者用于最终测试，因此我不能偷看，也无法在评估时修改程序。取两个集合分别用于开发和测试是个好习惯，它让我不至于自欺欺人地调整程序以适应结果，然后觉得程序效果有提升。我还写了单元测试：
|
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
def unit_tests():
"""开发的单元测试"""
assert correction('speling') == 'spelling' # insert
assert correction('korrectud') == 'corrected' # replace 2
assert correction('bycycle') == 'bicycle' # replace
assert correction('inconvient') == 'inconvenient' # insert 2
assert correction('arrainged') == 'arranged' # delete
assert correction('peotry') =='poetry' # transpose
assert correction('peotryy') =='poetry' # transpose + delete
assert correction('word') == 'word' # known
assert correction('quintessential') == 'quintessential' # unknown
assert words('This is a TEST.') == ['this', 'is', 'a', 'test']
assert Counter(words('This is a test. 123; A TEST this is.')) == (
Counter({'123': 1, 'a': 2, 'is': 2, 'test': 2, 'this': 2}))
assert len(WORDS) == 32192
assert sum(WORDS.values()) == 1115504
assert WORDS.most_common(10) == [
('the', 79808),
('of', 40024),
('and', 38311),
('to', 28765),
('in', 22020),
('a', 21124),
('that', 12512),
('he', 12401),
('was', 11410),
('it', 10681)]
assert WORDS['the'] == 79808
assert P('quintessential') == 0
assert 0.07 < P('the') < 0.08
return 'unit_tests pass'
def spelltest(tests, verbose=False):
"""对测试集合1中的(right, wrong)词条，运行correction(wrong)并统计结果的正确性"""
import time
start = time.clock()
good, unknown = 0, 0
n = len(tests)
for right, wrong in tests:
w = correction(wrong)
good += (w == right)
if w != right:
unknown += (right not in WORDS)
if verbose:
print('correction({}) => {} ({}); expected {} ({})'
.format(wrong, w, WORDS[w], right, WORDS[right]))
dt = time.clock() - start
print('{:.0%} of {} correct ({:.0%} unknown) at {:.0f} words per second '
.format(good / n, n, unknown / n, n / dt))
def Testset(lines):
"""对测试集合2中的错误样本，将'wrong1 wrong2'修正为[('right', 'wrong1'), ('right', 'wrong2')]"""
return [(right, wrong)
for (right, wrongs) in (line.split(':') for line in lines)
for wrong in wrongs.split()]
print(unit_tests())
spelltest(Testset(open('spell-testset1.txt'))) # Development set
spelltest(Testset(open('spell-testset2.txt'))) # Final test set
|
结果如下：
|
1
2
3
4
|
unit_tests pass
75% of 270 correct at 41 words per second
68% of 400 correct at 35 words per second
None
|
可以看到，开发部分的集合准确率达到了74%（处理速度是41词/秒），而在最终的测试集中准确率是68%（31词/秒）。结论是：我达到了简洁，开发时间短，运行速度快这3个目的，但准确性不太高。也许是我的测试集太复杂，又或是模型太简单因故而不能达到80%~90%的准确率。
后续工作
考虑一下我们如何做的更好。
1. 语言模型P(c)。在语言模型中我们能区分两种类型的错误（译者：known词和unknown词，前者2次编辑词集合存在元素inWORDS，后者不存在），更为严重的是unknow词，程序会直接返回该词的原始结果。在开发集合中，有15个unknown词，约占5%，而测试集中有43个（11%）。以下我们给出部分spelltest的运行结果：
|
1
2
3
|
correction('transportibility') => 'transportibility'(0); expected 'transportability'(0)
correction('addresable') => 'addresable' (0); expected 'addressable' (0)
correction('auxillary') => 'axillary' (31); expected 'auxiliary' (0)
|
我将期望输出与实际输出分别打印出来，计数’0’表示目标词汇不在词库字典内，因此我们无法纠错。如果能收集更多数据，包括使用一些语法(例如在单词后加入”ility”或是”able”)，我们能构建一个更好的语言模型。
处理unknown词汇的另一种办法是，允许correction结果中出现我们没见过的词汇。例如，如果输入是”electroencephalographicallz”，较好的一种修正是将末尾的’z’替换成’y’，尽管”electroencephalographically”并不在词库里，我们可以基于词成分，例如发音或后缀来实现此效果。一种更简单的方法是基于字母序列：统计常见2、3、4个字母序列。
2. 错误模型P(w|c)。目前为止我们的错误模型相当简陋：认定编辑距离越短错误越小。这导致了许多问题，许多例子中应该返回编辑距离为2的结果而不是距离为1。如下所示：
|
1
2
3
4
5
|
correction('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’的简单编辑概率很低。
显然我们可以根据编辑开销来改进模型：根据直觉将叠词的编辑开销降低，或是改变元音字母。一种更好的做法是收集数据：收集拼写错误的语料，并对照正确单词统计增删、替换操作的概率。想做好这些需要大量数据：例如给定窗口大小为2的两个单词，如果你想得到两者间的全部修正概率，其可能的转换有266种，超过3000万词汇。因此如果你想获取每个单词的几个转换实例，大约需10亿条修正数据，如要保证质量，大概需要100亿之多。叉车租赁
注意到语言模型和错误模型存在联系：目前如此简陋（编辑距离为1的词必定优于编辑距离为2的词）的错误模型给语言模型造成阻碍：我们不愿将相对冷僻的词放入模型内，因为如果这类词恰好与输入单词的编辑距离为1，它将被选中，即使存在一个编辑距离为2但很常见的词。好的错误模型在添加冷僻词时更富有侵略性，以下例子展示了冷僻词出现在字典里的危害：
|
1
2
3
4
|
correction('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)
|
3. 修正集合argmaxc。本程序会枚举某单词所有编剧距离2以内的修正，在开发集的270个修正词中只有3个编辑距离超过2，然而在测试集合中，23/400个编辑距离超过2，它们是：
|
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
|
purple 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’之间的替换。
4. 第四种（也可能是最佳）改进方案为：将correction的文本窗口调大一些。当前的correction只检测单个词，然而在许多情形下仅靠一个单词很难做出判决。而假若这个单词恰好出现在字典里，这种纠错手段就更显无力。例如：
|
1
2
3
|
correction('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”。
要构建一个能同时处理词和上下文的模型需要大量数据。幸运的是，Google已经公开了最长5个词的全部序列词库，该数据源于上千亿的语料集。我相信要使拼写纠错准确率达到90%，必须依赖上下文辅助决策，关于这个以后我们再讨论。
我们也可以决定以哪种方言进行训练。以下纠正时产生的错误均源于英式和美式拼写间的差异：
|
1
2
3
|
correction('humor') => 'humor' (17); expected 'humour' (5)
correction('oranisation') => 'organisation' (8); expected 'organization' (43)
correction('oranised') => 'organised' (11); expected 'organized' (70)
|
5. 最后，我们可以改进实现方法，使程序在不改变结果的情况下运行速度更快。例如：将实现该程序的语言从解释型语言换成编译型语言；缓存纠错结果从而不必重复纠错。一句话：在进行任何速度优化前，先大致看看时间消耗情况再决定优化方向。