如何编写拼写检查器

本文翻译自 How to Write a Spelling Corrector，讲述用很少的一段代码实现拼写检查的功能。 本文是贝叶斯公式的一个很好的实例，比教科书上寥寥几句的例题更能帮助读者深入理解贝叶斯公式。

开篇

2007年的某一周里，我有两个朋友（Dean 和 Bill）分别找到我，说他们对谷歌新推出的拼写纠错功能感到惊讶：在搜索框里输入一个拼写错误的关键字，比如 speling ，谷歌会立刻返回 “显示 Spelling 的搜索结果：”。我这两位仁兄在各自的工程和数学领域都取得了不小的成就，竟然对这个纠错过程的背后运作原理都没有自己的直觉判断。不过想想也对，有谁会愿意在自己专业范围之外再多学点东西？

如果我出面对此问题做个解释，他们两个（也可能包括广大读者）也许能从中受益。大厂开发的拼写纠错程序属于工业产品，其细节相当复杂，以致于我们无法了解具体的细节。但是好消息是，我们也不需要了解那么详细，只要明白其中基本的原理即可。

于是我在一次长途飞机旅途中写了一个简单如玩具的拼写纠错程序，一共也只有半页左右的代码，竟然能以每秒10个单词的处理速度达到 80% 甚至 90% 的正确率。

全部代码都在这里（Python3 的版本见 这里）：

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

函数 correct（word） 能返回一个可能性很高的正确拼写形式，例如：

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

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

（说明我们还是有信心继续研究下去，而不用管大厂的程序有多复杂，毕竟原理都是想通的。）

运行原理（概率论角度）

在 上节 的代码里，correction(w) 函数尝试寻找参数值 w 最大可能的正确拼法。程序并不能完全给出十分确定的答案（例如，“lates” 究竟应该被纠正为 “late”、“latest”、“lattes”还是其他什么？）。于是我们只能持概率的观点：在给定原始拼法 w 的情况下，在可能的原始单词集合中，找到成为原始单词概率最大的那个 c.

写成数学公式如下：

$$\argmax_{c\in 全部可能原始单词}P(c|w)$$

根据贝叶斯定理，上式等价于： $$\argmax_{c\in 全部可能原始单词}\dfrac{P(c)P(w|c)}{P(w)}$$

对每个可能的备选 c ， $P(w)$ 都是相等的，因此可以将其作为常量因子提取出来，转化为： $$\argmax_{c\in 全部可能原始单词}P(c)P(w|c)$$

我们观察上式的四个部分：

1. 挑选法则

我们从备选答案中，选择能使两个概率乘积 $P(c)P(w|c)$ 达到最大值的 c，也就是 $\argmax$

2. 备选模型

$ {c\in} $ 全部可能原始单词。这表示预先确定 c 的可能单词集合。

3. 语言模型

$P(c)$. 在英语文本中，任意一个词 c 出现的概率。例如，在大量的文本中，the 一词出现的频率为 $7\%$，因此估算出 $P({\rm the})=0.07$

4. 出错模型

$P(w|c)$. 当原始意图是 c 单词时，实际错写为 w 的概率。例如，$P({\rm teh}|{\rm the})$ 的概率值相对较高，但 $P({\rm theeexyz}|{\rm the})$ 的概率值将非常低。

读者很可能会问：为什么要把最初的简单的单模型 $P(c|w)$ 写成更为复杂的、两个模型的 $P(c)P(w|c)$ ？

回答是 $P(c|w)$ 模型将“语言模型”和“出错模型”等两个不相干的因素杂糅在一起，导致难以处理。我们要寻求简化问题，就要将两个无关因素分解开，再各自单独处理。

