一. 拼写纠正项目概述

1.1 拼写错误概述

image.png

问题:
我们看到用户输入了一个不在字典中的单词，我们需要去猜测：“这个家伙到底真正想输入的单词是什么呢？

P(我们猜测他想输入的单词| 他实际输入的单词)

用户实际输入的单词记为D （D 代表Data ，即观测数据）

1. 猜测1：P(h1 | D)，猜测2：P(h2 | D)，猜测3：P(h1 | D) 。。。
   统一为：P(h | D)

2. P(h | D) = P(h) * P(D | h) / P(D)

3. 对于不同的具体猜测h1 h2 h3 .. ，P(D) 都是一样的，所以在比较P(h1 | D) 和P(h2 | D) 的时候我们可以忽略这个常数

4. P(h | D) ∝ P(h) * P(D | h)
   对于给定观测数据，一个猜测是好是坏，取决于“这个猜测本身独立的可能性大小（先验概率，Prior ）”和“这个猜测生成我们观测到的数据的可能性大小。

1.2 贝叶斯方法计算

P(h) * P(D | h)，P(h) 是特定猜测的先验概率

比如用户输入tlp，那到底是top 还是tip ？这个时候，当最大似然不能作出决定性的判断时，先验概率就可以插手进来给出指示——“既然你无法决定，那么我告诉你，一般来说top 出现的程度要高许多，所以更可能他想打的是top ”

1.3 模型比较理论

最大似然：最符合观测数据的（即P(D | h) 最大的）最有优势

奥卡姆剃刀：P(h) 较大的模型有较大的优势

掷一个硬币，观察到的是“正”，根据最大似然估计的精神，我们应该猜测这枚硬币掷出“正”的概率是1，因为这个才是能最大化P(D | h) 的那个猜测

如果平面上有N 个点，近似构成一条直线，但绝不精确地位于一条直线上。这时我们既可以用直线来拟合（模型1），也可以用二阶多项式（模型2）拟合，也可以用三阶多项式（模型3），特别地，用N-1 阶多项式便能够保证肯定能完美通过

奥卡姆剃刀：越是高阶的多项式越是不常见

二. 项目实战

2.1 数据源介绍

一个12万行数据的英文文档，里面包含常用的英文单词。

image.png

2.2 一些概念

编辑距离:
两个词之间的编辑距离定义为使用了几次插入(在词中插入一个单字母), 删除(删除一个单字母), 交换(交换相邻两个字母), 替换(把一个字母换成另一个)的操作从一个词变到另一个词.

正常来说把一个元音拼成另一个的概率要大于辅音 (因为人常常把 hello 打成 hallo 这样); 把单词的第一个字母拼错的概率会相对小, 等等.但是为了简单起见, 选择了一个简单的方法: 编辑距离为1的正确单词比编辑距离为2的优先级高, 而编辑距离为0的正确单词优先级比编辑距离为1的高.

2.3 代码

代码:

import re, collections

# 把语料中的单词全部抽取出来, 转成小写, 并且去除单词中间的特殊符号
def words(text): return re.findall('[a-z]+', text.lower())

# 要是遇到我们从来没有过见过的新词怎么办.
# 假如说一个词拼写完全正确, 但是语料库中没有包含这个词, 从而这个词也永远不会出现在训练集中.
# 于是, 我们就要返回出现这个词的概率是0. 这个情况不太妙,
# 因为概率为0这个代表了这个事件绝对不可能发生, 而在我们的概率模型中, 我们期望用一个很小的概率来代表这种情况. lambda: 1
def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model

