英文单词拼写纠错

程序员文章站 2022-07-06 18:58:57

在知乎上看到了一个问题“有哪些你喜欢的逻辑清晰，书写优雅的源代码呢？” 有人po出了大神Peter Norvig的‘Spelling Corrector’（拼写检查器） by http://norvig.com/spell-correct.html 文章大意：2007年的一个星期，两位朋友（迪恩和比 ......

在知乎上看到了一个问题“有哪些你喜欢的逻辑清晰，书写优雅的源代码呢？”

有人po出了大神peter norvig的‘spelling corrector’（拼写检查器）

文章大意：2007年的一个星期，两位朋友（迪恩和比尔）独立告诉我，他们对谷歌的拼写纠正感到惊讶。输入类似spelling的搜索，google会立即显示结果：拼写。我认为dean和bill是高度成熟的工程师和数学家，他们对这个过程的运作方式有很好的直觉。但他们没有，并且想到它，为什么他们应该知道迄今为止他们的专长？

我认为他们和其他人可以从解释中受益。工业强度法术纠正器的全部细节非常复杂。但我认为，在横贯大陆的飞机旅行过程中，我可以编写和解释一个玩具拼写校正器，在大约半页代码中以每秒至少10个字的处理速度达到80％或90％的准确度。

源代码如下：

 1 import re
 2 from collections import counter
 3 
 4 #==== 训练一个带有概率的词库 ====
 5 def words(text): 
 6     return re.findall(r'\w+', text.lower())
 7 
 8 words = counter(words(open('d:\\big.txt').read()))
 9 
10 def p(word, n=sum(words.values())): 
11     "probability of `word`."
12     return words[word] / n
13 
14 #==== 给定单词a，枚举所有可能正确的拼写 ====
15 def edits1(word):
16     "all edits that are one edit away from `word`."
17     letters    = 'abcdefghijklmnopqrstuvwxyz'
18     splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
19     deletes    = [l + r[1:]               for l, r in splits if r]
20     transposes = [l + r[1] + r[0] + r[2:] for l, r in splits if len(r)>1]
21     replaces   = [l + c + r[1:]           for l, r in splits if r for c in letters]
22     inserts    = [l + c + r               for l, r in splits for c in letters]
23     return set(deletes + transposes + replaces + inserts)
24 
25 def edits2(word): 
26     "all edits that are two edits away from `word`."
27     return (e2 for e1 in edits1(word) for e2 in edits1(e1))
28 #==== 返回候选词  ====
29 def candidates(word): 
30     "generate possible spelling corrections for word."
31     return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])
32 
33 def known(words): 
34     "the subset of `words` that appear in the dictionary of words."
35     return set(w for w in words if w in words)
36 
37 #==== 输出概率最大的纠正词  ====
38 def correction(word): 
39     "most probable spelling correction for word."
40     return max(candidates(word), key=p)

其实自己没有其他博主的讲解是真的看不懂，甚至单词还有自己google翻译......我真是tcl......

一些概率知识

拼写检查器的目的是找到最近似错误输入“w”的正确拼写，但是对于一个错误拼写，其正确的候选者有很多（例如：“lates”应该被纠正为“late”呢，还是“lattes”呢？）。因此我们可以采取概率的思路，在错误拼写w出现的条件下，选择所有可能的备选纠正单词c中概率最大的。

由贝叶斯公式可得：

由于 $p (w)$

这个公式中由四个主要的部分：: 选择机构：argmax
我们选择备选单词中概率最高的单词作为输出。; 备选模型： $c \in c a n d i d a t e s$; $p (c)$; 错误模型： $p (w | c)$

我们用条件概率 $p (w | c)$

python具体实现过程

$p (w | c)$

这是一个很大的set，因为对于一个长度为n的单词，会生成n个deletions，n-1个transpositions，26n个replacements，16（n+1）个insertions，总共是（54n+25）个可能性。例如：

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

然而我们可以定义一个识别这些生成的备选单词正确性的模块，只匹配词典中存在的词。这个set将会变得很小，因为随机生成单词中，许多都是非法拼写的，并非真正存在。

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

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

同样，我们考虑经过两步骤的简单操作（edits）后得到的纠错备选模型（例如，写错了两个字母，写掉了两个字母），经过两次简单操作的组和将会生成更多的备选单词，但是也仅有很少一部分是正确拼写的单词，例如：

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

经过edits2（w）处理的单词，与原始单词w的edit distance（不知道怎么翻译，翻译为编辑距离？）为2。

3、语言模型

我们通过统计在语料库中某个词（word）出现的频率来衡量一个词的先验概率 $p (w o r d)$

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

通过一些简单的nlp操作，我们可以看到这里有32192个单词，所有单词一共出现了1115504次，’the’是出现概率最大的，一共出现了79808次：

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

定义出一个函数candidates（），根据优先级产生一个非空的候选单词序列：

优先级排序如下: 1、原始单词; 2、与原始单词的edit distance为1的单词（即经过一次编辑产生的那些拼写）
3、与原始单词的edit distance为2的单词（即经过两次编辑产生的那些拼写）
4、原始单词，即使那些单词是词典中没有的。

因此我们把条件概率模块替换成了这样一种优先级的排序。或许这其中还有很多不完善的地方，如根据什么别的语料库统计到，人们写单词写错的时候是写掉一个字母比多加一个字母常见，交换两个字母比写错一个字母常见等这些规则是我们在没学习也没数据的时候未知的，也是你在定义自己的拼写纠错器时，可以自己考虑的内容。因为我们现在只是一个玩具代码，所以我们采取了这样一个简单的优先级排序模式来替代这个重要的部分。

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

下载地址： spell-testset1

spell-testset2.txt

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

前人栽树，后人乘凉。感谢前人的经验分享与讲解，让后辈们受益颇多，也特此感谢博主irfan_lcmll的分享

另附自动纠错github其他开源代码

上一篇： PHP中计算字符串相似度的函数代码

下一篇：可爱没辙的小朋友和女版孙悟空图片

英文单词拼写纠错

python具体实现过程

世界上最长的英文单词189819个字母是谣言，读完只需3秒钟

Python实现单词拼写检查

在Word2010中设置“拼写和语法”选项

python实现将英文单词表示的数字转换成阿拉伯数字的方法

百度地图怎么纠错？百度地图位置报错的详细教程

怎样写一个拼写检查器 (python)

搜狗输入法如何拼音纠错

RedisRepository 分享和纠错

用CSS控制表格或单元格强制换行,防止表格被英文单词或中文撑大

世界上最长的英文单词189819个字母是谣言，读完只需3秒钟