1. 拼写检查器基本原理—基于贝叶斯概率公式
问题：
在所有正确的拼写词中, 我们想要找一个正确单词 c, 使得其对于错误单词w 的条件概率最大。
问题求解：
P(c|w) = P(w|c) P( c ) / P(w)
比如：appla是条件w，apple和apply是正确的词c，对于apple和apply来说P(w)都是一样的，所以我们在上式中忽略它, 写成: P(w|c) P( c )
- P( c )表示文章中出现这个正确拼写的词 c 的概率, 也就是说, 在英语文章中, c 出现的概率有多大。
假设可以认为单词在文章中出现的概率越大，则正确拼写的概率就越大，可以用单 词出现次数来代替这个量。好比说, 英语中出现 the 的概率 P(‘the’) 就相对高, 而出 现 P(‘zxzxzxzyy’) 的概率接近0(假设后者也是一个词的话).
- P(w|c), 在用户想键入 c 的情况下敲成 w 的概率。这个是代表用户会以多大的概率把 c 敲错成 w。
2. 构建单词集并统计单词数
import re • 1
# 我们导入一个比较大的文本集，并且统计文本中各单词数量 text = open('text.txt').read()
# 展示文本中前1000个字符 text[:1000]
'The Project Gutenberg EBook of The Adventures of Sherlock Holmes\nby Sir Arthur Conan Doyle\n(#15 in our series by Sir Arthur Conan Doyle)\n\nCopyright laws are changing all over the world. Be sure to check the\ncopyright laws for your country before downloading or redistributing\nthis or any other Project Gutenberg eBook.\n\nThis header should be the first thing seen when viewing this Project\nGutenberg file. Please do not remove it. Do not change or edit the\nheader without written permission.\n\nPlease read the "legal small print," and other information about the\neBook and Project Gutenberg at the bottom of this file. Included is\nimportant information about your specific rights and restrictions in\nhow the file may be used. You can also find out about how to make a\ndonation to Project Gutenberg, and how to get involved.\n\n\n**Welcome To The World of Free Plain Vanilla Electronic Texts**\n\n**eBooks Readable By Both Humans and By Computers, Since 1971**\n\n*****These eBooks Were Prepared By Thousan'
# 将文本中所有的单词取出，并将其转小写，只保留a-z字符 words = re.findall('[a-z]+', text.lower())
# 统计每个单词的出现次数 dic_words = {} for t in words: dic_words[t] = dic_words.get(t,0) + 1
# 展示前10个单词及其数目 list(dic_words.items())[:10]
[('the', 80030), ('project', 288), ('gutenberg', 263), ('ebook', 87), ('of', 40025), ('adventures', 17), ('sherlock', 101), ('holmes', 467), ('by', 6738), ('sir', 177)]
3. 计算单词间的距离，并返回候选单词
3.1 编辑距离:
两个词之间的编辑距离定义：使用了几次插入(在词中插入一个单字母), 删除(删除一个单字母), 交换(交换相邻两个字母), 替换(把一个字母换成另一个)的操作从一个词变到另一个词.
3.2 计算与拼写单词编辑距离为1、2的正确单词
统计编辑距离为1的单词集
# 字母表 alphabet = 'abcdefghijklmnopqrstuvwxyz' #返回所有与单词 word 编辑距离为 1 的集合 def one_edit(word): n = len(word) # 1次删除操作的单词集 del_words = [word[0:i]+word[i+1:] for i in range(n)] # 1次交换操作的单词集 trans_words = [word[0:i]+word[i+1]+word[i]+word[i+2:] for i in range(n-1)] # 1次替换操作的单词集 alter_words = [word[0:i]+c+word[i+1:] for i in range(n) for c in alphabet] # 1次插入操作的单词集 insert_words = [word[0:i]+c+word[i:] for i in range(n+1) for c in alphabet] one_edit_words = set(del_words + trans_words + alter_words + insert_words) return one_edit_words
统计编辑距离为2的单词集
def two_edit(word): two_edit_words = set() for e1 in one_edit(word): for e2 in one_edit(e1): two_edit_words.add(e2) return two_edit_words
e1 = one_edit('something') e2 = two_edit('something') len(e1) + len(e2)
114818
与单词something 编辑距离为1或者2的单词居然达到了 114818 个，这里我们可以进行优化，仅选取那些正确的词作为候选词。
3.3 将编辑距离小于2的词中,选正确的词作为候选词
all_edit_words = e1 | e2 correct_word = [] dict_words = set(dic_words.keys()) for word in all_edit_words: if word in dict_words: correct_word.append(word) print(correct_word)
['soothing', 'seething', 'something', 'smoothing']
我们可以看到,优化之后只返回 4 个单词: [‘soothing’, ‘seething’, ‘something’, ‘smoothing’]
4. 编写单词拼写检查器
P(w|c)求解：正常来说把一个元音拼成另一个的概率要大于辅音 (因为人常常把 hello 打成 hallo 这样); 把单词的第一个字母拼错的概率会相对小, 等等。
但是为了简单起见, 我们选择了一个简单的方法:
1. 编辑距离为1的正确单词比编辑距离为2的优先级高,
2. 编辑距离为0的正确单词优先级比编辑距离为1的高.
一般把hello打成hallo的可能性比把hello打成halo的可能性大。
4.1 定义拼写检查器-----返回最优单词
def known(words): # 返回正确的单词集合 w = set() for word in words: if word in dic_words: w.add(word) return w # 先计算编辑距离，再根据编辑距离找到最匹配的单词 def correct(word): # 获取候选单词 # 判断单词是否正确,若正确则直接返回 if word in dic_words: return word # 如果known(set)非空, candidates 就会选取这个集合, 而不继续计算后面的，优先为1次编辑距离>2次编辑距离 candidates = known(one_edit(word)) or known(two_edit(word)) or word # 若字典中不存在相近的词，则直接返回该单词 if word == candidates: return word # 返回频率最高的词 max_num = 0 for c in candidates: if dic_words[c] >= max_num: max_num = dic_words[c] candidate = c return candidate
4.2 拼写器使用举例
correct('learw') • 1
'learn' • 1
correct('tess')
'less' • 1
correct('appl') • 1
'apply'
correct('fdsfsdgergg') • 1
'fdsfsdgergg'
