一个简单的基于编辑距离的英文单词查错（Python） Muilpin.Miao的日志网易博客

一个简单的基于编辑距离的英文单词查错（Python） - Muilpin.Miao的日志 - 网易博客

一个简单的基于编辑距离的英文单词查错（Python）
2011-06-10 20:15:26|  分类：数据挖掘 |  标签：单词拼错   编辑距离   python  规则   |字号大中小订阅
输入：测试文档，具有一定规模的字典
输出：测试本当可能错误的单词并推荐可能正确的单词
思路：统计测试文档中每个单词的频度，如果单词的频度小于一定阈值，则遍历字典，进行相似度计算并推荐相似度最强的那个正确单词。这样的思路的优点是简单易懂，取得的效果也较好，但存在以下缺点：
1.前提假设不够充分；我们假设认为一个人不会重复写错的某个单词，但这种假设不能概括所有的情况；
2.阈值的选取；阈值应该随着测试文档单词的数量进行自适应，而非固定；
3.时间复杂度高；查错阶段每次需要遍历字典；

首先，对测试文档进行预处理。可以针对读取数据的特征采用正则表达式进行预处理，例如：
#读取测试文档，计算词频
test=open('test.txt','r') #打开测试文件
contend=test.read()
words=re.sub(r'[^\w]','|',contend).split('|') #使用正则表达式，匹配非字母与下划线的字符，使用’|‘代替
其次，统计测试文档的词频。
wc={}
for word in words:
   word=word.lower()
   wc.setdefault(word,0)
   wc[word]+=1
最后，将词频小于阈值的单词进入词典查错并推荐相似度高的单词。
for d in wc:
   if wc[d]<2: #假设阈值为2，即当频度为1时，将单词进入字典里匹配
   if d not in train:
   if d.rstrip("s ing") not in train: #基于规则再筛选，增加规则可以在这里增加
   rec_word=''
   mind=999999999
   for w in train: #查找字典与其最相似的单词进行推荐
   dis=word_similarity(d,w)
   if dis<mind:
   mind=dis
   rec_word=w
   print "The wrong word is \"%s\" --> %s" % (d,rec_word)
注意，里面还可以使用正则表达式扩展一些规则，提高准确率与效率
以某篇英语6级作文作为输入文档进行测试，输出结果为：
The wrong word is "quicker" --> quicken
The wrong word is "achieving" --> chewing
Used Time: 10.750000s
显然：时间复杂度是非常高的，但效果还是挺好的！
编辑距离：用来计算两个字符串的相似度，可以理解为步骤数，步骤数=通过三个基本字符操作（增加，删除，更改）将源字符串转化成目标字符串的步骤数；如abc转化为abcd只需增加一个d，因此，步骤数=1，详细请参考具体文献；Python实现的具体代码如下：
def word_similarity(word1,word2):
   if len(word1)==0 | len(word2)==0:return 99999999
   juzhen=[[0 for j in range(len(word1)+1)] for i in range(len(word2)+1)]
   for i in range(len(word2)+1):
juzhen[i][0]=i
   for j in range(len(word1)+1):
juzhen[0][j]=j
   for i in range(1,len(word2)+1):
   for j in range(1,len(word1)+1):
   if word2[i-1]==word1[j-1]:cost=0
   else:cost=1
   juzhen[i][j]=min(juzhen[i-1][j]+1,juzhen[i][j-1]+1,juzhen[i-1][j-1]+cost)

   return juzhen[len(word2)][len(word1)]
非常神奇的编辑距离算法，感谢俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念；

后记1--加速：最后时间复杂度太高了，经过发现，消耗支出在于纠错：每个单词都需要与字典中6万多个单词计算编辑距离。因此，采取了一种措施：先将6万多个单词按照首字母分类，这样，出错单词就不需要将字典所有单词进行匹配，只匹配与自己首字母一样的那一块即可，速度定性估计提高了26倍。缺点是：如果第一个字母出错，那么纠错的正确率就会降低，因为纠错时假设首字母是对的；
后记2--提高准确率：另外，增加了一些普遍通用的规则，如以'ing'结尾的单词用'e'代替'ing'，再进入词典查找。并没有增加不规则单词变换的检查；普遍通用规则代码如下：
if d not in first_word[d[0]]:
   if re.sub(r'es

,'',d) not in first_word[d[0]] and re.sub(r's ,'',d) not in first_word[d[0]] and\

re.sub(r'd ,'',d) not in first_word[d[0]] and\

re.sub(r'er ,'',d) not in first_word[d[0]] and\

re.sub(r'ing ,'',d) not in first_word[d[0]] and\

re.sub(r'ed ,'',d) not in first_word[d[0]] and\

re.sub(r'ied ,'y',d) not in first_word[d[0]] and\

re.sub(r'ing ,'e',d) not in first_word[d[0]] and re.sub(r'ies ,'y',d) not in first_word[d[0]]:

一个简单的基于编辑距离的英文单词查错（Python） Muilpin.Miao的日志 网易博客

一个简单的基于编辑距离的英文单词查错（Python）

一个简单的基于编辑距离的英文单词查错（Python） Muilpin.Miao的日志网易博客