近似串匹配算法在自动评分系统中的应用.pdfVIP

东莞理工学院学报 第15卷第3期 V01．15No．3 JoURNALOFDONGGUANUNn也RSITY0FTECHNOLOGY 2008 2008年6月 Jun． 近似串匹配算法在自动评分系统中的应用 李少芳车艳 (莆田学院电子信息工程学系，福建莆田35llOO) 摘要：无纸化考试是大规模计算机基础课考试的发展趋势，自动评分系统的可靠设计与实现直接影响 这类考试的可信度。应引起足够重视．简述计算机自动评分系统研究现状。详细介绍了近似串匹配算法的 实现原理，并讨论其在文字录入模块自动评分中的一些关键应用． 关键词：近似串匹配；自动评分：文字录入；算法应用 文献标识码：A 文章编号：1009一0312(2008)03一0025一04 中图分类号：11P301．6 1 计算机自动评分系统研究现状 计算机无纸化考试是现代教育考核方式中的一种重要手段，它的推广和应用是信息技术条件下教 育环节中考试方式的全新改革和发展趋势。无纸化考试系统通常包括题库维护、在线考试和评分三个 子系统，计算机自动评分子系统的设计与实现是其中最重要也是难度最大的部分。计算机自动评分Ⅲ 是指使用计算机程序来模拟人工评分的标准及内部过程，对开放式题目和表现性活动进行评分及反 馈。国外目前开发完成并已投入使用的计算机自动评分系统包括用于短文评分和写作技巧评定的项目 短文评定系统PEG(ProjectEssay EssayAssessor)、智能 Gmder)、智能短文评价者IEA(Intclligent 测评(Intellimetric)、电子评分者E．ra_ter以及用于其他类型开放式题目评分的CAS系统，如用于牙 科评价的DISC(DentalInteractiveSimulation 试的CAS系统等。但我国CAS的研究起步晚，目前仅限于针对计算机应用能力考核而设计的计算机 上机考试系统的自动评分，还不能为受试者提供反馈”-。 2 近似串匹配算法的实现原理 字符串的匹配问题被视为计算机科学的基本问题之一，早期的研究多集中于精确匹配领域。精 确串匹配技术要求模式与正文子串完全匹配，不允许有错误。但是后来人们逐渐发现在许多实际应 用中，并不要求模式与文本子串完全精确匹配，而往往更需要进行近似串匹配。例如，由于单词本 身可能有文法上的变化，加上书写和印刷方面的错误，在一个文本中查找某个给定的单词，就需要 进行近似匹配忙。。然而在实际问题中确定两个字符串是否近似匹配不是一个简单的问题，比如可以 串的近似匹配，就是允许在匹配时有一定的误差，比如在字串。以前高手好久不见”中找搿以前是 高手”也能成功。具体地说，近似的类型有三种；加字符(以前也是高手)、漏字符(以前高手) 和替换字符(以前石膏手)。 P在丁中包含至多K个差别的匹配。差别的三种情况(图l所示)：(1)删去：P中含有一个未出现在 T中的一个字符；(2)插入：P中不含有出现在T中的一个字符；(3)修改：P与丁中对应字符不同。 收稿日期：2008一03一ll 作者简介：李少芳(197l一)．女，福建福安人，讲师．主要从事计算机算法研究． 东 莞理工学院学报 2008年 T： a r oxi ma ● p y @ 恼 P： appr Ox～＼h、m a 0 y 注。①删去②插入@修改