基于编辑距离的自适应反馈程序评测方法
2022-08-23薄钧戈乔亚男房琛琛
薄钧戈,乔亚男,齐 琪,黄 鑫,房琛琛
(西安交通大学 计算机科学与技术学院,陕西 西安 710049)
0 引 言
程序设计类课程是计算机类专业的专业基础课,是数据结构、算法设计与分析等计算机核心课程的先修课[1]。程序设计类课程教学目标是培养学生应用计算机去求解实际问题的能力,为了达到此目标,同学们需要反复的上机编程训练。由于传统的程序设计类课程考核方式(纸面试卷)有很多缺点,比如教师需要花大量的时间和精力来批改作业、学生无法及时获得学习效果反馈、缺乏在编程中的自我判断能力等,导致学习兴趣逐渐减退[2-3],因此近几年有不少高水平本科院校程序设计类课程将程序在线评测系统(Online Judge,OJ)引入到实践教学环节中[4-5],以提高学生编程热情和压力情况下解决编程问题的能力,以正确的计算思维去理解和构建复杂的程序系统[6-7]。
对于编程题的自动评阅,目前主要有两种方法,一种是将学生程序代码编译为可执行文件,然后输入“预设测试用例输入”,得出“学生代码输出”,再和“预设测试用例输出”比对,给出相应得分情况,该方法在基础教学和算法竞赛中皆有长时间广泛而成熟的应用[8];另一种是结合程序代码特征和复杂性度量,如学生代码的行数、变量个数、复杂度以及语法树等去评价学生程序代码的质量并给出得分[9-10],并结合一些分类、聚类、可视化等数据挖掘的方法进行图表显示[11-13],这两种方法都有明显的缺点:当学生代码编译错误,或者测试用例评测不对,在没有得全分的情况下,面对编译、运行等问题,学生还是很难改对代码;尤其是在编译通过而测试用例不通过的情况下,学生在修改代码时有可能只是因为测试用例输出的大小写出错、缺失标点符号、顺序出错、有无空格等简单格式问题而花费大量时间进行调试(为了保证测试用例的安全,测试用例不能公开)。
为了解决上述问题,该文提出一种基于编辑距离的自适应反馈程序评测方法,通过检测学生代码的编译信息和测试用例信息,应用编辑距离,自适应给出学生代码出错原因并给出反馈指导,帮助学生快速找到代码出错位置并有针对的进行修改。该方法应用到了本校面向大面积计算机基础课程的作业系统中(该系统由教学团队自主研发,相关界面见图1),该系统基于ASP.NET MVC框架开发,主要有题库管理、在线练习、实时评测、系统监控、学习预警等功能。学生注册后,根据题目在线提交多种编程语言(C,C++,C#等)源代码,系统编译源代码后执行,采用黑盒测试的方式,通过和预设测试用例的比对来检验源代码编译和运行的正确性。
图1 计算机基础课程作业系统截图
实践证明,通过结合自适应反馈程序评测方法的OJ系统,可以有效促进程序设计类课程的教学质量[14]。
1 研究方法和过程
该文提出的基于编辑距离的自适应反馈程序评测方法,整体的步骤如图2所示[8]。
图2 自适应反馈程序评测方法步骤
第一步,教师端布置编程题目信息,如题目描述、参考答案、开始完成和截止时间、预设测试用例等,其中测试用例根据题目考察点,可设置多个测试用例;
第二步,学生根据题目要求通过在线编辑器完成题目编写并上传至代码评测服务器,其中在线编辑器有代码高亮显示、折叠、缩进等模拟真实开发环境功能;
第三步,在评测学生程序代码之前,需检测过滤学生程序,对学生程序中出现不安全代码进行过滤,所述不安全代码包括fdisk-硬盘分区、format-格式化、shutdown-关机等命令,防止恶意代码;
第四步,编译学生程序,代码中如果由于语法错误导致编译失败,获取编译错误信息,如图3所示,通过对编译器返回的编译错误信息进行筛选整理,分别获得下面信息:
图3 获取编译错误信息
(1)编译错误代码,通过编译错误代码,弹出相应错误代码帮助文档,如MSDN文档,或者打开相应错误代码帮助网页;
(2)编译错误行号,通过编译错误行号,学生可以快速定位找到程序错误位置;
(3)编译错误详细说明,通过编译错误详细说明,可以帮助学生理解编译错误原因,有针对地修改错误代码。
第五步,如果学生程序编译通过,而运行不通过,则表示学生程序通过“预设测试用例的输入”生成的输出结果和“预设测试用例输出”两段文本不相等。因此,如果需要提供给学生一个比较准确的错误反馈信息,则需比对分析学生程序的输出和“预设测试用例输出”的异同,然而,学生编写练习的程序和一般软件产品不同,比如结构简单,大多数有固定的算法模块,如果编译通过而运行不通过,大概率总有这样的情况:学生代码通过“预设测试用例的输入”生成的输出总是朝着“预设测试用例输出”靠近。因此对于学生代码编译通过而运行不通过的错误原因可能是常见简单错误,所述常见简单错误包括:学生代码输出结果大小写出错、中英文标点符号错误、缺失或存在多余的空格、顺序出错、错位问题、数值间存在倍数扩大或缩小等。
该文将重点讨论第五步 “程序编译通过而运行不通过” 这种情况,将在下一小节详细介绍。
2 基于编辑距离的自适应反馈程序评测方法
2.1 判断测试用例考察类型
基于编辑距离的自适应反馈程序评测方法首先判断测试用例考察类型,可以结合“预设测试用例输出”,得出测试用例考察类型,根据程序设计类课程历史中同学们常见问题总结考察类型为四种,分别为:“单一字符串型”、“多个字符串型”、“单一纯数值型”、“多个纯数值型”。测试用例考察类型确定方法如图4所示。
图4 测试用例考察类型判断方式
当预设测试用例输出文本内容有字符或符号时,且字符串间没有空格隔开,判断测试用例类型为“单一字符串型”;
当预设测试用例输出文本内容有字符或符号时,且字符串间以空格隔开,判断测试用例类型为“多个字符串型”;
当预设测试用例输出文本内容只有纯数值(包括小数)时,判断测试用例类型为“单一纯数值型”;
当预设测试用例输出文本内容只有纯数值或小数点或空格,并数值间以空格隔开时,判断测试用例类型为“多个纯数值型”。
2.2 计算编辑距离
对于四种不同的测试用例考察类型,需要计算学生代码的输出结果和“预设测试用例输出”的编辑距离(Minimum Edit Distance,MED)。
编辑距离是由俄罗斯科学家Vladimir Levenshtein在1965年提出的,因此编辑距离也称为 Levenshtein Distance。在信息论、语言学和计算机科学领域,编辑距离是用来度量两个序列相似程度的指标。简单的说编辑距离就是指在两个单词之间,由其中一个单词A转换为另一个单词B所需要的最少单字符编辑操作次数[15]。
在自然语言中的拼写检查时,根据一个拼错的字符串和其他正确的字符串的编辑距离,可以判断哪一个或哪几个是比较可能的字符串。对于两段字符串A和B,其中字符串A的长度为m,字符串B的长度为n,其计算方法如下:
d[0][0]=0
d[i][0]=0, 1≤i≤m
d[0][j]=0, 1≤j≤n
d[i][j]=
其中,d表示一个[m+1][n+1]大小的二维数组(d的数组比字符串长度长1个,是因为需要一个[1][1]大小的数组记录其编辑距离为0),d[i][j]表示完成从A(0,i)到B(0,j)的编辑次数。wdel(ai)表示把A[i]删除的一次操作,wins(bj)表示把B[j]插到A[i]的一次操作,wsub(ai,bj)表示把A[i]用B[j]替换的一次操作。
相应的符号如图5所示。
图5 文中相应的符号及表示内容
2.3 “单一字符串型”用例结果错误
对于测试用例考察类型为“单一字符串型”,首先判断学生代码输出结果和预设测试用例输出长度是否相等。
(1)学生代码输出结果字符串和预设测试用例输出字符串长度相等时,依次做如下处理:
将学生代码输出结果字符串大、小写转换(大写字符转为小写字符、小写字符转为大写字符、全部转为大写字符、全部转为小写字符)后和预设测试用例输出字符串比较是否相等,如果相等,则中英文反馈指导学生由于“字符大小写问题”导致运行不通过;
将学生代码输出结果字符串标点符号中英文转换后和预设测试用例输出字符串比较是否相等,如果相等,则中英文反馈指导学生由于“标点符号中英文问题”导致运行不通过;
调整修改学生代码输出结果字符串的顺序后和预设测试用例输出字符串比较是否相等,如果相等,则中英文反馈指导学生由于“顺序错误”导致运行不通过;
将学生代码输出结果字符串旋转(从首字符到最后一个字符进行多次旋转)后和预设测试用例输出字符串比较是否相等,如果相等,则中英文反馈指导学生由于“存在输出错位问题”导致运行不通过;
计算学生代码输出结果字符串和预设测试用例输出字符串的编辑距离edit_Dis,以及编辑距离计算中删除字符次数Ndel,编辑距离计算中添加字符次数Nins,且计算编辑距离占预设测试用例输出比例R=edit_Dis/Lt,其中Lt为预设测试用例输出字符串的长度,如果R<0.5,则中英文反馈指导学生由于“输出与测试用例输出长度相等,但是一半的字符无法匹配”导致运行不通过;如果编辑距离edit_Dis和预设测试用例输出字符串长度相等,则中英文反馈指导学生由于“输出与测试用例输出长度相等,但是所有字符均无法匹配”导致运行不通过。
(2)学生代码输出结果字符串和预设测试用例输出字符串长度不相等时,依次做如下处理:
删除学生代码输出结果字符串中所有标点符号(主要是空格、回车等)后和预设测试用例输出字符串比较是否相等,如果相等,则中英文反馈指导学生由于“输出了多余的标点符号”导致运行不通过;
删除预设测试用例输出字符串中所有标点符号(主要是空格、回车等)后和学生代码输出结果字符串比较是否相等,如果相等,则中英文反馈指导学生由于“缺少某些标点符号”导致运行不通过;
计算学生代码输出结果字符串和预设测试用例输出字符串的编辑距离edit_Dis,以及编辑距离计算中删除字符次数Ndel,如果编辑距离edit_Dis和删除字符次数Ndel相等,则中英文反馈指导学生由于“多输出了某些字符,与预设测试用例输出无法匹配”导致运行不通过;
计算学生代码输出结果字符串和预设测试用例输出字符串的编辑距离edit_Dis,以及编辑距离计算中添加字符次数Nins,如果编辑距离edit_Dis和添加字符次数Nins相等,则中英文反馈指导学生由于“少输出了某些字符,与预设测试用例输出无法匹配”导致运行不通过;
计算学生代码输出结果字符串和预设测试用例输出字符串的编辑距离edit_Dis,以及计算编辑距离占预设测试用例输出比例R=edit_Dis/Lt,其中Lt为预设测试用例输出字符串的长度,如果R<0.5,则中英文反馈指导学生由于“输出与测试用例输出长度不相等,且一半的字符无法匹配”导致运行不通过;否则显示“输出与测试用例输出长度不相等,且超过一半的字符无法匹配”导致运行不通过。
2.4 “多个字符串型”用例结果错误
对于测试用例考察类型为“多个字符串型”,需先判断学生代码输出结果字符串个数Ns(以空格隔开)和预设测试用例输出字符串个数Na(以空格隔开)是否相等。
(1)学生代码输出结果字符串个数和预设测试用例输出字符串个数相等时,依次做如下处理:
判断删除学生代码输出结果字符串空格、回车后和预设测试用例输出字符串比较是否相等,如果相等,则中英文反馈指导学生由于“输出内容与测试用例要求大体一致,有多余的空格、回车”导致运行不通过;
判断删除预设测试用例输出字符串空格、回车后和学生代码输出结果字符串比较是否相等,如果相等,则中英文反馈指导学生由于“输出内容与测试用例要求大体一致,缺失题目要求的空格或回车(可在输出头、尾检查)”导致运行不通过;
将学生代码输出结果字符串大、小写转换(大写字符转为小写字符、小写字符转为大写字符、全部转为大写字符、全部转为小写字符)后和预设测试用例输出字符串比较是否相等,如果相等,则中英文反馈指导学生由于“字符大小写问题”导致运行不通过;
将学生代码输出结果字符串标点符号中英文转换后和预设测试用例输出字符串比较是否相等,如果相等,则中英文反馈指导学生由于“标点符号中英文问题”导致运行不通过;
调整修改学生代码输出结果字符串的顺序后和预设测试用例输出字符串比较是否相等,如果相等,则中英文反馈指导学生由于“顺序错误”导致运行不通过;
将学生代码输出结果字符串旋转(从第一个字符串到最后以个字符串进行多次旋转)后和预设测试用例输出字符串比较是否相等,如果相等,则中英文反馈指导学生由于“存在输出错位问题”导致运行不通过。
(2)学生代码输出结果字符串个数和预设测试用例输出字符串个数不相等时,依次做如下处理:
学生代码输出结果字符串个数Ns大于预设测试用例输出字符串个数Na时,判断学生代码输出结果字符串中前Na个字符串是否和预设测试用例输出字符串相等,如果相等,则中英文反馈指导学生由于“前Na个字符串和预设测试用例输出匹配,但多输出了某些字符串”导致运行不通过;
学生代码输出结果字符串个数Ns小于预设测试用例输出字符串个数Na时,判断学生代码输出结果字符串中前Ns个字符串是否和预设测试用例输出字符串相等,如果相等,则中英文反馈指导学生由于“前Ns个字符串和预设测试用例输出匹配,但少输出了某些字符串”导致运行不通过;
将学生代码输出结果调整顺序后,判断学生代码输出结果字符串中前min{Ns,Na}个字符串是否和预设测试用例输出字符串相等,如果相等,则中英文反馈指导学生由于“输出字符串个数有误,且存在输出顺序问题”导致运行不通过;
将学生代码输出结果按照字符串间隔旋转后和预设测试用例输出字符串比较是否部分相等,如果相等,则中英文反馈指导学生由于“输出字符串个数有误,且存在输出错位问题”导致运行不通过;
去除掉学生代码输出结果字符串和预设测试用例输出中的所有空格,并计算学生代码输出结果字符串和预设测试用例输出字符串的编辑距离edit_Dis,以及计算编辑距离占预设测试用例输出比例R=edit_Dis/Lt,其中Lt为去除掉空格后的预设测试用例输出字符串的长度,如果R<0.5,则中英文反馈指导学生由于“输出字符串个数与测试用例输出字符串个数不相等,且一半的字符无法匹配”导致运行不通过;否则显示“输出字符串个数与测试用例输出字符串个数不相等,且超过一半的字符无法匹配”导致运行不通过。
2.5 “单一纯数值型”用例结果错误
对于测试用例考察类型为“单一纯数值型”,依次做如下处理:
将学生代码输出结果字符串和和预设测试用例输出字符串转为数值型,按照10的倍数放大或缩小学生代码输出结果,再与预设测试用例输出比较,如果相等,则中英文反馈指导学生由于“输出字符串与预设测试用例输出无法匹配,但是存在10的倍数关系”导致运行不通过;
判断学生代码输出结果字符串和和预设测试用例输出字符串长度是否相等,如果不相等,计算学生代码输出结果字符串和和预设测试用例输出字符串的编辑距离edit_Dis,再比较前min{Ls-edit_Dis, Lt-edit_Dis}(Ls为学生代码输出结果字符串长度,Lt为预设测试用例输出字符串长度)个学生代码输出结果字符串是否和预设测试用例输出字符串相等,如果相等,则中英文反馈指导学生由于“输出字符串与预设测试用例输出无法匹配,但是有效位保留出错”导致运行不通过。
2.6 “多个纯数值型”用例结果错误
对于测试用例考察类型为“多个纯数值型”,需先判断学生代码输出结果数值个数Ns(以空格隔开)和预设测试用例输出数值个数Na(以空格隔开)是否相等。
(1)学生代码输出结果数值个数和预设测试用例输出数值个数相等时,依次做如下处理:
判断删除学生代码输出结果字符串空格、回车后和预设测试用例输出字符串比较是否相等,如果相等,则中英文反馈指导学生由于“输出内容与测试用例要求大体一致,有多余的空格、回车”导致运行不通过;
判断删除预设测试用例输出字符串空格、回车后和学生代码输出结果字符串比较是否相等,如果相等,则中英文反馈指导学生由于“输出内容与测试用例要求大体一致,缺失题目要求的空格或回车(可在输出头、尾检查)”导致运行不通过;
调整修改学生代码输出结果数值的顺序后和预设测试用例输出数值比较是否相等,如果相等,则中英文反馈指导学生由于“多个数值间存在输出顺序错误”导致运行不通过;
将学生代码输出结果多个数值进行旋转(从第一个数值到最后一个数值进行多次旋转)后和预设测试用例输出数值比较是否相等,如果相等,则中英文反馈指导学生由于“多个数值间存在输出错位问题”导致运行不通过。
(2)学生代码输出结果数值个数和预设测试用例输出数值个数不相等时,依次做如下处理:
学生代码输出结果数值个数Ns大于预设测试用例输出中数值个数Na时,判断学生代码输出结果数值中前Na个数值是否和预设测试用例输出相等,如果相等,则中英文反馈指导学生由于“前Na个数值和预设测试用例输出匹配,但多输出了某些数值”导致运行不通过;
学生代码输出结果数值个数Ns小于预设测试用例输出中数值个数Na时,判断学生代码输出结果数值中前Ns个数值是否和预设测试用例输出相等,如果相等,则中英文反馈指导学生由于“前Ns个数值和预设测试用例输出匹配,但多输出了某些数值”导致运行不通过;
将学生代码输出结果调整顺序后,判断学生代码输出结果中前min{Ns,Na}个数值是否和预设测试用例输出相等,如果相等,则中英文反馈指导学生由于“输出数值个数有误,且存在输出顺序问题”导致运行不通过;
将学生代码输出结果按照数值间隔旋转后和预设测试用例输出比较是否部分相等,如果相等,则中英文反馈指导学生由于“输出数值个数有误,且存在输出错位问题”导致运行不通过。
3 自适应反馈程序评测方法的实施与成效分析
将基于编辑距离的自适应反馈程序评测方法引入到本校面向大面积计算机基础课程的作业系统中,学生使用该系统的相关截图如图6和图7所示。通过连续3年的应用,发现学生在线提交作业后,由于自适应的指导反馈,可以有效提高学生编程的积极性。通过该系统学生不再局限于时间和地点的约束,并且系统有学习状况分析功能,能够看到同班级学生的完成情况,营造竞争和激励的良好学习氛围,也有利于同学们的自主学习。同时,教师从传统的向学生传授知识转变为协助学生解决任务,有利于教师提前发现充满热情的学生,对其进行有针对性的培养。
图6 编译不通过反馈提示界面
基于编辑距离的自适应反馈程序评测方法除了在本校大面计算机基础课程的教学有应用外,还用于竞赛的培训,实现有效衔接。课程组老师指导的学生多次获得ACM国际大学生程序设计竞赛、“蓝桥杯”全国软件和信息技术专业人才大赛以及团体程序设计天梯赛奖项。在2019-2021年,本校连续三届均有团队获得全国总决赛团队一等奖。
图7 编译通过运行不通过反馈提示界面
4 结束语
近年来,团队老师在计算机基础课程体系、能力培养模式、教学资源、人才培养等方面取得了重要成果,应用效果显著。对于其他兄弟院校、专业开设程序设计课程和实践能力培养具有较好的借鉴和示范作用。
实践证明,结合自适应反馈程序评测方法的在线评测系统,可以有效激发学生的学习热情,通过在实践中学习掌握正确的计算机思维和行动方法,促进程序设计类课程的教学质量。同时,系统引入了线上学习新的教学评价体系和学习成绩考核机制,取得了良好的教学效果。另一方面,在实际的应用过程中,也存在一些不足和不完善的地方,例如系统没有考虑到学生的自律性和主动性存在差异,以及如何扩展学习深度和难度,为更优秀的学生提供深层次的教学扩展等,这些不足还需要在后续研究和应用中进一步改进和探索。