一、要求
(1)计算两个英语(或汉语)字串的编辑距离。(2)实现一个英语单词拼写检查程序,如果单词拼写错误,则给出纠错结果。(3)实现一个简单的拼音输入法。
二、内容
2.1 计算两个英语字串的编辑距离
2.1.1 代码
这里主要借助动态规划算法来计算两个字符串的编辑距离。编辑距离指的是将一个字符串转换为另一个字符串所需的最少编辑操作(插入、删除、替换)次数。代码中主要通过edit_distance函数实现。
A.初始化操作:
该函数接受两个字符串str1和str2代表要计算两个编辑距离的字符串,通过m和n存储两个字符串的长度,使用一个二维列表dp作为动态规划的状态数组。dp[i][j] 代表 str1 的前 i 个字符和 str2 的前 j 个字符之间的编辑距离。dp 数组的大小为 (m + 1) x (n + 1),这样做是为了处理空字符串的情况。
B.循环遍历dp数组每一个元素:
(1)当 i == 0 时,意味着 str1 是空字符串,此时要将空字符串转换为 str2 的前 j 个字符,需要进行 j 次插入操作,所以 dp[0][j] = j。
(2)当 j == 0 时,意味着 str2 是空字符串,此时要将 str1 的前 i 个字符转换为空字符串,需要进行 i 次删除操作,所以 dp[i][0] = i。
(3)若 str1 的第 i 个字符(索引为 i - 1)和 str2 的第 j 个字符(索引为 j - 1)相同,那么不需要额外的编辑操作,dp[i][j] 就等于 dp[i - 1][j - 1]。
(4)若 str1 的第 i 个字符和 str2 的第 j 个字符不同,此时有三种编辑操作可供选择:
a.删除:把 str1 的第 i 个字符删除,那么问题就转化为求 str1 的前 i - 1 个字符和 str2 的前 j 个字符的编辑距离,即 dp[i - 1][j]。
b.插入:在 str1 的末尾插入 str2 的第 j 个字符,那么问题就转化为求 str1 的前 i 个字符和 str2 的前 j - 1 个字符的编辑距离,即 dp[i][j - 1]。
c.替换:把 str1 的第 i 个字符替换为 str2 的第 j 个字符,那么问题就转化为求 str1 的前 i - 1 个字符和 str2 的前 j - 1 个字符的编辑距离,即 dp[i - 1][j - 1]。选择这三种操作中所需编辑次数最少的,再加上当前这次编辑操作(即加 1),就是 dp[i][j] 的值。
C.最后返回结果dp[m,n]
#借助动态规划算法算出两个字符串的编辑距离
def edit_distance(str1, str2):
m = len(str1)#第一个字符串str1的长度
n = len(str2)#第二个字符串str2的长度
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]
#读取文件
def read_file(file_path):
try:
with open(file_path, 'r', encoding='utf-8') as file:
return file.read()
except FileNotFoundError:
print("错误: 文件未找到!")
except Exception as e:
print(f"错误: 发生了一个未知错误: {e}")
return None
#main函数,输入字符串,计算这两个字符串的编辑距离并输出结果
if __name__ == "__main__":
file_path = 'D:\\00NLP\实验语料库25\实验4\spell.txt'
file_content = read_file(file_path)
if file_content is not None:
input_string = input("请输入一个字符串: ")
result = edit_distance(input_string, file_content)
print(f"输入字符串与文件内容的编辑距离是: {result}")
2.1.2 结果截图
(1)当随便输入一个单词,和一个英文txt文件进行处理,结果如下:
图 1
(2)输入两个相似的单词试验,结果图如下:
图 2
2.2 实现一个英语单词拼写检查程序
2.2.1 代码
这里导入spellchecker库中的SpellChecker类用于检查单词的拼写并提供纠错。首先使用正则表达式 \w+ 匹配文件内容中的所有单词,并将它们存储在列表 words 中。content.lower() 将文件内容转换为小写,以确保不区分大小写。
再调用 SpellChecker 实例的 unknown 方法,找出 words 列表中拼写错误的单词,并将它们存储在 misspelled 列表中。调用 SpellChecker 实例的 correction 方法,为当前错误单词提供一个可能的纠错结果。最后打印错误单词及其纠错结果。
from spellchecker import SpellChecker
import re
def spell_check_file(file_path):
spell = SpellChecker()
try:
with open(file_path, 'r', encoding='utf-8') as file:
content = file.read()
words = re.findall(r'\w+', content.lower())
misspelled = spell.unknown(words)
for word in misspelled:
correct_word = spell.correction(word)
print(f"错误单词: {word}, 纠错结果: {correct_word}")
except FileNotFoundError:
print("错误: 文件未找到!")
except Exception as e:
print(f"错误: 发生了一个未知错误: {e}")
if __name__ == "__main__":
file_path = 'D:\\00NLP\实验语料库25\实验4\spell.txt'
spell_check_file(file_path)
2.2.2 结果截图1
运行程序后,对spell.txt文本纠错结果如下所示:
图 3
2.2.3 对输入的单词进行拼写检查 代码
from spellchecker import SpellChecker
import re
def spell_check_string(input_string):
spell = SpellChecker()
words = re.findall(r'\w+', input_string.lower())
misspelled = spell.unknown(words)
if not misspelled:
print("单词拼写无错误")
else:
corrected_string = input_string
for word in misspelled:
correct_word = spell.correction(word)
print(f"错误单词: {word}, 纠错结果: {correct_word}")
# 替换输入字符串中的错误单词
corrected_string = corrected_string.replace(word, correct_word)
print(f"修正后的字符串: {corrected_string}")
if __name__ == "__main__":
input_string = input("请输入一个字符串: ")
spell_check_string(input_string)
2.2.4 结果截图2
重新修改2.2.1的代码,输入单词,检查其是否拼写正确。实验结果如下所示:
图 4 正确拼写结果
图 5 错误拼写结果
2.3 实现一个简单的拼音输入法
2.3.1 代码
from pypinyin import pinyin, Style
import itertools
# 简单的拼音 - 汉字映射
pinyin_dict = {
"ni": ["你", "尼", "泥"],
"hao": ["好", "号", "豪"],
}
def generate_possible_characters(pinyin_list):
all_possible_chars = []
for py in pinyin_list:
if py in pinyin_dict:
all_possible_chars.append(pinyin_dict[py])
else:
print(f"未找到拼音 {py} 的对应汉字,跳过。")
return []
# 生成所有可能的汉字组合
combinations = list(itertools.product(*all_possible_chars))
result = [''.join(comb) for comb in combinations]
return result
def pinyin_input(pinyin_str):
pinyin_list = pinyin_str.split()
characters = generate_possible_characters(pinyin_list)
return characters
if __name__ == "__main__":
input_pinyin = input("请输入拼音,用空格分隔:")
results = pinyin_input(input_pinyin)
if results:
print("可能的汉字组合:")
for res in results:
print(res)
else:
print("未找到合适的汉字组合。")
三、小结
计算字符串编辑距离可以直观地看到,将原字符串转换为目标字符串所需要编辑的具体次数(距离)。在实现对英文文本拼写检查时通过 SpellChecker 类和正则表达式实现了该功能,并处理了可能出现的文件未找到和其他未知异常。但是SpellChecker 提供的纠错结果可能不是绝对准确的,它根据内置的字典给出最可能的纠错建议。我们在使用时还需进一步比对该单词在具体语境中的含义及用法。在实现简单的拼音输入法时,可以看到结合拼音,会有不同的汉字组合,侧面反映了中文汉字的处理、拼写过程难度高于英文字母。