例如：遇到一个拼写错误的单词 w="thew" ，还有两个备选的原始正确拼写 c="the" 和 c="thaw"。哪个 c 有更高的 $P(c|w)$ ？“thaw” 似乎更像一些，因为从 “a” 到 “e” 只是一个细小的改变。然而，“the” 似乎也不错，因为 “the” 是一个非常常见的词，尽管在后面加上 “w” 字母是一个更大的、从而不太可能出现的改变，但也许是在敲键盘的时候，手指从 “e” 键滑到了旁边的 “w” 键。

举这个例子是为了说明：要想估计 $P(c|w)$ 的数值，我们必须同时考虑备选的原始单词 c 出现的概率（$P(c)$）和从 c 出错到 w 的概率（$P(w|c)$），如果合并在一起，将难以快速做出抉择。必须将这两个因素从表达式的形式上分解开，各自考虑，才会使处理思路更为清晰。

运行原理（Python角度）

上节中 从概率论角度将问题分成四个部分讨论，本节使用 Python 程序实现这四个部分：

1. 挑选法则

Python中的 max(iterable, *, key=None) 函数的 key 参数，可以实现 $\argmax$

2. 备选模型

在解释备选模型之前，先要明确 simple edit （简单修改） 操作的含义：

• deletion: 指从单词中删除一个字母
• transposition: 指交换两个相邻字母的位置
• replacement: 将一个字母替换为另一个字母
• insertion: 添加一个字母

明确了简单修改的定义后，然后再来看 开篇 代码中的 edits1(word) 函数，接受字符串参数 word 。无论 word 是不是一个已知的单词，总是返回 word 经过一次简单修改后所有可能结果的集合。

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)

不难想象， edits1(word) 函数返回的结果会是个巨大的集合。假设字符串参数 word 的长度为 $n$ , 则上述四种简单修改的可能结果数量分别为：

• deletion: $n$
• transposition：$n-1$
• replacement: $26n$
• insertion: $26(n+1)$

合计：$54n+25$ 种可能，其中极少重复的（注：函数返回的是set 类型，如果有重复的，会自动去掉）。例如：

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

这个例子中，错误拼写 len('somthing') 等于 $8$ , 所以有 $54\times8+25=457$ , 说明有 $457-442=15$ 种重复情况。

虽然简单修改的全部结果数量庞大（例如上面的 442），但是其中大部分都不是正确的英文单词。如果我们将返回结果限制为字典里的单词（即下面例子中的 WORD），返回结果集就会小很多。下面的 known(words) 函数用于过滤出字典里的单词。

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

比如：经过 known(words) 一次字典筛选后， 442中可能性只剩下了2个：

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

到现在为止，只考虑了错一个字母的情况，即通过一次简单修改就能恢复原来的单词。或者说，我们假设 known() 函数返回的集合中，必然包括原始意图的正确单词 c ，这样的程序容错水平不够好，有可能会找不到正确的原始单词。所以，我们再考虑两次简单修改才能恢复的情况。

def edits2(word): return (e2 for e1 in edits1(word) for e2 in edits1(e1))

edits2() 函数通过双重循环实现了两次简单修改。显然，结果是个更大的集合。但是加了字典单词的限制后，往往结果里也没几个，例如：

