【ＮＬＰ】单词纠错——ｐｙｔｈｏｎ⼩练习
原⽂来⾃：
金针菇炒肉起源
本⽂翻译⾃⼤⽜ Peter Norvig 的博⽂，作为本渣渣技术博客的第⼀篇内容，熟悉⼀下这个博客的操作哈~
意思就是⼤⽜⾃⼰的两个⼤⽜朋友问⼤⽜，为什么⾕歌的拼写检查功能这么厉害，⼤⽜很惊讶，为什么这么厉害的两个⼯程师+数学家竟然不懂这种简单的算法原理吗？看来此时只能本⼤⽜写⼀个简单的解释让⼤家能够从中获得⼀些有益的启发了。这只是⼀个玩具代码，正确率⼤概在80%~90%之间。速度⼤概在每秒钟⼗个词左右。代码很短。
下⾯就是代码啦~
import re
from collections import Counter
def words(text):return re.findall(r'\w+', text.lower())
WORDS = Counter(words(open('').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 subt of `words` that appear in the dictionary of WORDS."
return t(w for w in words if w in WORDS)
def edits1(word):
"All edits that are one edit away from `word`."4s管理
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]
transpos = [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]
inrts = [L + c + R for L, R in splits for c in letters]
return t(deletes + transpos + replaces + inrts)
def edits2(word):
"All edits that are two edits away from `word`."
return (e2 for e1 in edits1(word) for e2 in edits1(e1))
函数“correction（word）” 会返回“word”最近似的正确拼写内容：
>>> correction('speling')
'spelling'
>>> correction('korrectud')
'corrected'
⼀些概率知识
拼写检查器的⽬的是找到最近似错误输⼊“w”的正确拼写，但是对于⼀个错误拼写，其正确的候选者有很多（例如：“lates”应该被纠正为“late”呢，还是“lattes”呢？）。因此我们可以采取概率的思路，在错误拼写w出现的条件下，选择所有可能的备选纠正单词c中概率最⼤的。
由贝叶斯公式可得：
由于 对于每个待选择的c都是⼀样⼤⼩的，因此我们就忽略这个因素，最终公式变形为：
这个公式中由四个主要的部分：
选择机构：argmax
我们选择备选单词中概率最⾼的单词作为输出。
备选模型：
这⼀部分告诉我们考虑哪些单词作为备选。
语⾔模型：
单词c出现在语料库中的概率。例如，在⼀个英⽂语料库中，有7%的单词是“the”，那么
错误模型
当⽤户想输⼊C时，错输⼊成w的概率。例如， 应该远⼤于 。
我们⽤条件概率 和先验概率 这两个便于考虑和学习的因素替代了后延概率 ，这样问题更容易分析和解决。
python具体实现过程
1、选择机构 ：由python的max函数实现
2、备选模型 ：通过⼀些简单的操作（edits），⽣成⼀个t作为备选单词库。如：删除⼀个字母（deletions），交换两个字母的位置（transpos），把⼀个字母替换成另⼀个字母（replacement），增加⼀个字母（inrtion）。通过这⼏个常见的拼写错误，可以扩展出⼀系列的备选单词，形成⼀个t。
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]
transpos = [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]
inrts = [L + c + R for L, R in splits for c in letters]
return t(deletes + transpos + replaces + inrts)
《柳》古诗这是⼀个很⼤的t，因为对于⼀个长度为n的单词，会⽣成n个deletions，n-1个transpositions，26n个replacements，16（n+1）个inrtions，总共是（54n+25）个可能性。例如：
>>> len(edits1('somthing'))
442
联想主机编号
然⽽我们可以定义⼀个识别这些⽣成的备选单词正确性的模块，只匹配词典中存在的词。这个t将会变得很⼩，因为随机⽣成单词中，许多都是⾮法拼写的，并⾮真正存在。
def known(words):return t(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(t(edits2('something'))
90902
>>> known(edits2('something'))
{'ething', 'smoothing', 'something', 'soothing'}
>>> known(edits2('somthing'))
{'loathing', 'nothing', 'scathing', 'ething', 'smoothing', 'something', 'soothing', 'sorting'}
经过edits2（w）处理的单词，与原始单词w的edit distance（不知道怎么翻译，翻译为编辑距离？）
为2。
3、语⾔模型 我们通过统计在语料库中某个词（word）出现的频率来衡量⼀个词的先验概率，这⾥我们使⽤⼀个语料库来构建我们的语⾔模型。这个语料库含有100万个单词，⾥⾯包含⼀本书和⼀些常见词汇的列表。定义函数 word 来把语料⽂本打碎成⼀个⼀个单词的形式，然后构建⼀个计数器counter，统计每个词的出现频率，概率P代表了每个词出现的概率：
def words(text):return re.findall(r'\w+', text.lower())
WORDS = Counter(words(open('').read()))
def P(word, N=sum(WORDS.values())):return WORDS[word] / N
烤排骨
通过⼀些简单的NLP操作，我们可以看到这⾥有32192个单词，所有单词⼀共出现了1115504次，’the’是出现概率最⼤的，⼀共出现了79808次：
>>> len(WORDS)
32192
>>> sum(WORDS.values())
1115504
>>> st_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、错误模型
作者⼤⽜说写这个玩具代码的时候，在飞机上（⼈家坐个飞机都这么厉害。。。），没有互联⽹也没有数据，因此这个错误模型不是学习得到的，是通过定义⼀些特殊的规则来衡量的。因此，定义了⼀个函数candidates（word），根据优先级产⽣⼀个⾮空的候选单词序列：
优先级排序如下
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():
asrt correction('speling') == 'spelling'# inrt
asrt correction('korrectud') == 'corrected'# replace 2
asrt correction('bycycle') == 'bicycle'# replace
asrt correction('inconvient') == 'inconvenient'# inrt 2
asrt correction('arrainged') == 'arranged'# delete
asrt correction('peotry') =='poetry'# transpo
asrt correction('peotryy') =='poetry'# transpo + delete
asrt correction('word') == 'word'# known
asrt correction('quintesntial') == 'quintesntial'# unknown
asrt words('This is a TEST.') == ['this', 'is', 'a', 'test']
asrt Counter(words('This is a test. 123; A TEST this is.')) == (
Counter({'123': 1, 'a': 2, 'is': 2, 'test': 2, 'this': 2}))
asrt len(WORDS) == 32192
asrt sum(WORDS.values()) == 1115504
st_common(10) == [
('the', 79808),
('of', 40024),
('and', 38311),
('to', 28765),
('in', 22020),
('a', 21124),
('that', 12512),
('he', 12401),
('was', 11410),
('it', 10681)]
asrt WORDS['the'] == 79808
asrt P('quintesntial') == 0
asrt0.07 < P('the') < 0.08
return'unit_tests pass'
短信诈骗def spelltest(tests, verbo=Fal):
"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 verbo:
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 cond '
.format(good / n, n, unknown / n, n / dt))
def Testt(lines):
"Par '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(Testt(open(''))) # Development t
spelltest(Testt(open(''))) # Final test t
