朴素贝叶斯法理论学习和拼写检查器实战_拼写检查器的业务需求

贝叶斯定理是关于随机事件A和B的条件概率（或边缘概率）的一则定理。其中P(A|B)是在B发生的情况下A发生的可能性。

简单表达式为：         P(A|B)=P(A)P(B|A)/P(B)                 在机器学习中，我们将P(A|B)称为后验概率，P(A)称为先验概率

肯定会有人疑惑：为什么要把一个表达式拆为两个式子相乘，增加计算的难度？这必然是有原因，在实际问题中一些问题的P(A|B)可以说是毫无联系，无法直接测量，但是P(A)，P(B|A)/P(B)却是可以求解，进而求得P(A)。

朴素贝叶斯法基于贝叶斯定理的基础之上假设变量条件是相互独立的。

拼写检查器的实现：

目标需求分析：自动检查是否拼写错误并自动补全，比如：sorrw->sorry,somthin->somthing

符号说明：w为错误单词，c为理想的单词。P(c|w)为条件概率，

我们的目标便是确定一个c是的P(c|w)概率最大，则c就是我们所求的答案。但是像sorrw->sorry,somthin->somthing之类

从错误的单词下的确定正确单词的条件概率是明显无迹可寻，那么此时我们就需要用到贝叶斯公式：

P(c|w)=P(w|c)*P(c)/P(w),又因为对于所有的c，P(w)值相等，所有问题也可以简化为求一个c使得P(w|c)*P(c)概率最大，为了进一步简化问题

我们可以假设对于所有的c，将c写错为w的概率相同，那么问题进一步简化为求一个c使得P(c)的概率最大，P(c)=c在词库的出现次数/词库的单词总量。

下面开始实现程序：

big.txt中记录许多文章，单词，我们可以用来作为词库。

import re, collections
 
#我们利用一个叫 words 的函数把语料中的单词全部抽取出来, 转成小写, 并且去除单词中间的特殊符号
# 单词就会成为字母序列, don't 就变成 don 和 t 了，为了简化操作我们就忽略这个细节
def words(text): return re.findall('[a-z]+', text.lower())
 
def train(features):
    #defaultdict类的初始化函数接受一个类型作为参数，当所访问的键不存在的时候，可以实例化一个值作为默认值,及所有键的初始值都为1
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model
#NWORDS为一个字典 {单词：次数}
NWORDS = train(words(open('big.txt').read()))

相关论文显示，80-95%的拼写错误跟想要拼写的单词都只有1个编辑距离。可是我很快发现把270个错误拼写组成的语料库进行测试，发现只有76%的编辑距离是1。可能我测试的数据要比典型的错误要难。不管怎样，我觉得只考虑1次编辑距离还不够好。所以我们要考虑两次编辑距离。2次编辑距离变换也很容易，只需要进行两次edit1处理就好了。 

这些说起来容易，但是我们又面临了运算问题。len(edits2(‘something’))的值是114,324。但是，我们确实得到了很好的结果：270个测试例子中，只有3个的编辑距离大于2。我们可以做一个优化，我们最后的结果集合中只保留确认为已知单词的。也就是说，我们需要考虑所有的可能性，但是不用建立很大的一个集合。

#字母表 用于编辑距离函数的插入
alphabet = 'abcdefghijklmnopqrstuvwxyz'
#返回所有与单词 w 编辑距离为 1 的集合
def edits1(word):
    n = len(word)
    return set([word[0:i] + word[i + 1:] for i in range(n)] +                             # 减少一个字母
               [word[0:i] + word[i + 1] + word[i] + word[i + 2:] for i in range(n - 1)] +  # 调换相邻间两个字母顺序，ps：人们应该不会将距离远的俩字母写反！
               [word[0:i] + c + word[i + 1:] for i in range(n) for c in alphabet] +       # 替换一个字母
               [word[0:i] + c + word[i:] for i in range(n + 1) for c in alphabet])        # 插入一个字母
 
#返回所有与单词 w 编辑距离为 2 的集合
#在这些编辑距离小于2的词中间, 只把那些正确的词作为候选词
def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

剩下的操作就是找到概率最大的正确单词了：

#返回在字典中可以找到的编辑单词
def known(words): return set(w for w in words if w in NWORDS)
 
def correct(word):
    # 为了简便我们采用python的短路表达式，如果known(set)非空, candidate 就会选取这个集合,
    #  而不会再继续计算后面的，当然我们也可以将代码写成if-else形式
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=lambda w: NWORDS[w])
 
if __name__ == '__main__':
    print(correct('somethin'))

something

全部代码：

import re, collections
 
#我们利用一个叫 words 的函数把语料中的单词全部抽取出来, 转成小写, 并且去除单词中间的特殊符号
# 单词就会成为字母序列, don't 就变成 don 和 t 了，为了简化操作我们就忽略这个细节
def words(text): return re.findall('[a-z]+', text.lower())
 
def train(features):
    #defaultdict类的初始化函数接受一个类型作为参数，当所访问的键不存在的时候，可以实例化一个值作为默认值,及所有键的初始值都为1
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model
#NWORDS为一个字典 {单词：次数}
NWORDS = train(words(open('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)] +                             # 减少一个字母
               [word[0:i] + word[i + 1] + word[i] + word[i + 2:] for i in range(n - 1)] +  # 调换相邻间两个字母顺序，ps：人们应该不会将距离远的俩字母写反！
               [word[0:i] + c + word[i + 1:] for i in range(n) for c in alphabet] +       # 替换一个字母
               [word[0:i] + c + word[i:] for i in range(n + 1) for c in alphabet])        # 插入一个字母
 
#返回所有与单词 w 编辑距离为 2 的集合
#在这些编辑距离小于2的词中间, 只把那些正确的词作为候选词
def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)
 
#返回在字典中可以找到的编辑单词
def known(words): return set(w for w in words if w in NWORDS)
 
def correct(word):
    # 为了简便我们采用python的短路表达式，如果known(set)非空, candidate 就会选取这个集合,
    #  而不会再继续计算后面的，当然我们也可以将代码写成if-else形式
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=lambda w: NWORDS[w])
 
if __name__ == '__main__':
    print(correct('somethin'))

总结：整个程序只有21行代码，却实现了如此强大的功能。数学思想对程序是极其重要的。

拼写检查器是国外的一位大佬所写，原文翻译地址：https://blog.csdn.net/u013830811/article/details/46539919