光环大数据教你如何编写一个拼写纠错器

光环大数据（大数据培训班的专业机构）， 2007年的某个星期，我的两个朋友(Dean和Bill)分别向我传达了他们对Google的拼写自动纠错能力的赞叹。例如输入”speling”，Google会立即显示”spelling”的检索结果。我原以为这两位才智卓越的工程师、数学家，会对 ...

Python 模型 测试 Hadoop 培训

2007年的某个星期，我的两个朋友(Dean和Bill)分别向我传达了他们对Google的拼写自动纠错能力的赞叹。例如输入”speling”，Google会立即显示”spelling”的检索结果。我原以为这两位才智卓越的工程师、数学家，会对其工作原理有准确的推测，事实上他们没有。后来我意识到，他们怎么会对离自身专业领域如此远的东西认知清晰呢？
我觉得他们还有其他人，也许能从拼写纠错原理的解释中获益。工业级的完整拼写纠错相当复杂(详细参见[1]和[2])，在横贯大陆的航空旅途中，我用约半页代码写了一个迷你拼写纠错器，其性能已经达到对句子以10词/秒的速度处理，且纠错准确率达到80%~90%。
代码如下：# coding:utf-8 import refrom 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)返回一个最有可能的纠错还原单词：
>>>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个部分：选择机制：在Python中，带key的max()函数即可实现argmax的功能。候选模型：先介绍一个新概念：对一个单词的简单编辑是指：删除(移除一个字母)、置换(单词内两字母互换)、替换(单词内一个字母改变)、插入(增加一个字母)。函数edits1(word)返回一个单词的所有简单编辑（译者：称其编辑距离为1）的集合，不考虑编辑后是否是合法单词:
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个简单编辑（其中存在重复）。例如：
>>>len(edits1('something'))442
然而，如果我们限制单词为已知(known，译者：即存在于WORDS字典中的单词)，那么这个单词集合将显著缩小：
def known(words):    """'words'中出现在WORDS集合的元素子集"""    return set(w for w in words if w in WORDS) >>>known(edits1('something'))['something', 'soothing']
我们也需要考虑经过二次编辑得到的单词（译者：“二次编辑”即编辑距离为2，此处作者巧妙运用递归思想，将函数edits1返回集合里的每个元素再次经过edits1处理即可得到），这个集合更大，但仍然只有很少一部分是已知单词：
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基于该统计评估每个词的概率：
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%)，其他词概率低一些。
>>> 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)的优先级如下：
原始单词（如果已知），否则到2。所有距离为1的单词，如果为空到3。所有距离为2的单词，如果为空到4。原始单词，即使它不是已知单词。
效果评估现在我们看看程序效果如何。下飞机后，我从牛津文本档案库下载了Roger Mitton的伯克贝克拼写错误语料库，从中抽取了两个错误修正测试集，前者在开发中作为参考，调整程序以适应其结果；后者用于最终测试，因此我不能偷看，也无法在评估时修改程序。取两个集合分别用于开发和测试是个好习惯，它让我不至于自欺欺人地调整程序以适应结果，然后觉得程序效果有提升。我还写了单元测试：
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 setspelltest(Testset(open('spell-testset2.txt')))  # Final test set
结果如下：unit_tests pass75% of 270 correct at 41 words per second68% of 400 correct at 35 words per secondNone
可以看到，开发部分的集合准确率达到了74%（处理速度是41词/秒），而在最终的测试集中准确率是68%（31词/秒）。结论是：我达到了简洁，开发时间短，运行速度快这3个目的，但准确性不太高。也许是我的测试集太复杂，又或是模型太简单因故而不能达到80%~90%的准确率。
后续工作考虑一下我们如何做的更好。
1. 语言模型P(c)。在语言模型中我们能区分两种类型的错误（译者：known词和unknown词，前者2次编辑词集合存在元素inWORDS，后者不存在），更为严重的是unknow词，程序会直接返回该词的原始结果。在开发集合中，有15个unknown词，约占5%，而测试集中有43个（11%）。以下我们给出部分spelltest的运行结果：
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。如下所示：
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但很常见的词。好的错误模型在添加冷僻词时更富有侵略性，以下例子展示了冷僻词出现在字典里的危害：
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，它们是：
purple perpulcurtains courtensminutes muinetssuccessful sucssufulhierarchy heiarkyprofession preffesonweighted wagtedinefficient ineffiectavailability avaiblitythermawear thermawherenature natiordissension desentionunnecessarily unessasarilydisappointing dissapoitingacquaintances aquantencesthoughts thortscriticism citisumimmediately imidatlynecessary necaserynecessary nessasarynecessary nessisaryunnecessary unessessaynight niteminutes muiuetsassessing accesingnecessitates 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)
我们几乎不可能知道correction('where')在某个语句内应该返回”were”，而在另一句返回”where”。但如果输入语句是correction('They where going')，我们很容易判定此处”where”应该被纠错为”were”。
要构建一个能同时处理词和上下文的模型需要大量数据。幸运的是，Google已经公开了最长5个词的全部序列词库，该数据源于上千亿的语料集。我相信要使拼写纠错准确率达到90%，必须依赖上下文辅助决策，关于这个以后我们再讨论。
我们也可以决定以哪种方言进行训练。以下纠正时产生的错误均源于英式和美式拼写间的差异：
correction('humor') => 'humor' (17); expected 'humour' (5)correction('oranisation') => 'organisation' (8); expected 'organization' (43)correction('oranised') => 'organised' (11); expected 'organized' (70)
5. 最后，我们可以改进实现方法，使程序在不改变结果的情况下运行速度更快。例如：将实现该程序的语言从解释型语言换成编译型语言；缓存纠错结果从而不必重复纠错。一句话：在进行任何速度优化前，先大致看看时间消耗情况再决定优化方向。
阅读材料Roger Mitton关于拼写检测的调研文章Jurafsky 和 Martin的教材中拼写检测部分。Manning 和 Schutze 在他们编撰的 Foundations of StatisticalNatural Language Processing 中很好的讲述了统计语言模型, 但似乎没有(至少目录中没有)提及拼写检查。aspell 项目中有大量有趣的材料，其中的一些测试数据似乎比我使用的更好。LinPipe 项目有一个拼写检测教程

 　   大数据时代，大数据培训机构，就选光环大数据！

 　　原创文章，转载请注明出处：光环大数据官网。

大数据培训、人工智能培训、Python培训、大数据培训机构、大数据培训班、数据分析培训、大数据可视化培训，就选光环大数据！光环大数据，聘请专业的大数据领域知名讲师，确保教学的整体质量与教学水准。讲师团及时掌握时代潮流技术，将前沿技能融入教学中，确保学生所学知识顺应时代所需。通过深入浅出、通俗易懂的教学方式，指导学生更快的掌握技能知识，成就上万个高薪就业学子。 更多问题咨询，欢迎点击------>>>>在线客服！