python脚本实现英文单词纠错_英语单词纠错api

GitHub地址：https://github.com/fanorfan/EnglishWordErrorCorrection

单词纠错算法

1. 准备一个语料库，里面包含的内容如下：

• Gutenberg语料库数据
• 维基词典
• 英国国家语料库中的最常用单词列表

下载地址：https://github.com/fanorfan/EnglishWordErrorCorrection/blob/master/big.txt

2. 取出语料库中所有的单词，并统计其出现的次数。

3. 对于一个给定的单词，不管其是否拼写错误，依次找到和它编辑距离为0、1、2的单词。

4. 考虑以下三个优先顺序来挑选出该单词一个最佳纠正结果：

		1).	编辑距离为0的单词（即该单词本身） >	编辑距离为1的单词 > 编辑距离为2的单词
		2).	是否在语料库中出现（最起码得是一个正确的存在的单词）
		3).	语料库中出现的次数
1
2
3

python实现

1. 英文单词纠错（CorrectWords.py）

1. 语料库的处理

import re, collections

# text中所有单词转为小写形式并匹配
# text示例："The Project Gutenberg EBook of The Adventures of Sherlock Holmes\nby Sir Arthur Conan Doyle"
def tokens(text):
    return re.findall("[a-z]+", text.lower())

# 打开语料库文件
with open('big.txt', 'r') as f:
    words = tokens(f.read())
1
2
3
4
5
6
7
8
9
10

2. 取出语料库中所有的单词，并统计其出现的次数。

# 统计语料库中每个单词的个数
word_counts = collections.Counter(words)
1
2

3. 单词纠正
   创建一个单词纠正函数如下：

# text示例：'fianlly helloa cta'
def correct_text_generic(text):
    """
    纠正匹配到的单词中所有拼写错误的单词
    """
    return re.sub('[a-zA-Z]+', correct_match, text)
1
2
3
4
5
6

correct_match参数是一个回调函数，来执行对匹配到的单词的操作，我们创建这个函数如下：

def correct_match(match):
    """
    替换的回调函数
    """
	# 匹配到的单词依次取出,第一次取'fianlly'
    word = match.group()

    def case_of(text):
        """
            返回小写
        """
        return (str.upper if text.isupper() else
                str.lower if text.islower() else
                str.title if text.istitle() else
                str)

    return case_of(word)(correct(word.lower()))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

case_of(word)()的第二个括号中需要一个函数，我们创建这个函数如下：

def correct(word):
    """
        获得输入单词的最佳正确拼写
    """
    # 1.是否在语料库中出现

    # 2.单词的优先顺序：编辑距离为0的单词（即该单词本身） > 编辑距离为1的单词 > 编辑距离为2的单词

    # 3.在语料库中的出现次数

    candidates = (known(edits0(word)) or
                  known(edits1(word)) or
                  known(edits2(word)) or
                  {word})
    return max(candidates, key=word_counts.get)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

candidates变量来保存符合1). 2).两个条件的单词,最后返回其中在语料库中出现次数最多的单词。

2). 是否在语料库中出现对应的函数如下：

def known(words):
    """
        判断words中的每一个单词是否在语料库中出现，若出现就返回此单词
    """
    return {w for w in words if w in word_counts}
1
2
3
4
5

1). 编辑距离为0的单词（即该单词本身） > 编辑距离为1的单词 > 编辑距离为2的单词 对应的函数如下：

def edits0(word):
    """
        返回跟输入单词是0距离的单词,也就是自己
    """
    return {word}


