Python编程

Python编程 第四版中文版 ...

↑我也要推荐

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

发布时间:2011-07-02 04:43:30, 关注:+5407, 赞美:+9, 不爽:+4

原始出处: Bony.Miao's Blog

输入:测试文档,具有一定规模的字典
输出:测试本当可能错误的单词并推荐可能正确的单词
思路:统计测试文档中每个单词的频度,如果单词的频度小于一定阈值,则遍历字典,进行相似度计算并推荐相似度最强的那个正确单词。这样的思路的优点是简单易懂,取得的效果也较好,但存在以下缺点:

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'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]]:
 

如果你觉得本站对你有帮助,欢迎向本站赞助 :P

使用支付宝捐赠

Copyright© Python4cn(news, jobs) simple-is-better.com, 技术驱动:powered by web.py 空间主机:Webfaction

版权申明:文章转载已注明出处,如有疑问请来信咨询。本站为 python 语言推广公益网站,与 python 官方没有任何关系。

联系/投搞/留言: en.simple.is.better@gmail.com 向本站捐赠