如何写一个拼写纠错器 -- how to write a spelling corrector

本文是经典的how to write a spelling corrector的大致翻译。

作者两个朋友向他夸赞google的拼写纠正功能，输入speling, google就会立即问你是不是找spelling相关的结果。作者的这两个朋友都是高级的工程师和数学家，却也不知道这个的原理。
由此，作者想要简单解释一下spelling corrector背后的原理。工业级别的实现非常复杂，但是简单一些的spelling corrector也能得到80%-90%的正确性。

代码如下：

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())): 
    "Probability of `word`."
    return WORDS[word] / N

def correction(word): 
    "Most probable spelling correction for word."
    return max(candidates(word), key=P)

def candidates(word): 
    "Generate possible spelling corrections for word."
    return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])

def known(words): 
    "The subset of `words` that appear in the dictionary of WORDS."
    return set(w for w in words if w in WORDS)

def 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)

def edits2(word): 
    "All edits that are two edits away from `word`."
    return (e2 for e1 in edits1(word) for e2 in edits1(e1))

• 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

函数correction（word）返回一个可能的拼写纠错：

>>> correction('speling')
'spelling'

>>> correction('korrectud')
'corrected'

• 1
• 2
• 3
• 4
• 5

How it works:一些概率理论

correction(w)试图选择w最可能的拼写纠正。没办法完全确定用户到底想输入啥，这就表明我们要用到概率。给定输入的原本错误的单词w，在所有候选的单词中，选择概率最大的correction c：
a r g m a x c ∈ c a n d i d a t e s P ( c ∣ w ) argmax_{c\in candidates}P(c|w) argmaxc∈candidates​P(c∣w)
通过贝叶斯定理，上式就等于
a r g m a x c ∈ c a n d i d a t e s P ( c ) P ( w ∣ c ) / P ( w ) argmax_{c\in candidates}P(c)P(w|c ) /P(w) argmaxc∈candidates​P(c)P(w∣c)/P(w)
因为对每个候选词c,P(w)是相等的，所以可以不考虑它：
a r g m a x c ∈ c a n d i d a t e s P ( c ) P ( w ∣ c ) argmax_{c\in candidates}P(c)P(w|c ) argmaxc∈candidates​P(c)P(w∣c)
这个公式包含四部分：

1. 选择机制：argmax 我们选择由最高组合概率的候选词
2. 候选模型：candidates 告诉我们考虑哪些候选词
3. 语言模型：P( c) 这个概率表示c以单词形式出现在英文文本中的概率。 比如，单词“the”大概占英文文本的7%，所以P(the)=0.07
4. 错误模型 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’在英文中非常常见，而加一个’w’则是一个不太可能的大改变，可能是打字者的手指不小小划过e而输入了w。 因此，要估计P(c|w)，我们不得不考虑这两方面的概率：即单词c本身的概率以及从c转到w的概率。所以，直接拆开成两部分更清晰。

How it works:一些Python

这四部分对应的程序是这样额：

1. 选择机制： 在Python中，用max函数，加上一个参数就能实现argmax
2. 候选模型： 这里要先提出一个新的概念：编辑距离。编辑距离为1，表示一个单词删掉一个字母、或交换两个相邻字母、或插入一个字母、或替换一个字母之后得到的单词，与原来的单词编辑距离为1。函数edits1返回一个集合，包含距离传入单词所有编辑距离为1的单词：

def 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)

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

这个集合可能非常大。对于一个长度为n的单词，可以由n个删除后的单词，n-1种交换，26n中替换，以及26（n+1）种插入，共54n+25（里面是有些重复的）种，例如：

>>> len(edits1('somthing'))
442

• 1
• 2

然而，如果我们只把候选词限制在已知词汇表里，即只保留词典中的词，那集合就小得多了：

def known(words): return set(w for w in words if w in WORDS)

>>> known(edits1('somthing'))
{'something', 'soothing'}

• 1
• 2
• 3
• 4

我们也考虑编辑距离为2的候选词，这会产生更多的单词，但只有一部分是在词典中的：

def 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'}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

所以edits2(w)得到的单词距离w的编辑距离为2.

1. 语言模型 ：我们可以通过从大的文本(big.txt)里计数一个词出现的频率来估计一个单词word的概率P(word)。函数words把文本拆成单词，然后变量WORDS保存着每个单词出现的次数，而P基于词频估计概率：

def 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] / N

• 1
• 2
• 3
• 4
• 5

可以看到由32192个不同的单词，总共出现了1，115，504次，单词’the’出现次数最多，达79808次（大概7%的概率）：

>>> 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

• 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

• 错误模型： 当我写这个程序的时候，是2007年在一架飞机上，没有拼写错误的数据，也没联网。因为没有数据，我无法建立一个好的拼写错误模型，所以我采用一种捷径：我定义了一种小的、有缺陷的错误模型，认为所有距离已知词编辑距离为1的词比编辑距离为2的词的概率大，而编辑距离为0的概率最大。所以我们可以让candidates(word)根据优先级生成第一个非空的列表：

• 如果单词在词典里，那就是这个单词，否则

• 如果有的话，列出该单词编辑距离为1的单词列表，否则

• 编辑距离为2的，否则

• 本身的单词，即使这个词没在词典里出现

这样我们就不需要乘以P(w|c)因子了，因为同一优先级的候选词的概率相同，也就是：

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]

• 1
• 2
• 3
• 4

评估测试

