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

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

阅读量：7117 次

发布时间：2019-06-28

本文共 2525 字，大约阅读时间需要 8 分钟。

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

2011-06-10 20:15:26|  分类： |  标签：         |字号大中小

输入：测试文档，具有一定规模的字典

输出：测试本当可能错误的单词并推荐可能正确的单词

思路：统计测试文档中每个单词的频度，如果单词的频度小于一定阈值，则遍历字典，进行相似度计算并推荐相似度最强的那个正确单词。这样的思路的优点是简单易懂，取得的效果也较好，但存在以下缺点：

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