C/C++基于词汇间固定搭配纠错拼写算法的实现[2025-06-18]-CSDN博客

本文链接：https://blog.csdn.net/qq_35960743/article/details/148749165

C/C++基于词汇间固定搭配纠错拼写算法的实现[2025-06-18]

【问题描述】
拼写纠错算法广泛应用于文本编辑工具、自然语言处理工具、搜索引擎及其它基于字符输入的检索系统。以下是一个基于词汇间固定搭配来纠错拼写的算法描述。请实现该算法，完成给定文件中错误单词的识别及替换词推荐任务。
拼写纠错算法：

单词读入：逐个读入文件in.txt中的单词（仅由连续英文字母组成），并将所有单词转换为小写以进行统一处理。注意：对于缩略词，例如it’s, 处理时将单引号去掉，转换为"it"与"s"两个词。
错误单词识别：与给定的词典文件dict.txt中的单词匹配来识别错误单词。如果一个单词不在dict.txt文件中，则认定为拼写错误。
修正单词推荐：
a) 在自然语言处理中，一个2-gram（bigram）是指由两个连续的单词组成的序列。序列的连续性会在遇到标点符号或其它非字母字符时终止（空格’ ‘和横向制表符’\t’除外）。例如，句子“look, the quick brown fox.”的2-grams包括：(the, quick)，(quick, brown)，和(brown, fox)。由于逗号分隔，词look不与后续词构成2-gram。
b) 当出现拼写错误的单词是某个2-gram中的第二个单词时（假设前一个单词是正确的），查找整个文件中所有首个单词相同的正确的2-grams，并从中选择第二个单词与错误单词具有最小编辑距离的2-gram作为修正建议。如果存在多个编辑距离最小的候选修正词，则按字典序输出这些单词。所谓正确2-gram，是指不含错误拼写单词的2-gram。最小编辑距离可以通过调用给定的editdistDP.c中的editdistDP函数计算得到。
c) 如果按上述方法找不到修正词（没有参考的2-gram，即正确句子中不含与出错2-gram首个单词相同的2-gram），则输出：“No suggestion“。
d）如果一个句子的第一个单词是错误单词，或者错误单词前面的单词也是错误单词，则忽略该错误单词（不做任何处理，没有任何输出）。
【输入形式】
需要进行拼写纠错的文件为in.txt，词典文件为dict.txt（其中每行一个单词，按照字典序存放）。
【输出形式】
向控制台输出结果。按出错单词在文中首次出现次序依次按行列出出错单词及修改建议。要求：
每行一个出错单词及修正结果信息，格式为前缀词+英文冒号+空格+出错词+空格±>+空格+修正词列表。
当有多个修正词时，修正词用逗号分隔，并按字典序排列。
如果一个出错单词没有可推荐的修正词，则在修正词的位置输出“No suggestion”。即前缀词+英文冒号+空格+出错词+空格±>+空格+No suggestion
注意：只有出错单词以及前面的正确单词都相同的，才算相同的出错单词！相同的出错单词的修正结果只输出一次！
【样例输入】
课程平台下载区文件“project2025.zip”中包含了in.txt, dict.txt和editdistDP.C等与作业实现相关的文件。in.txt是要进行错误单词识别和纠正的样例文本文件，dict.txt为关键词列表（每行一个词），editdistDP.c为一种计算编辑距离算法的实现代码。
【样例输出】
data: structurs -> structure,structures
【样例说明】
structurs为出错单词，structure,structures两个词在in.txt文件中存在于data structure, data structures 2-gram中，与出错单词所在2-gram data structures，满足第一个单词data相同，且structure和structures 与出错单词编辑距离最小，为1. 输出按字典序structure在前，structures在后。
【评分标准】
此题为综合性能测试题，测试数据较大，程序运行正确（通过测试点）才能得分，其中运行正确占40%分，性能占60%。