没有合适的资源?快使用搜索试试~ 我知道了~
沙特国王大学学报CoEdit:一种使用拼写校正算法的Abdulelah AlwabelSattam bin Abdulaziz王子大学计算机工程与科学学院计算机科学系,Al-Kharj 11942,沙特阿拉伯阿提奇莱因福奥文章历史记录:收到2020年2021年2月15日修订2021年2月20日接受2021年3月4日网上发售保留字:错误修复错误增强服务器Editex四通编辑编译A B S T R A C T现代编译器不仅可以检测编程错误,还可以使用错误修复技术为这些错误提供一些修复和解决方案。错误修复是指为计算机程序员编写的一段代码编译时发生的错误找到修复方法的过程。然而,修复并不总是与程序员的目的一致。这意味着编译器建议的修复与程序员想要编写的修复不同。当由于拼写错误而导致编程错误时,许多编译器无法提供正确的修复建议。本文的目的是利用拼写校正算法来增强编译程序的纠错过程。一个典型的编译器不提供最常见的语法编程错误的解决方案,这些错误是由于拼写错误而发生的。这样的错误很容易被编译器检测到,但很难提出正确的修复方法。因此,一种新的纠错机制,这是所谓的CoEdit方法的开发,以帮助编译器建议最合适的修复程序错误发生的错误,由于错误的打字错误。Four-Way和Editex算法是众所周知的拼写校正算法,也被扩展并用于与编程语言兼容。CoEdit方法采用这些算法,以便找到拼写错误的修复。CoEdit是一种通用的方法,可以在任何语言的任何编译器中增强错误修复,因为它针对拼写错误的编译器错误。本文的结论是,在查找因拼写错误而发生的编程错误的修复情况©2021作者由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。1. 介绍编译器被设计成将一段用编程语言编写的代码翻译成计算机可以理解的机器语言。编译器分析源代码以在翻译之前找到错误。如果检测到错误,编译器会将其报告给代码的编写者,让他们纠正错误。编译器可以进一步帮助程序员解决错误。此外,现代编译器和最近的集成开发环境(IDE)能够建议使用错误修复方法修复某些类型的错误。错误修复方法基于错误恢复机制(Graham等人,1979年)。然而,新手程序员在理解错误信息方面可能面临挑战电子邮件:a. psau.edu.sa沙特国王大学负责同行审查由于缺乏提供的错误解决方案(Hartmann等人, 2010年)。编译器的好的错误消息应该提供错误修复,这可以帮助程序员弄清楚如何修复错误(Yeum等人,2006年)。然而,一些新手程序员被编译器错误消息所迷惑,并且不直接将它们与代码中的错误相关联,因为消息是模糊的或通用的(Becker等人, 2016年)。错误恢复过程是指为编码过程中发生的错误找到修复方法的过程。它是计算机科学中编译器设计的一个众所周知的部分一般来说,该过程旨在定位误差的准确位置(Sykes和Franek,2004年)。此外,它还试图找到错误的解决方案,以便继续解析剩余的代码。编译完成后,会生成错误消息,以帮助程序员定位和修复列出的错误。虽然有人建议错误消息应该建议解决方案(Thompson,2006),但有些编译器可能只是指出一行代码中有错误,而不建议修复。本工作的目的是开发一个更可行的解决方案,程序员的错误恢复方法和算法的基础上。https://doi.org/10.1016/j.jksuci.2021.02.0101319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。制作和主办:Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页:www.sciencedirect.comA. 阿尔瓦贝尔沙特国王大学学报8491一个典型的Java编译器不能建议修复由拼写错误的单词引起的程序 错 误 。 拼 写 错 误 被 认 为 是 编 程 错 误 中常 见 的 编 程 错 误 之 一(Jadud,2005)。这种类型的错误是解决的,通过旋转校正算法。一种拼写校正算法,用于计算在字典中保存的单词列表中这项工作的目的是提高编译器中的错误修复建议的修复程序中的错误是由于拼写错误的问题。然而,一个正确的单词应该与程序员首先想要写的内容一致本文提出了一种新的纠错机制CoEdit,它采用了Four-Way和Editex两种拼写纠正算法来决定哪一种是最好的拼写纠正算法。本文的结构如下:第二部分讨论了编译器中错误修复机制的背景。错误修复意味着修复一个编程错误,以便让编译器恢复搜索以查找其他错误。有不同的算法试图找到解决方案的编程错误。然后,编程错误进行了研究,以找出哪些错误是不固定的,以及如何解决它们针对这一问题,提出了两种拼写算法:Four-Way算法和Editex算法。第三部分介绍了CoEdit方法,这是一种新的方法,使用拼写校正算法来找到最佳匹配修复由于拼写错误而导致的编程错误第四部分介绍了三个实验,以显示CoEdit的效率下一节介绍了与本文工作相关的工作。最后一节总结了这项工作以及今后进一步加强工作的方向。2. 背景2.1. 错误修复过程错误修复是一个解析过程,它删除或插入符号,以解决编译代码时遇到的错误(Appel和Ginsburg,1997)。最近,已经添加了移位符号作为解决错误的一种方式。错误恢复旨在实现三个目标:第一,以准确和清晰的方式报告错误的检测。其次,快速修复每个错误。这背后的原因是能够检测和报告后续错误。最后,应该可以快速纠正一段代码。错误修复旨在让在解析代码期间发现语法错误的编译器继续解析代码以便发现后续错误(Corchuelo 等人, 2002年)。错误修复可以分为两类:第一类是局部错误修复,这是一种尝试通过在检测到错误的位置之后对输入符号应用错误修复过程来解决错误的方法。第二类是全局错误修复,这是一种类似于局部错误修复的方法,但它也包括检测到的错误位置之前的输入符号(Kim和Yi,2010)。在编译程序时,减少虚假的错误信息是至关重要的。虚假错误消息是虚假错误的消息。换句话说,它们是不是真正的错误的结果。纠错是修改包含错误的输入流以使其正确的步骤。如果目标只是为了继续解析而修复错误,即检测子语法错误,而不管更改是否是程序员打算做的,则称为错误修复。错误更正尝试按照程序员的意图修复错误。因此,任何错误纠正都是错误修复,而不是相反(Grune和Jacobs,2008)。2.2. 错误修复算法有不同的算法可以用于增强和设计修复编译器错误的新方法。“伯克-费舍尔”,“麦肯齐等人”和“set follow”是在编译器中实现的算法,允许进行解析操作在检测到错误后继续解析一段代码,通过找到解决方案或简单地找到一个解决方案,例如Java中的解决方案。然而,这些算法不能保证与程序员的期望一致的修复。它可以允许继续解析以查找代码片段中的其他错误。这种方法在某些情况下是有效的,但并不总是如此,稍后将进行描述。Burke-Fisher 是 由 Burke 和 Fisher ( van der Spek 等 人 , 2005年)。该算法的目的是让解析器在检测到错误后通过找到一组修复来恢复错误。然后,解析器可以继续查找其他错误。该算法的思想是定位一组令牌并存储它们在一个临时的队列中。此外,还有两个堆栈用于算法:第一个被称为当前,第二个被称为旧。旧堆栈存储验证过的令牌,即经过解析的令牌,而当前堆栈保留任意数量的令牌,比如M。此操作在解析操作发生之前执行。每次执行解析操作时,队列都保存M个令牌。 如果在这组标记中发生错误,解析器能够从存储在队列中的标记中追溯到错误这个方法会向前看,在那里可以找到更多要检查的标记。然后,该算法应用插入新符号、删除或替换以解决错误。这种策略在发现作为其他错误的症状的错误方面是有效的,但在错误本身时却不是(Burke和Fisher,1987)。Van Der Spek等人然而,有人认为,这种算法并不总是能找到修复错误的他们的研究指出,当错误是一种症状时,它可以恢复错误,但并不总是(van der Spek等人, 2005年)。虽然这项研究并没有给出为什么伯克和费舍尔算法不能总是找到一个错误的修复的原因,情况是显而易见的,当错误的单词包含许多不正确的字母相比,正确的单词。此外,可以认为,该算法具有插入过程作为恢复错误的方式,这可能导致进一步的错误,并且多次重复插入步骤,这可能导致无限循环。然而,他们没有列出为什么它并不总是有效的原因。除此之外,据称Burk-Fisher错误恢复算法存在两个问题。第一种是为了插入或删除令牌,需要设置队列中的令牌数量为k。其次,它影响解析器通过延迟语义动作。另一个使用相同原理的算法称为McKenzie等人的算法。该算法使用确定性解析自动机(DPA)而不是使用额外的表(McKenzie例如,1995年)。它维护一个按插入或删除符号的代价排序的队列。一方面,该算法在理论上可以修复任何遇到的错误。另一方面,在实践中这样做需要时间,这导致解析过程变慢。这是因为该算法调用密集搜索来找到包括所有可能的终端令牌的修复(Kim和Choe,2001)。其他使用类似原理的算法是:戴恩算法和费舍尔和莫尼算法(费舍尔和莫尼,1992年)。另一种算法称为Set Follow算法,其目的是产生可能出现在被称为解析器令牌的令牌之后的令牌列表,其中解析器令牌由解析器生成。换句话说,解析器生成解析器标记,因此算法的工作是设计一组可能的标记,这些标记可以放置在解析器标记之后。这个可能的令牌列表被称为集合跟随(Bigrigg等人, 2003年)。A. 阿尔瓦贝尔沙特国王大学学报8492然而,该算法的性能可能存在问题。对于解析器生成的每个标记,都将生成一个set follow此外,每个标记出现在一段代码中的不同位置因此,该算法产生不同的集合follow-low,其可以是相似的,也可以不是相似的。此外,对于集合follow中的每个标记一方面,可以认为,除了在发现错误的情况下,没有必要创建可能的解决方案集另一方面,创建集合跟随是非常有效的,因为它实现了找到建议解决编程错误的方法的目标。2.3. 排除编程这一部分主要是对常见的程序错误进行研究和分析,以设计更好的修复机制。编译错误是与编程语言语法不一致的错误,它们在编译时 出 现 语 义 错 误 是 那 些 导 致 程 序 意 外 运 行 的 错 误 ( Grune 和Jacobs,2008)。Garner等人(2005)的研究描述了新手程序员面临的问题。这项研究涵盖了250名学生的入门课程。它描述的问题涉及使用工具编写程序,理解Java任务,命名变量等,此外,它涉及编程错误。这项研究发现,基本力学,因为它是所谓的工作,是排名对于程序员新手来说是最困难的问题之一。 基本的技巧包括大括号,括号,分号,错别字和拼写。然而,这项研究并没有详细说明哪种基本力学是最常见的在Jackson等人(2005)的研究中,他们确定了新手程序员最常见的Java错误,认为他们的研究是新颖的,因为他们使用了一个在线IDE,将所有常见错误记录在数据库中。他们的研究总结了十个常见错误。然而,他们发现,学术教师往往只识别其中的一半,这清楚地说明了在不研究程序员错误本身的情况下识别常见错误的困难,而Ahmadzadeh等人为了改进编程语言的教学方式而研究常见错误(Ahmadzadeh等人,2005年)。后者的动机是了解学生的错误如何有助于提供有效的编程教学方法。他们的方法是收集错误消息和产生这些错误的代码源,他们分析了大约108,000个错误记录。他们的研究结果得出结论,大约三分之一的编程错误是基于语法的,而大多数,另外三分之二,是语义的。与此相关的还有Thompson的研究,该研究调查了常见的编程错误(Thompson,2006)。这项研究的方法是基于使用日志分析软件记录参与者的代码以及他们的这项研究涉及编译器和运行时的错误,专注于解决编程错误所需的平均时间,可以被认为是一种新的方法来研究编程错误。Jadud(2005)进行了另一项研究,研究了使用BlueJ进行编程的新手程序员遇到的常见错误。在实验中,大约63名学生的行为研究得出的结论是,最常见的错误,这是五个错误实现了58%的所有承诺的错误,如下:1. 丢失的小行星约占18%。2. 未知符号:变量约为12%。3. 预计约为12%。4. 在约9%时非法开始表达。5. 未知符号:约占7%。如图所示,在所有错误中,最大的错误是丢失了约18%的子元素然而,第二个和最后一个错误似乎是因为同样的原因;要么拼写错误,要么使用unfined变量(或方法)。因此,它可以排在第一位,因为它占19%左右。Thompson(2006)的研究似乎与这些发现一致。该研究指出,未定义的名称是最常见的错误,与先前研究中称为未知符号的错误相同。这是因为忘记了变量声明或者拼错了变量名,而变量名可能是一个方法的变量 该研究与其他研究一致(Tabanao等人, 2011; Brown等人, 2014年,研究了常见的编程错误。根据Jackson等人的研究,表1显示了编译器最常见的错误消息。(2005年)。最常见的值得一提的是,消息本身可能因所使用的编译器而异。第一条消息是由于拼写错误和使用未定义的方法或单词而产生的。这里的拼写错误包括使用变量或方法的同义词。可以注意到,表中的每个错误消息都提供了相应错误的修复。例如,在缺少一个分号的情况下,编译器除了报告所述的和明确的解决方案外,还报告行号;缺少一个分号。然而,这种情况下的例外是最常见的错误消息,编译器报告行号而不提供任何进一步的帮助。可以说,在使用未声明的变量或方法的情况下,是否不可能进行修复,而在编译问题的情况下,编译器应该尝试查找匹配。2.4. 拼写纠正算法拼写错误的单词是一个常见的问题,可以遇到,而写作;无论是手写或使用文字处理器。Damerau(1964)的一项研究表明,大约80%的拼写错误是由一个错误引起有几种拼写校正算法可用于此上下文中。第一个已知的设计拼写校 正 方 法 的 工 作 是 由 Glantz ( 1957 ) 在 1957 年 完 成 的(Hamrouni,1994)。这项研究的领域只是考虑了一种识别英语明文中拼写错误的单词的然后,将每个拼写错误的单词与字典中正确的单词进行比较(Morgan,1970)。其他作品是为不同领域设计的;例如,用于纠正拼写错误的名称,搜索查询,字处理器等。弗里曼的工作(弗里曼,1964年)被认为是第一个专注于纠正编译器中编程拼写错误的研究(摩根,1970年在纠正拼写错误的单词的过程中有两个基本步骤(Elmi,1994)。首先,应该检测拼写错误的单词。在此之前,需要定义拼写错误的单词。定义可以根据问题的域而不同。例如,在字处理应用程序中,定义表1顶部错误消息。)预期3.8%}预期2.3%错误消息出现无法解析符号百分之十四点六;预期百分之八点五需要类或接口4.6%h标识符i预期值4.5%A. 阿尔瓦贝尔沙特国王大学学报8493ðωÞ拼写错误的单词,很明显,就是用错误的格式写一个单词检测是通过简单地将其与预定义的单词列表进行比较来确定单词是否被识别或是否是拼写错误来实现的。然而,在编译器和编程语言的情况下,这并不总是正确的,因为计算机程序员有能力自己定义变量,并且它们不一定是正确的形式。校正的第二个基本步骤是校正检测到的错误单词。这个步骤也可以分为不同的步骤。第一种方法是找到一组候选词,并保存在字典中。由于寻找解决方案的效率,候选词的数量被限制在合理的数量。这取决于过滤过程。这个过程的目的是尽快丢弃不相关的词,以产生一个较小的列表,错误的词(见下文)。然后,在一个称为匹配过程的过程中,从这组单词中选择一个单词作为对拼写错误的单词的修复。转换可能涉及一个或多个添加、删除或替换的字符。 图 1显示了该过程是如何实现的。为了限制不需要的单词的数量,提出了不一致阈值。它涉及计算两个字符串之间的百分比差异(Kukich,1992)。不一致阈值的目的是找到好的候选词,并丢弃或限制不需要的词。但是,如果阈值太低,它可能会忽略好的单词,或者它可能涉及不需要的单词。因此,提出了一种自适应分歧阈值(Elmi,1994),其目的是找到一个候选词,而不包括不需要的词。它只是从一个相对较高的门槛开始,比如50%。然后,在识别出N个候选词之后,阈值动态地设置为较低值,例如30%。在生成可以被认为是修复的单词列表之后,每个单词都与匹配机制进行比较,以找到最佳匹配。四路和Editex算法被广泛用于匹配。四路算法基于Lee提出的用于拼写校正的称为三路匹配方法的先前算法(Woo等人,2006年)。该方法旨在纠正用于理解和编译自然语言的解析器中的拼写错误。然后,对该方法进行了扩展在四种方式(埃尔米,1994年)。这两种算法都旨在为自然语言中的错误单词找到修复方法。纠正错字的步骤如下。首先,将错误单词与保存在词典中的正确单词列表进行比较然后,具有最小编辑距离的单词,即需要添加、删除或替换的字母的最小数量,被认为是候选单词。第三,候选词的排序,每个的权重。重量计数是基于给每个不同的字母一个特定的字母。最后,可以采用上下文的语法和语义以找到最佳匹配。Editex算法基于Soundex编码与编辑距离方法相结合的思想(Zobel和Dart,1996)。Soun- dex是一种语音编码算法,作为一种表示个人姓名的方法而开发(Branting,2003)。编辑距离是一种算法,用于测量两个字符串之间的距离(Pighizzini,2001),以找到最小的num。Fig. 1. 拼写纠正过程。将一个字符串转换为另一个字符串所需的字母数(Bille,2005)。该算法声称是穷人在性能方面,由于事实上,它需要Om n 其中n是数字的字母数,m 是来自词典的候选词中的单词的字母数(Hodge和Austin,2003)。这种说法是减轻在我们的工作有两个原因:第一是,词典3. CoEdit方法本节演示了CoEdit方法的设计,这是一种为拼写错误找到最合适的修复方法的新方法。最合适的修补是符合愿望的修补写错误的程序员的名字该方法实现如图2所示的拼写校正过程。该工具首先获取源代码作为输入。然后,该方法分析源代码,以获得将被添加到字典中的单词列表。然后,通过匹配算法得到字典和错误词,并根据该算法产生一个合适的匹配列表,称为候选列表。如果方法找到修复,则它完成,否则它继续尝试另一个候选,直到错误被解决或没有进一步的候选。该方法有三个核心过程,即分析、匹配和编辑编译过程。下一节将进一步解释它们。3.1. 分析过程这个过程有两个输入:包含编程错误的源代码和预定义的字典。预定义的字典是包含可用于找到合适的修复的单词的字典。字典包含了编程语言的相关词汇,如关键字、预定义方法、预定义变量、摘要和包.然而,这本字典因编程语言而异。然后,该过程分析源代码,以获得可能有用的单词,如变量或方法,已定义的程序。分析过程通过采用如2.4节中所述的不一致技术来过滤字典。该技术从预定义的字典和源代码中过滤不需要的单词,以减少输出字典。这个过程的结果是错误的单词和过滤的字典。3.2. 匹配过程该过程试图通过计算字典中每个单词的错误权重来找到与错误单词可能匹配的列表,然后将该列表馈送到下一个过程。为了计算误差权重,该过程使用两种算法:Four Way和Editex算法,在第2.4节中提到。每个算法的扩展和采用在这个过程中,以决定哪一个产生更好的结果,在修复编程错误的范围内的准确性和时间。Four Way算法逐个字母比较两个单词,并根据错误类型(即这两个字母之间的差异)分配权重。表2显示了每种错误类型的权重。值得一提的是,一个单词可以有一个或多个前面列出的错误计算每个单词的总错误权重A. 阿尔瓦贝尔沙特国王大学学报8494← ðÞ图二. CoEdit方法。表2错误权重。错误消息发生率人物案例10反序60字符替换70缺少字符80添加字符80算法1.固件算法1:n←getChar字符串12:m←getChar字符串2次3:如果n因此,预计该算法在这项工作中得到扩展。Editex代码组中增加了两个新的分组代码,即特殊字符(代码9)和数字(代码10),如表4所示。该算法在算法2中给出。3.3. 编辑编译匹配过程产生匹配单词的列表而不是单个单词。候选词的列表被称为候选列表。已经注意到,尽管未能找到修复,但修复仍然能够找到想要的修复,尽管它不是最佳匹配。最佳匹配意味着具有最小错误权重的候选词。因此,实现了一个被称为编辑的功能,该功能用候选列表中的单词替换错误单词。4:如果n=1/4/4mn/4/4m=1,则5:错误重量¼逆序6:否则,如果n=1&&7:如果n=1 1/4/4m= 1,则8:errorWeight=字符替换9:else10:errorWeight=缺少字符11:如果12:否则,如果n=1/4/4mn13:如果n=1/4/4m= 1,则14:errorWeight=字符替换15:else16:errorWeight=添加字符17:end if18:其他19:errorWeight=字符替换20:end if21:else if如果不确定,则22:errorWeight= character case23:end if24:returnerrorWeight算法1显示了四路算法。表3显示了拼写错误的单词recognizeFla的示例,其正确形式是recognizeFlag。该表展示了按权重以升序排序的十个候选词的列表权重最小的单词被认为是修复。Editex算法的开发是为了找到人类语言中没有特殊字符或数字的错误的修复方法。算法2. Editex算法1:n←长度1个字1个2:m长度2个3:对于i= 1到n做4:对于j = 1至m,5:距离e½i;j]¼min6:距离e/2i-1;j]i =1;7:距离e/2i;j-1]n1;8:距离e½i-1;j-1]宽度d1½i]1/4宽度d2½j]?0:1分9:结束10:结束11:返回n距离e½n;m]这是通过编辑包含错误单词的原始源代码来实现的。然后,编辑的源代码编译源代码以检查错误是否仍然存在。如果错误仍然存在,则它使用候选列表中的另一个单词重复所有步骤。这种方法尝试一定数量的单词,以节省每次修改源代码然后编译的时间。4. 评价本节提供了进行实验的方法。它首先解释了数据收集和建立字典,其中包含错误单词的可能解决方案。除此之外,它还讨论了我们如何收集和构建测试表3候选人名单的四个方面的例子。表4扩展Editex代码组。字母组代码字母组代码候选词错误权重候选字错误权重A,E,I,O,U,Y,H,W0R6识别标志70承认280B、P1F、V7认识到滞后140承认280C、G、J、K、Q2S,X,Z8识别标志140承认280D、T3特殊字符9识别器标志150递归地410L40至910recognize_Flag150不一致420M、N5A. 阿尔瓦贝尔沙特国王大学学报8495¼ð Þ数据它进一步介绍了实验的结果。本节最后讨论了结果。4.1. 方法如前所述,拼写错误校正过程需要字典来比较错误的单词以便找到匹配。在大多数情况下,词典通常包含一个适当的单词列表。专有词是指在特定的自然语言中定义的词本文以Java程序设计语言为例进行了研究。因此,它需要一个字典,其中包含在这项工作中有用的单词,如Java关键字,预定义的方法,预定义的变量,摘要和包。此外,用户可以自己定义变量和方法这些属性因用户而异;因此,它们仅在特定源代码运行期间包含。为了编纂这部词典,我们采取了两个步骤.首先是分析Java源代码文件,以获得变量、方法和关键字。从两个在线Java资源中收集了大约1, 000 个Java 源代 码文 件: BlueJ(BlueJ, 2020 )和 CodeProject(CodeProject,2020)。这些网站提供用Java编写的源代码,用于收集单词。第二步用于过滤收集的词。第一步收集了大约20万个单词,而第二步过滤了它,使其略高于10,000。过滤过程包括删除重复和不相关的单词。为了检查CoEdit方法,需要收集编程错误列表。然而,这样的档案是不可用的。因此,另一种方法已经被采用来收集根据诸如牛津词典的若干英语词典被认为是最容易拼错的英语单词的单词列表。这些资源提供了常见的拼写错误的单词与每个正确的形式。这使得能够将其用作真实的测试数据。测试数据被分为几个类别,以研究所使用的算法的行为。表5给出了这些类别的示例。进行了三种不同类型的实验:第一个实验比较了四路算法与Editex算法,没有添加CoEdit算法。第二个算法是用来展示CoEdit在使用Four Way算法和Editex算法实现时的行为。第三个也是最后一个实验涉及研究CoEdit方法中使用的候选列表的大小在准确性和执行时间方面的影响。为了比较Four-Way算法和Editex算法,同时考虑精度和时间来衡量性能。准确率是指正确识别的拼写错误的单词数除以总单词数。公式如下所示:一个被识别的单词意味着一个程序员最初的意思,但以错误的格式编写的单词另一个测试测量是完成任务所需的时间,无论结果是否正确。时间是指运行和执行每个算法所需的总根据Hodge和Austin(2003)的研究,这两项措施是拼写检查过程中的基础。这项研究的重点是检索名称的准确性或所谓的回忆,以及找到修复的速度。他们的研究检查拼写错误的名称,而本文的方法检查编程错误。如表5所示,测试数据被分成类别,总共有1,214个拼写错误的单词。该测试分为9个类别,每个类别包含100个拼写错误的单词。然而,最后一种类型的测试数据的大小是其他测试数据的四倍,为414个单词。如本节前面提到的,使用不同的算法在三个实验中运行和测试每组第一种是Elmi(1994)提出的基本格式的四路算法。第二种是Editex算法,如Hodge和Austin(2003)中所述。然后,将这两种算法推广到CoEdit方法中,以找出哪种算法产生更好的结果。第二个实验是实验结果。此外,在第三个也是最后一个实验中,所有数据都在一个步骤中进行测试,以找出每个算法的准确性和所需时间,而不管其类型。此外,为了测试是否能提高两种算法的精度或减少时间,改变候选列表的大小。对于编辑和编译步骤,实验采用BlueJ(Kolling等人,2003年)运行编译阶段,以测试候选词一一个。4.2. 结果和讨论本节介绍并讨论运行该工具实现的实验结果。相同的测试集在4.1中描述的四种不同的方法下运行。表6示出了所采用的算法的结果。时间列显示运行每个测试集所需的总时间。最后一行显示了运行算法的平均准确度和在一段代码中查找单个拼写错误的单词的修复所需的平均时间该算法的平均准确率约为73%,并且为拼写错误的单词找到修复所需的时间为2s。总的来说,该算法在查找单个字母拼写错误单词的修复方面的准确率约为88%,而对于许多字母,这一百分比急剧下降至约56%请注意,单个字母包括缺失、添加或替换单个字母。主要原因是,如前所述,缺少一个以上的字母会导致与其他正确的单词混淆。该算法在一个非常合理的时间内执行,估计约为2秒。的原因正确拼写错误的单词总数ð1Þ在这之后,算法需要On,其中n是错误字的长度。表5测试类型和示例。测试类型示例正确形式缺少单个字母specal special缺少许多字母,添加单字母exram检查添加多个字母描述之间替换单个字母替换多个字母zkace place特殊字符单个字母max_in_valuemax_int_value特殊字符多个字母min_double_Val mindoubleVal表6四路算法结果。测试类型准确度时间(秒)缺少单个字母83% 1.9缺少许多字母37% 2.6添加单个字母81% 2添加多个字母44% 2.1替换单字母91% 1.9替换多个字母68% 3.3特殊字符单字母96% 2.4特殊字符多字母78% 2.3最容易拼错的单词87% 7.2平均值72.75% 2A. 阿尔瓦贝尔沙特国王大学学报8496ωð ωÞEditex算法按照(Hodge和Austin,2001)中的描述实现,但它需要扩展Editex代码组。在Editex算法下测试了具有四路算法的相同测试集平均准确率约为84%,平均处理文件所需时间约为8秒。结果见表7。该算法在修复错过一个以上字母的拼写错误单词时不是很准确。除此之外,该算法通常在找到正确单词方面具有高准确度它是高度准确地处理顶部拼写错误的单词,特殊字符的单词,错过了一个单一的字符,并添加单个字母。根据Damerau(1964)的研究,80%的拼写错误的单词只是单个字母的拼写错误;因此,大多数拼写错误的单词都是单个字母的拼写错误。Editex算法在8 s时比Four-Way算法慢四倍其主要原因是Editex算法需要On m,其中n是错误单词的长度,m是字典中单词的长度。这是因为算法运行一个嵌套的循环,m n代表二维数组总的来说,Editex算法显示出比Four-Way算法更好的准确性。这似乎是因为Editex考虑到字母的相似性,将它们分为不同的组,称为Editex代码组,而Four-Way则根据错误情况划分每个错误。然而,Four-Way算法处理拼写错误的单词所花费的时间大约是Editex的四分之一。因此,可以得出结论,准确度和时间之间存在直接关系这意味着,为了提高查找拼写错误单词的修复的准确性,完成此任务所需的时间也会增加。四路算法的实现不需要改变算法,因为该算法是语言无关的。例如,可以在英语或阿拉伯语中采用相同的算法,而不需要任何改变。这在执行方面似乎是一个很好的观点。然而,语言的规范,例如相似的语音字母,在提高旨在纠正拼写问题的算法的效率方面起着关键作用。在编程语言的上下文中,部分使用英语单词;因此,采用一些语言特征可以帮助提高准确性。该算法是穷人在寻找一个修复的拼写错误的单词与一个以上的不正确的字母,由于它可以分类其他正确的单词作为一个修复的事实。通过改变Editex码组,将Editex算法扩展到数字和特殊字符Editex维护语言的一些属性。事实上,Editex代码组反映了这一点,因为它是基于同一组内每个字母之间的语音相似性然而,这不是一个积极的方面,因为它可能会导致基于字母之间的相似性选择错误的单词例如,same和name都是拼写错误的单词mame的候选单词。如果正确的形式是相同的,则算法无法找到正确的修复因为n和m之间的语音相似性。此外,该算法以区分大小写的方式处理拼写错误的单词,就好像它们是完全不同的单词一样。很明显,它应该来自同一个代码组。该算法在精度方面优于Four-Way算法,但是在时间方面,它更差。如果程序员通过使拼写错误的单词更接近于他打算做的单词而错误地输入了一个单词,这两种算法都会失败,因为这两种算法都使用计算来找到最佳匹配,这有时可能会误导。Editex的准确率约为84%,但仍需要更好的水平,因为本文的目的是找到最佳匹配,而不是让用户在候选词列表中进行选择,这是文字处理应用程序的方式。因此,CoEdit方法已经被开发,以获得更好的效率。这两种算法都被修改,以产生一个特定数量的单词的候选人列表。具有最小错误权重的匹配单词不被认为是最佳匹配,直到错误单词用它替换;然后,它被正确编译。如果不是,则它使用第二个候选词,依此类推。表8显示了使用四路算法执行CoEdit方法的准确性和时间。新方法显示,整体准确率提高了约88.89%,而没有新功能的准确率为72%。原因是该算法成功地找到了相应的修复,但它没有将其列为最佳匹配。然而,时间增加了,因为该方法每次用候选列表中的单词替换错误单词时都进行编译。编译在增加查找修复所需的时间方面起着关键作用。一方面,该算法在处理大约53%的丢失字母方面仍然很差,尽管它提高了大约16%。对另一方面,该算法在查找包含具有单个错误字母、缺失单个字母、添加单个字母和顶部拼写错误单词的特殊字符的拼写错误单词的修复时显示出非常高的准确率,分别为100%、99%、99%和97%。表9显示了采用Editex算法的CoEdit方法的结果。如图所示,该算法在所有算法中具有最高的准确度水平,准确度超过96%。该算法比原算法提高了约16%。该算法达到了非常可接受的准确度水平在处理缺少一个以上字母的单词时。80%的人认为它是最好的。然而,这个数字被认为是其他测试类型中最不准确的,所有测试类型都超过90%。高精度是有代价的。处理时间相对较长。事实上,处理一个单词的时间,平均来说,12.5 s,包括编译已编辑源代码的时间。相比之下,在CoEdit方法所采用的算法之间,Editex具有更高的准确性,而Four-Way在执行时间方面更快。这支持了准确性和执行力之间存在关系表7Editex算法结果。表8与四路结果进行协同编辑。测试类型精度时间(秒)测试类型精度时间(秒)缺少单个字母百分之八十七8.9缺少单个字母百分之九十九1.9缺了很多字母百分之四十九8.7缺了很多字母百分之五十三1.9添加单个字母百分之九十四9.3添加单个字母百分之九十八2.6添加多个字母百分之九十10.2添加多个字母百分之七十一2.2替换单字母百分之八十九9替换单字母百分之九十九2替换多个字母百分之六十七10.7替换多个字母百分之九十二2特殊字符单字母百分之九十五13.8特殊字符单字母100%的2.1特殊字符多个字母百分之八十五8特殊字符多个字母百分之九十一2.3最容易拼错的单词百分之九十七31.6最容易拼错的单词百分之九十七7.3平均83.67%8平均88.89%2.2A. 阿尔瓦贝尔沙特国王大学学报8497表9与Editex结果进行协同编辑。测试类型精度时间(秒)缺少单个字母百分之九十九9.2缺了很多字母百分之八十7.2添加单个字母百分之九十九12.4添加多个字母百分之九十九11替换单字母100%的8.3替换多个字母百分之九十五8.6特殊字符单字母100%的12特殊字符多个字母百分之九十九12最容易拼错的单词百分之九十九31.5平均百分之九十六点六七12.47图三. CoEdit的准确性:四路与Editex算法。时间是一种积极的关系。表8和表9示出了当候选数为7时的结果;即,该方法尝试来自候选列表的七个单词作为修复,并且如果一个单词被编译而没有错误,则它是如第3.3节中所描述的修复。最坏情况下的方法,即没有发现修复,需要以下内容:tt<$dωOncωtc2tt<$dωOn ωmc ωtc3第一个方程用于四向算法,第二个方程用于Editex;两者都使用CoEdit方法。tt表示总时间,d表示词典中的单词数量,n是错误单词的长度。c是候选词列表的大小,m是与错误词进行比较的词的长度,并且tc是编译一件作品的时间,其取决于编译器本身而变化。为了检验增加候选词的数量是否可以导致准确性的增加,将候选列表的数量的表10示出了两种算法的结果:CoEdit方法下的Four-Way和Editex,候选单词数量为10。四路算法的平均准确率为90.56%,而相同算法的平均准确率为88.89%,但候选数为10。在Editex下,准确度也得到了提高,达到了97.67%的准确度。然而,两者都显示出处理时间的增加。由此可以得出结论,增加候选人列表的大小导致整体准确性的增加。它的缺点是它需要更多的时间,因为它需要编译与最坏情况下的候选单词数量一样多的次数。图图3和图4使用相同的方法呈现了候选列表中具有不同数字的每个算法的总体准确性和执行时间,以便找到时间和准确性之间的最佳权衡。这些数字证实,增加候选词的数量也会增加准确率和时间。图四、CoEdit的执行时间:四路与Editex算法。图图3示出了使用不同大小的候选列表从准确度的角度对算法进行的比较。Similarly,Fig. 4显示了相同的比较,但从获得结果所需的时间的角度来看。两个图都表明,候选列表的大小越大,两种算法所需的时间越多,但精度几乎没有提高例如,当候选列表实验结果表明,Editex算法在精度上优于Four-
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功