Naive Bayes拼写纠正器

P(B|A)=P(B)*P(A|B)/P(A)

A为输入的单词 B为预测输出的单词。
对于输入的模糊单词A，比如有10个和A的编辑距离为1或2的单词满足条件，则统计这10个单词在一个大型语料库中出现的概率，出现概率最高的单词可以作为预测输出。
预处理：对该语料库先进行分词操作，构造字典，便于统计概率，此处求得的概率为P(B),也叫先验概率。
最大似然估计：求P(A|B)最大出现的概率。
拼写纠正器里面只提取了编辑距离为 2 以内的所有已知单词。这是为了避免去遍历字典中每个单词计算它们的 P(h) * P(D | h) ，但这种做法为了节省时间带来了一些误差。但话说回来难道我们人类真的回去遍历每个可能的单词来计算他们的后验概率吗？不可能。实际上，根据认知神经科学的观点，我们首先根据错误的单词做一个 bottom-up 的关联提取，提取出有可能是实际单词的那些""候选单词""，这个提取过程就是所谓的基于内容的提取，可以根据错误单词的一些模式片段提取出有限的一组候选，非常快地缩小的搜索空间（比如我输入 explaination ，单词里面就有充分的信息使得我们的大脑在常数时间内把可能性 narrow down 到 explanation 这个单词上。

import re
from collections import Counter

# 返回big.txt中的每一个单词，以列表形式返回，避免大小写不同认为单词不同
def words(text):
    return re.findall(r'\w+', text.lower())

# 构建WORD字典结构 word:n   n为出现次数
WORDS = Counter(words(open('spell amend/big.txt').read()))


def P(word, N=sum(WORDS.values())):
    "Probability of `word`."
    return WORDS[word] / N

# 输入word返回最有可能的单词
def correction(word):
    return max(candidates(word), key=P)

# 短路特性 1.文本中现有的词 2.距离为1的词集合 3.距离为2的词集合  4.返回词本身
def candidates(word):
    return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])


def known(words):
    # 返回在WORDS字典中的子集合
    return set(w for w in words if w in WORDS)

# 生成与word的编辑距离为1的单词
def edits1(word):
    letters = 'abcdefghijklmnopqrstuvwxyz'
    # 将word按每一位切割成一组
    splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
    # 删除word的每一位
    deletes = [L + R[1:] for L, R in splits if R]
    # 依次交换word的临近两位 产生新的单词
    transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R) > 1]
    # 依次将word的每一位用26个字母替换
    replaces = [L + c + R[1:] for L, R in splits if R for c in letters]
    # 依次用26个字母插入word的每一位
    inserts = [L + c + R for L, R in splits for c in letters]
    # 合并集合
    return set(deletes + transposes + replaces + inserts)

# 生成与word的编辑距离为2的单词
def edits2(word):
    # 产生距离为1的单词集合e1 通过e1产生e2
    return (e2 for e1 in edits1(word) for e2 in edits1(e1))


################ Test Code

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) == 32198
    assert sum(WORDS.values()) == 1115585
    assert WORDS.most_common(10) == [
        ('the', 79809),
        ('of', 40024),
        ('and', 38312),
        ('to', 28765),
        ('in', 22023),
        ('a', 21124),
        ('that', 12512),
        ('he', 12401),
        ('was', 11410),
        ('it', 10681)]
    assert WORDS['the'] == 79809
    assert P('quintessential') == 0
    assert 0.07 < P('the') < 0.08
    return 'unit_tests pass'



if __name__ == '__main__':
    print(unit_tests())

    print(correction("hellol"))
    print(correction('jokess'))