def edits1(word):
    """
        返回跟输入单词是1距离的单词
    """
    # 26个英文字母   ord():获取'a'的码  chr():通过码还原对应的字符
    # 'abcdefghijklmnopqrstuvwxyz'
    alphabet = ''.join([chr(ord('a') + i) for i in range(26)])

    def splits(word):
        """
            分割单词    以cta为例：  [('', 'cta'), ('c', 'ta'), ('ct', 'a'), ('cta', '')]
        """
        return [(word[:i], word[i:])
                for i in range(len(word) + 1)]

    # 分割好的单词
    pairs = splits(word)

    # 删除某个字符	['ta', 'ca', 'ct']
    deletes = [a + b[1:] for (a, b) in pairs if b]
    # 两个字符换位置	['tca', 'cat']
    transposes = [a + b[1] + b[0] + b[2:] for (a, b) in pairs if len(b) > 1]
    # 替换某个字符 ['ata', 'bta', 'cta', 'dta', 'eta', 'fta', 'gta', 'hta', 'ita', 'jta', 'kta', 'lta', 'mta', 'nta', 'ota', 'pta', 'qta', 'rta', 'sta', 'tta', 'uta', 'vta', 'wta', 'xta', 'yta', 'zta', 'caa', 'cba', 'cca', 'cda', 'cea', 'cfa', 'cga', 'cha', 'cia', 'cja', 'cka', 'cla', 'cma', 'cna', 'coa', 'cpa', 'cqa', 'cra', 'csa', 'cta', 'cua', 'cva', 'cwa', 'cxa', 'cya', 'cza', 'cta', 'ctb', 'ctc', 'ctd', 'cte', 'ctf', 'ctg', 'cth', 'cti', 'ctj', 'ctk', 'ctl', 'ctm', 'ctn', 'cto', 'ctp', 'ctq', 'ctr', 'cts', 'ctt', 'ctu', 'ctv', 'ctw', 'ctx', 'cty', 'ctz']
    replaces = [a + c + b[1:] for (a, b) in pairs for c in alphabet if b]
    # 插入某个字符 ['acta', 'bcta', 'ccta', 'dcta', 'ecta', 'fcta', 'gcta', 'hcta', 'icta', 'jcta', 'kcta', 'lcta', 'mcta', 'ncta', 'octa', 'pcta', 'qcta', 'rcta', 'scta', 'tcta', 'ucta', 'vcta', 'wcta', 'xcta', 'ycta', 'zcta', 'cata', 'cbta', 'ccta', 'cdta', 'ceta', 'cfta', 'cgta', 'chta', 'cita', 'cjta', 'ckta', 'clta', 'cmta', 'cnta', 'cota', 'cpta', 'cqta', 'crta', 'csta', 'ctta', 'cuta', 'cvta', 'cwta', 'cxta', 'cyta', 'czta', 'ctaa', 'ctba', 'ctca', 'ctda', 'ctea', 'ctfa', 'ctga', 'ctha', 'ctia', 'ctja', 'ctka', 'ctla', 'ctma', 'ctna', 'ctoa', 'ctpa', 'ctqa', 'ctra', 'ctsa', 'ctta', 'ctua', 'ctva', 'ctwa', 'ctxa', 'ctya', 'ctza', 'ctaa', 'ctab', 'ctac', 'ctad', 'ctae', 'ctaf', 'ctag', 'ctah', 'ctai', 'ctaj', 'ctak', 'ctal', 'ctam', 'ctan', 'ctao', 'ctap', 'ctaq', 'ctar', 'ctas', 'ctat', 'ctau', 'ctav'...
    inserts = [a + c + b for (a, b) in pairs for c in alphabet]
    # 返回集合
    return set(deletes + transposes + replaces + inserts)


def edits2(word):
    """
        返回跟输入单词是2距离的单词
        寻找跟word编辑距离为1的单词的编辑距离为1的单词就是编辑距离为2的单词
    """

    return {e2 for e1 in edits1(word) for e2 in edits1(e1)}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

说明：与该单词编辑距离为2的单词，也就是与该单词的编辑距离为1的单词的编辑距离为1的单词。

最后我们验证一下效果：

if __name__ == '__main__':
    original_word = 'fianlly helloa cta'
    correct_word = correct_text_generic(original_word)
    print('Original word:%s\nCorrect word:%s' % (original_word, correct_word))
1
2
3
4

输出结果如下：

Original word:fianlly helloa cta
Correct word:finally hello cat

2. word文档纠错（CorrectDocx.py）

1.导入相关模块，读取doc文档

from docx import Document
from nltk import sent_tokenize, word_tokenize
from CorrectWords import correct_text_generic
from docx.shared import RGBColor

# 文档中修改的单词个数
count_correct = 0
# 获取文档对象
file = Document("ErrorDocument.docx")
# 各种标点符号
punkt_list = r",.?\"'!()/\\-<>:@#$%^&*~"
document = Document()  # word文档句柄
1
2
3
4
5
6
7
8
9
10
11
12

2.创建修改每一段中错误单词的函数如下：

def write_correct_paragraph(i):
    """
        修改一个段落中的错误
    """
    global count_correct
    # 每一段的内容
    paragraph = file.paragraphs[i].text.strip()
    # 进行句子划分
    sentences = sent_tokenize(text=paragraph)
    # 词语划分
    words_list = [word_tokenize(sentence) for sentence in sentences]
    # 段落句柄
    p = document.add_paragraph(' ' * 7)
    for word_list in words_list:

        for word in word_list:

            if word not in punkt_list:

                p.add_run(' ')
                # 修改单词，如果单词正确，则返回原单词
                correct_word = correct_text_generic(word)

                # 每一句话第一个单词的第一个字母大写，并空两格
                if word_list.index(word) == 0 and words_list.index(word_list) == 0:
                    correct_word = correct_word[0].upper() + correct_word[1:]

                # 如果单词有修改，则颜色为红色
                if correct_word != word:
                    colored_word = p.add_run(correct_word)
                    font = colored_word.font
                    font.color.rgb = RGBColor(0xFF, 0x00, 0x00)
                    count_correct += 1
                else:
                    p.add_run(correct_word)
            else:
                p.add_run(word)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