>>> len(set(edits2('something'))
90902

再经过 known(words) 的字典筛选后，结果也只有 8 个：

>>> known(edits2('something'))
{'seething', 'smoothing', 'something', 'soothing'}

>>> known(edits2('somthing'))
{'loathing', 'nothing', 'scathing', 'seething', 'smoothing', 'something', 'soothing', 'sorting'}

我们可以称 edits2(w) 的返回结果集到 w 的 修改距离 (edit distance) 为 $2$

3. 语言模型

我们为了计算任意一个单词 word 在英文中出现的概率 $P({\rm word})$，事先建立起含有1百万个单词的语料库 big.txt 。这个语料库的来源有：古腾堡计划 中公开书籍的内容片断、Wiktionary 和 British National Corpus 中的常用词。

word() 函数将语料库中的长句分割成单词，形成词汇表，然后转换为一个 Counter 对象，用来统计词汇表中每个单词出现的次数，赋值给 WORD 变量。

def words(text): return re.findall(r'\w+', text.lower())

WORDS = Counter(words(open('big.txt').read()))

我们可以用每个单词在 WORD 中出现的次数估计其在整个英文语言中出现的概率。P() 函数用来实现概率的估计：

def P(word, N=sum(WORDS.values())): return WORDS[word] / N

从下面的例子中可以看到，词汇表中包含 32192 个不同的单词，一共出现了 1,115,504 次，单词 the 共出现了 79,808 次，是出现频率最高的单词（概率近似为 $7\%$）

>>> len(WORDS)
32192

>>> sum(WORDS.values())
1115504

我们的词汇表中，出现次数最多的10个单词是：

>>> 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$，即与事实不符。

根据这个模型，我们可以使按照如下优先级顺序输出备选单词的集合：

1. 如果单词 word 恰好在词汇表中，那么认为是正确的拼写，而不是其他单词拼错的结果，
2. 如果上一条结果为空，那么返回所有经过修改距离为 1 的已知词汇，
3. 如果上一条结果为空，那么返回所有经过修改距离为 2 的已知词汇，
4. 如果上一条结果为空，就说明找不到修复的可能，原样返回。

输出备选单词的集合由 candidate(word) 函数完成：

def candidates(word): 
    return known([word]) or known(edits1(word)) or known(edits2(word)) or [word]

这个函数使用了 Python 中的短路逻辑（short circuiting）实现了优先级的选择。

按照上面的不完美模型，每一次返回的备选单词集合都属于修改距离相同的情况，不会有两种情况掺在一起。那么对于返回的集合中的所有备选单词，$P(w|c)$ 都是相等的。

比如，收到的 w 是 “cac”，它本身不是已知的单词，那么符合上述第二条，可以得到的修改距离为1的集合大致为：

cab, can, cat, car...

上面的简化模型认为，这些词写错到 “cac” 的概率是相等的。所以寻找 $\argmax$ 的时候，不需要再乘上 $P(w|c)$ :

def correction(word): return max(candidates(word), key=P)

性能评估

到这里，全部代码就解释完了，现在到了评估性能的时候了。我乘坐的飞机落地后，我从牛津文本档案中下载了 Birkbeck 大学 Roger Mitton 编写的错误语料库。我下载了两个错误拼写集，一个是开卷的（即训练集），在我开发代码的时候可以查看；另一个是闭卷的（即测试集），仅用来验证程序的性能，我既不能打开看其中的内容，我的程序一旦开始测试后，也不能再修改了。

使用两个样本集是个好习惯，使我不能因为针对样本调整参数而自欺欺人的觉得是我的程序写得好。

另外我还写了一些单元测试，整个测试过程如下，spell-testset1.txt 是训练集，spell-testset2.txt 是测试集。

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

测试输出如下：

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

可以看出，在训练集上，我的程序给出了 75% 的正确率，速度为每秒 41 个单词，测试集上的结果是 68% 的正确率，速度为每秒 35 个单词。

结论是，我在简洁度、开发所用时间、运行速度等方面对我的程序比较满意，而正确率上则不达标。可能是因为测试集太难了，也可能是因为我的不完美模型过于简单了，难以达到 80% 甚至 90% 的正确率。

改善工作

我们来思考一下如何进一步优化程序：重新考察 运行原理 中推出的公式：

$$\argmax_{c\in 全部可能原始单词}P(c)P(w|c)$$

1. 语言模型

仔细思考语言模型 $P(c)$ 中的错误产生原因：词汇表不够全。在训练集里，有 15 个未知词汇，占比 5% ，而在测试集中，这个数字达到了 43 ，占 11% 。

下面是 spelltest 函数的 verbose 参数设为 True 时，程序打印的输出：

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

从这个例子中，能看到

2. 出错模型

如果您对本文有疑问或者寻求合作，欢迎 联系邮箱 。邮箱已到剪贴板

精彩评论