1. 研究目的与意义
在多数国人学习英语的过程中，经常遭遇一些容易混淆的词。经常碰到一些拼写相似甚至只相差一个字母的单词，这个问题非常影响对英文的学习针对这个问题。一些易混淆的单词也对学习过程中造成了影响。
但使用普通的字典以及金山词霸等软件也直接查找到其相似单词，很难快速的查找到自己想要的结果，这大大影响了人们对英语的学习。基于这些问题设计一个能实现相似四六级单词排序和提示的程序：此程序在输入某个单词后能出现与其相似的单词，并按照相似性对其进行排序，设计一种基于动态规划的有限分隔最长公共子串算法与改进的最小编辑距离算法进行相似单词查找与比对的程序来实现这一想法，通过此程序来提高人们对英语学习的效率更好的学习英语。
2. 课题关键问题和重难点
已知国外跨平台的拼写校正程序Aspell更加注重拼写校正，而通常忽略拼写正确的相似单词，例如form与from。同时在商业应用方面，Microsoft Word和google均含有拼写检查方面的工作。同样它们对于拼写正确的单词并不给出相似单词列表。
张扬等人提出一种基于判别模型的拼写校正方法，在这种方法中将编辑距离、基于字母的n元语法、发音相似度和噪音信道模型特征融合到判别模型中。他们的工作主要应用与网络日志挖掘方面。国内外相关研究重点放在大规模词典的近似匹配算法中，例如提出了分阶段匹配策略，即包括粗匹配阶段和细匹配阶段。
基于此有以下难点：
3. 国内外研究现状（文献综述）
随着人工智能和自然语言处理的迅速发展，相似度计算已成为语义消歧、信息提取、信息检索、文本分类、自动问答、数据挖掘等基础应用的亟待解决的问题。伴随各个领域研究的不断深入，相似度计算的对象也由之前的词共现相似、语法结构相似上升到了语义相似，而精准高效的语义相似度计算成为了一个亟待解决的问题。当前语义相似度算法主要是基于本体词典或知识库的规则方法以及基于大规模语料库的统计方法。其中，基于规则的方法主要利用词典或知识库中的本体树或图的结构或者本体之间的共现属性数目。而基于统计的方法又分为利用知识库和不利用知识库的方法。其中利用知识库的统计方法由于更加全面且一定程度上忽略了知识库中的噪音信息，在这些方法中取得了最优的效果。 拼写校正是指针对由拼写检查器检测出存在于文本中的每个拼写错误, 作出1个或多个更正建议的过程.通常情况下, 拼写检查器会把未在给定词典里出现的字符串识别为错误拼写.本文解决了在英文文本中校正非词错误 (比如将the拼成了teh) 的问题.我们不考虑将一个单词错拼成另一个单词的真词错误 (比如将form拼成了from) .换句话说, 我们暂不考虑上下文对单词拼写校正的影响, 这主要基于目标应用、评测集合和系统性能的考虑.本文的目标是提出一个更好的可以应用到文本处理程序 (比如Microsoft Word和Aspell) 中的拼写校正方法.在这些应用中, 一定数量的 (通常是5~10个) 更正建议以一种交互的方式展现给用户, 由用户选出最理想的一个.大多数情况下, 排到第一位的建议是优先推荐的, 因此, 侧重点在top-1的准确度 (top-1 accuracy, 答案排在第一位的样本比例) 上.此外, 由于前5/10个建议也会展现给用户, 所以我们同样关心top-5/top-10的准确度.Aspell[1]是目前比较流行的一个跨平台的拼写校正程序.文献[16]中的实验显示, Aspell在其测试集上的top-5准确度超过了85%, 而top-1的准确度只有不到60%. 在拼写校正任务中用到的模型主要分为规则和统计两类.基于规则的研究包括文献[10, 11].近些年来, 统计机器学习方法也应用到这个任务中来, 收到了良好的效果.统计方法大致可以分为两类:生成模型 (generative model) 和判别模型 (discriminative model) .在这个领域中广为应用的生成模型主要是噪音信道模型 (noisy channel model) , 包括文献[12-15].噪音信道模型将错误拼写的生成看作是把一段文本向带有噪音的信道进行传输的过程, 在传输过程中引起了拼写错误.对于每个可能的错误拼写, 具有最大后验概率 (即从输入拼写到该候选的转换概率) P (candidate|input) 的候选作为建议返回.通过使用贝叶斯公式, 并将作为常数的分母约去, 可以按照语言模型 (或称为源模型) P (candidate) 与信道模型 (或称为纠错模型) P (input|candidate) 的乘积作为分数对每个候选进行打分评判.语言模型可以用基于字母的n元语法来进行估计.而信道模型则通常归结为字母到字母或字符串到字符串的混淆概率.在现今的主流英文拼写校正模型中, 文献[5]由于其信道模型允许广义的字符串操作 (如后缀ant变为ent) 具有最好的性能.对于判别式模型, Winnow[19]和神经网络[7]被用到了拼写校正任务中来.文献[17]中描述的模型对上下文敏感, 采用了基于歧义消解的方法处理来自同一个混淆集 (confusion set, 比如form和from) 的用词错误.本文提出的模型是一个线性判别模型, 它可以将各种影响因素以特征的形式整合进来, 同时具有在训练过程中按照某种学习策略 (如梯度下降、二次规划等) 自动调整各个特征对应权值的特性.这些特性使得我们能够将现今流行的多种拼写校正技术放到同一个模型中去, 并且取得了理想的效果. 1.Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8. 2.张扬，何丕廉，向伟，李沐. 一种基于判别式重排序的拼写校正方法[J], 软件学报，2008，19(3): 557-564. 3.Schulz K, Mihov S. Fast string correction with Levenshtein automata [J]. International Journal of Document Analysis and Recognition, 2002, 5(1): 67-85. 4.龚才春, 黄玉兰, 许洪波, 白硕. 基于多重索引模型的大规模词典近似匹配算法[J]. 计算机研究与发展, 2008, 45(10): 1776-1781. 5.Wagner R A. The String-to-String Correction Problem [J]. Journal of the ACM, 1974, 21(1): 168-173. 6.李占波，王晓川. 基于不等长字符串的免疫匹配规则研究[J]. 微计算机信息, 2009, 10-3, 162-163. 7.于海英. 程序代码相似度度量的研究与实现[J]. 计算机工程, 2010, 36(2): 45-46. 8.Hu W.C.,Ritter G.X. Schmalz M.S. Approximateing the longest approximate common subsequence problem[C]. Southeast Regional Conference ACM,1998:166-172. 9.M. Karpinski, W. Rytter, A. Shinohara, An efficient pattern-matching algorithm for strings with short descriptions, Nordic Journal of Computing 4(1997) 172-186. [10]Mangu L, Brill E.Automatic rule acquisition for spelling correction.In:Proc.of the14th ICML.1997.187-194.http://citeseer.ist.psu.edu/mangu97automatic.html [11]Martins B, Silva MJ.Spelling correction for search engine queries.In:Proc.of the EsTAL.2004.372-383.http://www.springerlink.com/content/m7g3d9tt351urg7f/ [12]Ahmad F, Kondrak G.Learning a spelling error model from search query logs.In:Proc.of the EMNLP2005.2005.955-962 [13]Brill E, Moore RC.An improved error model for noisy channel spelling correction.In:Proc.of the38th Annual Meeting of Association for Computational Linguistics.2000.286-293. [14]Cucerzan S, Brill E.Spelling correction as an iterative process that exploits the collective knowledge of Web users.In:Proc.of the EMNLP.2004.293-300.http://citeseer.ist.psu.edu/754653.html [15]Toutanova K, Moore RC.Pronunciation modeling for improved spelling correction.In:Proc.of the40th Annual Meeting of Association for Computational Linguistics.2002.144-151.http://citeseer.ist.psu.edu/541572.html [16]Ahmad F, Kondrak G.Learning a spelling error model from search query logs.In:Proc.of the EMNLP2005.2005.955-962. 17]Golding AR, Roth D.Applying winnow to context-sensitive spelling correction.In:Proc.of the13th ICML.1996.182-190.http://citeseerist.psu.edu/golding96applying.html |
4. 研究方案
本课题的目标是为对中国英语学习者能提供有效的帮助。因而文中假设词典规模有限（来源于四六级，托福，GRE考试范围），因而重点研究适合这类应用需求的方法。
步骤如下：
1. 搭建运行环境python3.5 pycharm.
5. 工作计划
第一周-第二周：查看以及初步理解毕业设计任务，制定毕设的大致思路以及大体研究方向
第三周-第四周:完成外文翻译与开题报告，通过各种文献的查找以及外文翻译完成论文的开题报告。
第五周-第六周：进行需求分析并确定方案，进行程序制作前的准备工作。
以上是毕业论文开题报告，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