• 将count_correct设置为全局变量，将一段话划分为句子列表，再将每一句话划分为单词列表。
• 对每一个单词进行遍历，如果是punkt_list中的符号，直接添加；如果是单词，先加一个空格（英语句子中两个单词之间得有空格）。
• 接着纠正单词，调用的是CorrectWords.py中的correct_text_generic()函数。
• 如果是一句话的开头，第一个单词首字母大写。
• 如果单词有修改，设置其颜色为红色，文档中修改的单词个数加1。

最后我们验证一下效果：

if __name__ == '__main__':
    print("段落数：" + str(len(file.paragraphs)))
    for i in range(len(file.paragraphs)):
        write_correct_paragraph(i)
    document.save("CorrectDocument.docx")
    print("修改并保存文件完毕！")
    print("一共修改了%d处。" % count_correct)
1
2
3
4
5
6
7

输出结果如下：

段落数：4
修改并保存文件完毕！
一共修改了19处。

ErrorDocument.docx文档

CorrectDocument.docx文档

编辑距离

什么是两个字符串的编辑距离（edit distance）？给定字符串s1和s2，以及在s1上的如下操作：

• 删除（delete）一个字符
• 交换（transpose）两字符位置
• 替换（replace）一个字符
• 插入（insert）一个字符

最少需要多少次操作才能使s1转换为s2？

比如：
单词“cat”和“hat”，这样的操作最少需要1次，只需要把“cat”中的“c”替换为“h”即可。
单词“recall”和“call”，这样的操作最少需要2次，只需要把“recall”中的“r”和“e”去掉即可。
单词“Sunday”和“Saturday”，这样的操作最少需要3次，在“Sunday”的“S”和“u”中插入“a”和“t”，再把“n”替换成“r”即可。
以上操作对应的编辑距离分别为1,2,3。
那么，是否存在一种高效的算法，能够快速、准确地计算出两个字符串的编辑距离呢？

动态规划算法

我们使用动态规划算法（Dynamic Programming）来计算出两个字符串的编辑距离。
我们从两个字符串s1和s2的最末端向前遍历，假设s1的长度为m，s2的长度为n，算法如下：
1.如果两个字符串的最后一个字符一样，那么，我们就可以递归地计算长度为m-1和n-1的两个字符串的情形；
2.如果两个字符串的最后一个字符不一样，那么，进入以下三种情形（选择其后续总共需要操作步骤最少的）：

• 删除：递归地计算长度为m-1和n的两个字符串的情形，这是在s1中的末端删除了一个字符；
• 替换：递归地计算长度为m-1和n-1的两个字符串的情形，这是因为把s1中末端字符替换成了s2的最后一个字符，这样s1和s2的末端字符一样，就是1中情形；
• 插入：递归地计算长度为m和n-1的两个字符串的情形，这是因为在s1中的末端插入了一个s2的最后一个字符，这样s1和s2的末端字符一样，就是1中情形；

如果m为0，则至少需要操作n次，即在s1中逐个添加s2的字符，一共是n次；如果n为0，则至少需要操作m次，即把s1的字符逐个删除即可，一共是m次。

python实现（DynamicProgramming.py）

计算编辑距离的函数如下：

# 计算编辑距离
def edit_distance(s1, s2):
    print("---------------------------------------")
    print("s1的值:", s1)
    print("s2的值:", s2)
    # s1 长度m
    m = len(s1)
    # s2 长度n
    n = len(s2)
    # 如果m = 0，则至少还需要操作n次，即在s1中逐个添加s2的字符
    if m == 0:
        if n > 0:
            return n
        else:
            return 0
    # 如果n = 0，则至少还需要操作m次，即在s1中逐个删除字符
    # 如果m =0，n = 0，则不需要再操作
    if n == 0:
        if m > 0:
            return m
        else:
            return 0

    # s1和s2最后一个字符一样
    if s1[-1] == s2[-1]:
        return edit_distance(s1[:-1], s2[:-1])
    else:  # 最后一个字符不一样
        # 插入    删除      替换
        return 1 + min(edit_distance(s1, s2[:-1]), edit_distance(s1[:-1], s2), edit_distance(s1[:-1], s2[:-1]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

• 如果s1长度m已经为0，s2长度n不为0，则还需要s2长度n的操作次数，即在s1中逐个添加s2的字符。同理，如果s2长度n已经为0，s1长度m不为0，则还需要s1长度m的操作次数，即把s1的字符逐个删除即可。
• 如果s1和s2最后一个字符一样，直接递归迭代长度为m-1和n-1的两个字符串的情形
• 如果s1和s2最后一个字符不一样，则操作数加1，且选择插入、删除、替换，三操作中以后递归迭代完毕后需要的操作总次数最少的那个操作。

最后我们验证一下效果：

if __name__ == '__main__':
    string1 = "Sunday"
    string2 = "Saturday"
    distance = edit_distance(string1, string2)
    print("编辑距离：", distance)
1
2
3
4
5

输出结果如下：

编辑距离： 3

参考博客：

1. 用 Python 实现英文单词纠错功能
2. 用动态规划算法计算字符串的编辑距离