基贝叶斯后验概率的拼写检查器实现 python

首先，我们从头开始说起。相信大家都学习过概率与数理统计这门课程，其中有一个贝叶斯公式，如下：

也就是条件概率公式。可以由下面的式子推得：

即，A与B同时发生的概率等于，B发生的概率乘以，在B发生的条件下A发生的概率。

好了，前面引出这个公式，就是为了解决我们的拼写检查器的问题。既然是检查器，就得把我们写错的词给改正确。怎么改呢？我们仔细来分析一下这个过程：

1． 首先，我们有一个词典，里面全包含的是正确的词。

2． 输入一个词，若这个词在词典里面有，其本身为正确，不需要改；若这个词是错误的，问题一：我们应该把它改成哪个词呢？

看下面的公式，

在我们输入的word是Wrong的情况下，我们要把他改成正确的词，哪个正确的词的概率高，我们就把他改成哪个词。即最大的那个词。假设你有一个备选正确词的集合set，你需要的就是计算set中每个词的。

问题二：怎么样确定备选正确词的集合set？

我们假定，错误词的产生是由下列几种情况产生：

1． 漏了一个字母，如你输入china，输成了chna

2． 两个相邻字母换位了，如chnia

3． 输错了一个字母，如chjna

4． 插入了一个字母，如 chijna

以上这四种操作，我们称之为china的一步变换。

那么反过来，如果我们输入了chijna，我们会得到一个由以上四种操作得到的另外的词，我们把这个集合作为备选正确词集合set

问题三：怎么样计算呢？

这里我们来分析，首先，对于set中的每个词都是一样的，因为每个词都是由wrong word经过一步变换得来，所以都相等。那么只剩下了，这个由我们去统计获得，哪些正确的词在我们的训练文本集中出现的概率高。

至此，问题已经全部分析完。下面python代码实现，其实在代码中，他使用了一次变换和二次变换所得到的词作为备选set。

#-*- coding:utf-8 -*-
import re, collections
def words(text): return re.findall('[a-z]+', text.lower())

#返回值是一个dict
def train(features):
    #model是一个字典
    model = collections.defaultdict(lambda: 0)
    for f in features:
        model[f] += 1
    return model

NWORDS = train(words(file("big.txt").read()))
alphabet = 'abcdefghijklmnopqrstuvwxyz'

#word is string
def edits1(word):
    splits = [(word[: i], word[i: ]) for i in range(len(word) + 1)]
    deletes = [ a + b[1: ] for a, b in splits if b]
    transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b) > 1]
    replaces = [a + c + b[1:] for a,b in splits for c in alphabet if b]
    inserts = [a + c + b for a,b in splits for c in alphabet]
    return set(deletes + transposes + replaces + inserts)

def know_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):
    candidates = known([word]) or known(edits1(word)) or know_edits2(word) or [word]
    return max(candidates, key = lambda w: NWORDS[w])

print correct('hte')
print correct('babyu')
    

语料库下载 ：big.txt

参考：http://www.oschina.net/code/snippet_218146_14045

严重推荐：http://norvig.com/spell-correct.html