NWORDS = train(words(open('E:/file/big.txt').read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'

# 编辑距离:
# 两个词之间的编辑距离定义为使用了几次插入(在词中插入一个单字母), 删除(删除一个单字母),
# 交换(交换相邻两个字母), 替换(把一个字母换成另一个)的操作从一个词变到另一个词.

#返回所有与单词 w 编辑距离为 1 的集合
def edits1(word):
    n = len(word)
    return set([word[0:i]+word[i+1:] for i in range(n)] +                     # deletion
               [word[0:i]+word[i+1]+word[i]+word[i+2:] for i in range(n-1)] + # transposition
               [word[0:i]+c+word[i+1:] for i in range(n) for c in alphabet] + # alteration
               [word[0:i]+c+word[i:] for i in range(n+1) for c in alphabet])  # insertion

#与 something 编辑距离为2的单词居然达到了 114,324 个
#优化:在这些编辑距离小于2的词中间, 只把那些正确的词作为候选词,只能返回 3 个单词: ‘smoothing’, ‘something’ 和 ‘soothing’

#返回所有与单词 w 编辑距离为 2 的集合
#在这些编辑距离小于2的词中间, 只把那些正确的词作为候选词
def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

# 判断单词是否在词频中,并返回字母
# 例如输入'knon' 返回 {'k', 'n', 'o'}
def known(words): return set(w for w in words if w in NWORDS)

# 编辑距离为1的正确单词比编辑距离为2的优先级高, 而编辑距离为0的正确单词优先级比编辑距离为1的高.
def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=lambda w: NWORDS[w])

# 输出词频
print(NWORDS)
print("####################################")

#返回所有与单词 knon 编辑距离为 1 的集合
print(edits1('knon'))
print("####################################")

# 判断单词是否在词频中
print(known('knon'))
print("####################################")

#返回所有与单词 knon 编辑距离为 2 的集合
print(known_edits2('knon'))
print("####################################")

# 输出knon的拼写检查
print(correct('knon'))

测试记录:

defaultdict(<function train.<locals>.<lambda> at 0x00000000038652F0>, {'the': 80031, 'project': 289, 'gutenberg': 264, 'ebook': 88, 'of': 40026, 'adventures': 18, 'sherlock': 102, 
......
......
'wiktionary': 3, 'wiki': 2})
####################################
{'knzon', 'knton', 'knom', 'kncon', 'knorn', 'dknon', 'knop', 'knond', 'kkon', 'knonf', 'kaon', 'onon', 'kncn', 'koon', 'knodn', 'knno', 'knoq', 'tknon', 'unon', 'knocn', 'jknon', 'mknon', 'knoh', 'kvnon', 'fnon', 'knoln', 'knong', 'knpon', 'knoe', 'knoi', 'knoan', 'knofn', 'knopn', 'kmnon', 'nknon', 'knxon', 'kyon', 'knons', 'bnon', 'hnon', 'knoo', 'knoy', 'kndon', 'knyn', 'uknon', 'knovn', 'gknon', 'knonc', 'knln', 'kntn', 'knony', 'knok', 'know', 'knozn', 'kion', 'klnon', 'kdon', 'knjn', 'rknon', 'knun', 'kdnon', 'dnon', 'kunon', 'ynon', 'knzn', 'xknon', 'kqon', 'kngn', 'ktnon', 'knyon', 'knaon', 'pnon', 'knona', 'wknon', 'knoa', 'khon', 'knoc', 'bknon', 'yknon', 'tnon', 'knuon', 'jnon', 'knxn', 'kpnon', 'keon', 'kznon', 'knomn', 'kfnon', 'kqnon', 'knor', 'kwnon', 'knonm', 'knonq', 'anon', 'kzon', 'knion', 'krnon', 'kneon', 'knrn', 'knou', 'knoni', 'kron', 'pknon', 'knojn', 'knonn', 'knoen', 'vnon', 'snon', 'qknon', 'knob', 'kanon', 'ksnon', 'knont', 'kbnon', 'kson', 'kon', 'kcon', 'sknon', 'knvn', 'kwon', 'kmon', 'kjon', 'oknon', 'known', 'cknon', 'aknon', 'wnon', 'knonj', 'kvon', 'knron', 'knonk', 'rnon', 'non', 'knwn', 'kinon', 'knhon', 'knogn', 'knvon', 'knonp', 'knonw', 'lknon', 'knan', 'knod', 'knonx', 'knonz', 'knonb', 'knoj', 'znon', 'xnon', 'knjon', 'knox', 'knoon', 'kynon', 'kpon', 'knonh', 'kfon', 'knoin', 'kxon', 'hknon', 'qnon', 'knoz', 'knonu', 'knmn', 'kxnon', 'knohn', 'zknon', 'knnn', 'kgon', 'kcnon', 'vknon', 'knoyn', 'knog', 'iknon', 'kuon', 'knobn', 'knosn', 'knoxn', 'knonv', 'nnon', 'knotn', 'knkn', 'konon', 'knen', 'knokn', 'knov', 'knbn', 'knwon', 'mnon', 'knqn', 'eknon', 'kno', 'knlon', 'knoun', 'knone', 'enon', 'knoqn', 'khnon', 'knon', 'knson', 'knn', 'kenon', 'knfn', 'inon', 'knol', 'fknon', 'kton', 'kknon', 'knos', 'knono', 'cnon', 'gnon', 'knot', 'nkon', 'kgnon', 'knhn', 'klon', 'knqon', 'kbon', 'knonr', 'knkon', 'knsn', 'knonl', 'kndn', 'knfon', 'knof', 'knnon', 'konn', 'knin', 'knmon', 'kngon', 'knpn', 'kjnon', 'knbon', 'lnon'}
####################################
{'k', 'o', 'n'}
####################################
{'know', 'ken', 'known', 'moon', 'knock', 'knobs', 'boon', 'pon', 'on', 'union', 'knee', 'non', 'yon', 'no', 'lyon', 'khan', 'son', 'ton', 'kin', 'nor', 'knots', 'kann', 'lion', 'nod', 'knoll', 'not', 'nos', 'noun', 'ion', 'noon', 'klan', 'canon', 'von', 'nov', 'ano', 'akron', 'mon', 'upon', 'anon', 'knox', 'hon', 'knew', 'iron', 'ann', 'con', 'none', 'eton', 'knot', 'don', 'snow', 'keen', 'leon', 'inn', 'nom', 'onion', 'soon', 'knob', 'won', 'dron', 'icon', 'anton', 'knows', 'nan', 'knit', 'nun', 'now'}
####################################
know