现在该进行评估我们项目怎么样了。我飞机落地后，下载了Roger Mitton的Birkbeck spelling error corpus ，然后提取了两组数据，第一个是development数据，用于在开发的时候看，另一个是最终的测试机，开发者不能提前看。用两个数据集，可以让程序不过拟合一个数据集。我还写了一些单元测试：

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):
    "Run correction(wrong) on all (right, wrong) pairs; report results."
    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):
    "Parse 'right: wrong1 wrong2' lines into [('right', 'wrong1'), ('right', 'wrong2')] pairs."
    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
• 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

输出是这样滴

unit_tests pass
75% of 270 correct at 41 words per second
68% of 400 correct at 35 words per second
None

• 1
• 2
• 3
• 4

这样在development集上得到75%的正确率（一秒处理41个单词），在最终的测试集上有68%正确率。最终，开发时间和运行时间符合作者预期。可能是测试集太难了，也可能是这个简单的模型的确达不到80%到90%的正确性。

未来工作

让我们想想怎么可以更好。
1、P( c )，语言模型。我们可以在语言模型中看到两种错误烈性。更严重的是不在词典中的词。在development set中，有15个未知词，5%，而在最后的测试集中，43未知词，11%。几个例子：

correction('transportibility') => 'transportibility' (0); expected 'transportability' (0)
correction('addresable') => 'addresable' (0); expected 'addressable' (0)
correction('auxillary') => 'axillary' (31); expected 'auxiliary' (0)

• 1
• 2
• 3

调用correction，以及实际的和预期结果（括号里是WORDS里保存的词频）。（0）表示目标词词典里就没有，所以我们根本就没机会中却。我们可以搞一个更好的而语言模型，通过收集更多数据，也可以用点英语的语法（比如加’ility’ 'able’等）

另一种处理未知词的方法是允许correction的候选词里有词典中没有的词。例如，如果输入是’electroencephalographicallz’，一个好的候选词可以是把最后的’z’换成’y’，即使‘electroencephalographically’不在我们词典里。我们可以通过基于单词组成部分构造语言模型：可以是基于音节或词缀。但是基于字母序列更容易一点，通常是2- 3- 4- 字母序列

2、P(w|c),错误模型。目前，错误模型非常简单：编辑距离越小，错误越少。这里有一些问题，如下面例子所示。首先，一些情况里correction会返回编辑距离为1的候选词，但实际应该返回编辑距离为2的。

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)

• 1
• 2
• 3
• 4
• 5

为什么’adres’应该被改成’address’而不是’acres’？直观来看，‘d’转到’dd’，‘s’转到’ss’，这种转换是非常常见的，概率很大，而将’d’转成’c’的概率则很小。

很明显，我们应该用个更好的模型。我们可以用直观感受，对于double字母 以及元音字母间转换的这种，给更低的cost。但是更好的还是收集数据：收集错拼数据，计数每种插入、删除、改变的概率。这需要大量的数据。如果我们想看一个字母变成另一个字母，给定一个两字母的窗口，那就是 2 6 6 26^6 266.每一种都需要几个例子，平均而言，需要至少十亿，可能一百亿更安全一些。

注意到语言模型和错误模型之间是有联系的。当前的程序错误模型太简单了（编辑距离为1的单词都排在编辑距离为2的），也是语言模型的障碍：我们不敢加一些obscure words到模型里，因为如果其中一个obscure words正好是一个输入单词的编辑距离为1的单词，那可能就会被选择。但可能编辑距离为2的一个单词更加常用。如果错误模型根号，我们就敢于加更多obscure words到词典里。有几个例子表明obscure words的出现让我们很受伤：

correction('wonted') => 'wonted' (2); expected 'wanted' (214)
correction('planed') => 'planed' (2); expected 'planned' (16)
correction('forth') => 'forth' (83); expected 'fourth'

• 1
• 2
• 3

3、可能的候选测的枚举：argmax。我们的程序美剧所有编辑距离为2以内的候选词。在development集合里，270个词中只有3个是超过编辑距离2的，但是在最终测试集里，400个中由23个。是这些：
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函数一次只看一个单词，结果很多情况下很难作出决定。显然的，当一个词出现在词典里，但测试集合却说应该换成另一个词：

correction('where') => 'where' (123); expected 'were' (452)
correction('latter') => 'latter' (11); expected 'later' (116)
correction('advice') => 'advice' (64); expected 'advise' (20)

• 1
• 2
• 3

我们没法知道correction(‘where’)应该是’were’，还是’where’。但是如果query是correction(‘They where going’)，就更可能知道这里’where’应该被替换为’were’。

加上上下文，就可以在多个好候选词之间更好的做出选择。考虑：

correction('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)

• 1
• 2
• 3
• 4
• 5
• 6

为什么’thear’应该被改成’there’而不是’their’？只用一个词很难进行判断，但是如果是由上下文，就比较清晰了。

要建立一次看多个单词的模型，我们许哟啊更多的数据。幸运的是，Google开放了database of word counts，有最长5个词的单词序列。

我认为达到90%的spelling corrector需要考虑上下文来作出决策。但是我们以后再实现……

我们还可以考虑我们正在训练的是什么数据集。下面三个错误要考虑是美式英语还是英式英语（而我们的训练数据里两者都有）

correction('humor') => 'humor' (17); expected 'humour' (5)
correction('oranisation') => 'organisation' (8); expected 'organization' (43)
correction('oranised') => 'organised' (11); expected 'organized' (70)

• 1
• 2
• 3

5、最后，我们可以让程序再不改变结果的同时更快一点。我们可以重新实现一个编译语言版本，而不是解释语言。还可以缓存中间结果。一个建议：再试着提速之前，先仔细看看时间实际都用到哪了。