拼写正确，记为c(correct) 拼写错误，记为w(wrong)
根据贝叶斯定理可得：
对于所有的备选项c来说，w都是相同的，因此可将上式简化为：
所以，实际上可以看成是求式（3）的最大值
P(c)的含义是，某个正确的词的出现“概率”，它可以用“频率”代替。如果我们有一个足够大的文本库，那么这个文本库中每个单词的出现频率，就相当于它的发生概率。某个词的出现频率越高，P(c)就越大。
P(w|c)的含义是，在试图拼写c的情况下，出现拼写错误w的概率。这需要统计数据的支持，但是为了简化问题，我们假设两个单词在字形上越接近，就越有可能拼错，P(w|c)就越大。
举例来说，相差一个字母的拼法，就比相差两个字母的拼法，发生概率更高。
例如，如果你想拼写单词Serendipity，那么错误拼写成Serendipitu（相差一个字母）的可能性，就比拼成Serendipituu要高（相差两个字母）。
所以，我们只要找到与输入单词在字形上最相近的那些词，再在其中挑出出现频率最高的一个，就能实现P(w|c)*P(c)的最大值。
实现代码如下：
import refrom collections import Counterdef words(text): return re.findall(r'\w+', text.lower())WORDS = Counter(words(open('big.txt').read()))def P(word, N=sum(WORDS.values())):"Probability of `word`."return WORDS[word] / Ndef 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 subset of `words` that appear in the dictionary of WORDS."return set(w for w in words if w in WORDS)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]transposes = [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]inserts = [L + c + R for L, R in splits for c in letters]return set(deletes + transposes + replaces + inserts)def edits2(word):"All edits that are two edits away from `word`."return (e2 for e1 in edits1(word) for e2 in edits1(e1))################ Test Codedef unit_tests():assert correction('speling') == 'spelling' # insertassert correction('korrectud') == 'corrected' # replace 2assert correction('bycycle') == 'bicycle' # replaceassert correction('inconvient') == 'inconvenient' # insert 2assert correction('arrainged') == 'arranged' # deleteassert correction('peotry') =='poetry' # transposeassert correction('peotryy') =='poetry' # transpose + deleteassert correction('word') == 'word' # knownassert correction('quintessential') == 'quintessential' # unknownassert 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) == 32192assert sum(WORDS.values()) == 1115504assert WORDS.most_common(10) == [('the', 79808),('of', 40024),('and', 38311),('to', 28765),('in', 22020),('a', 21124),('that', 12512),('he', 12401),('was', 11410),('it', 10681)]assert WORDS['the'] == 79808assert P('quintessential') == 0assert 0.07 < P('the') < 0.08return 'unit_tests pass'def spelltest(tests, verbose=False):"Run correction(wrong) on all (right, wrong) pairs; report results."import timestart = time.clock()good, unknown = 0, 0n = len(tests)for right, wrong in tests:w = correction(wrong)good += (w == right)if w != right:unknown += (right not in WORDS)if verbose:print('correction({}) => {} ({}); expected {} ({})'.format(wrong, w, WORDS[w], right, WORDS[right]))dt = time.clock() - startprint('{:.0%} of {} correct ({:.0%} unknown) at {:.0f} words per second '.format(good / n, n, unknown / n, n / dt))def Testset(lines):"Parse '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()]if __name__ == '__main__':print(unit_tests())spelltest(Testset(open('spell-testset1.txt')))spelltest(Testset(open('spell-testset2.txt')))
