基于二元模糊匹配的编程题智能评分方法

冷强奎，刘雨晴，秦玉平

(1.渤海大学 信息科学与技术学院，辽宁 锦州 121000；2.渤海大学 工学院，辽宁 锦州 121000)

0 引 言

在高校的工科专业中，C语言均被列为一门重要的必修基础课程。由于学习人数众多，对学生程序的人工评分需要教师付出大量劳动，效率低下。并且学生提交程序后不能即时得到分数反馈，这也影响学生期末阶段的状态。另外，人工评分还要受到评卷教师水平、经验、个性甚至道德水准的影响[1]，因此设计一种智能的自动评分方法显得十分重要。

目前，已经存在一些自动评分方法，主要包括三大类[2-3]：动态测试方法、软件质量度量方法和源程序分析比较方法。动态测试方法[4-5]是一种黑盒测试方法，在程序运行期间通过构造大量数据进行饱和测试，并根据运行结果与期望结果的差异来进行评分。但这种方法所使用的饱和测试没有理论上的保证，它往往更取决于测试人员的经验。软件质量度量方法[6-7]是从静态分析角度来进行评分。该方法考虑，如果两个程序使用相同的评分标准，并且得到的分数相似，那么它们可能具有相似的结构、数据流及控制流特征。然而，这对共用评分标准的制定提出了巨大的挑战，即该标准既要能够计算相似，又要准确区分不同。第三类方法是源程序分析比较方法[8-11]，它克服了前两类方法无法衡量学生程序与参考答案的接近程度的问题，并且能够做到对程序进行语句理解，因此具有不错的发展前景。

对于学生程序中的两种极端情况，即无结果无源程序(空白卷)和编译成功结果正确(满分卷)，自动评分系统是很容易就能够判对的。因为只要对编程题目进行合理设置，总能够得到分步骤的输出结果(通常以文件形式写入外存)，这样就能够精确检测学生做题的步骤并防止直接写外存。而对于编译不通过或结果不正确的情况，评分过程则要复杂得多。文中要解决学生程序不完全正确下的自动评分问题，使用二元模糊匹配模型将学生程序与参考答案进行匹配，并根据匹配结果计算分数。最后通过仿真实验来对该匹配模型进行评测，以检验其在不同情况下的评分能力。

1 一元结构匹配

所谓一元结构匹配，即首先要检测学生程序与标准参考答案之间在结构方面的相似程度。答案的结构根据具体题目会略有不同，但通常分为主函数结构与辅助函数结构。每种结构又包含若干个小项，具体如图1所示。

图1 结构匹配示意图

在检测主函数的结构时，重点考查学生程序中是否存在数据输入、函数调用和结果输出等三个方面的内容。然后进行辅助函数结构的检测，这个阶段的检测要比主函数结构的检测复杂一些，因为它不但包含项目是否存在，还要考查各项目的体量(即数量)问题。比如，既要检查参数是否存在，还要检查参数的个数。同样的，也要检查分支结构和循环结构的数量。

下面以题目“编程将一维整型数组IntArray逆置”为例，详细解释结构匹配的操作过程。

试题分析：该题目的核心功能是逆置，而操作对象是一维整型数组IntArray。由于C语言的特点，当参数为数组时，需要再添加辅助参数—数组的规模n，因此能够确定形式参数由IntArray和n联合组成。在教学过程中，教师通常要求学生程序风格尽量模块化，所以在该题目中可以实现输入输出功能的函数化。

参考答案：教师在给出试题的同时，也需要提供相应的参考答案，并且为了评分更智能，通常会给出几份参考答案。当学生程序与其中的一份参考答案相匹配时，学生便会获得相应的分数。对于“数组逆置”这个题目，可以提供的参考答案如图2所示。

图2 参考答案示意图

学生程序：学生根据自身对题目的理解进行自由程序设计。在程序结构上可能会与参考答案存在一定的差异。例如，部分学生可能会认为不需要写输入输出函数，这部分功能在主函数中完成即可。部分学生认为需要更多的变量声明，才能表达清楚程序的功能。另外，学生还会存在程序设计习惯的问题，有的同学喜欢使用for循环，而另外的同学则喜欢使用while循环。因此，在检测学生程序与参考答案之间的结构相似性时，只需要检查每种结构是否存在以及体量问题，而对该结构具体的表达则不必处理。学生提供的可能答案如图3所示。

图3 学生程序示意图

主函数和辅助函数检查完毕后，根据检查结果给出结构匹配的分数。由于该匹配主要关注学生程序中是否存在相应的结构，而不关心这些结构的先后顺序和精确表达，因此称这种匹配是模糊的。从结构匹配的过程可以看出，它的操作很简单，只是对学生程序的一个初级评判，目的是快速确定学生程序中是否存在关键的采分点。

2 二元词语匹配

在一元结构匹配的基础上，接下来要进行关键的二元词语匹配。它包含变量归一化、词频统计、生成向量空间模型、相似度计算等几个步骤，如图4所示。

图4 词语匹配示意图

变量归一化：由于学生自定义的变量名与对应试题无实质性关联，因此为了检测学生程序中变量的类型和体量，对变量名作归一化处理。具体的处理方法是“类型+序号”，比如在程序中第一个出现的双精度浮点型变量，归一化后的名称为“double1”。

词频统计：变量归一化后，可以对答案中出现的词语进行词频统计，以决定该词的权重。这里的统计方法使用自然语言处理中的经典方法，即词频-逆文档频率(term frequency - inverse document frequency，TF-IDF)[12-13]。对于某一特定文件中的词ti来说，它的TF值计算公式如下：

(1)

ti的IDF值计算公式如下：

(2)

其中，|D|为语料库中的文件总数，1+|{j:ti∈dj}|为包含词ti的文件数目。

最终ti的词频可计算如下：

tf-idfi,j=tfi,j×idfi

(3)

TF-IDF表明词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。目前的语料库(即试题库)中文件的数量为20，每个文件提供5套参考答案，因此|D|=100。

生成VSM：经过词频统计得到词的权重后，每个学生程序可以得到一个对应的向量空间模型(vector space model，VSM)[14-15]。模型结构如表1所示，S1～S5是对应题目的参考答案，A为学生答案。

表1 向量空间模型

(4)

对于每个学生答案，要分别与5套参考答案进行相似度匹配，最终的相似度取5次匹配的平均值。与一元结构匹配类似，二元词语匹配也不关心具体词语的先后顺序和是否为精确表达，因此它也是模糊的。

3 智能评分框架

图5给出了整个评分系统的框架和流程。对于两种极端情况，即空白卷和满分卷，系统直接得出分数。如果介于两者之间，则需要进行二元模糊匹配，进行智能评分。

图5 评分系统框架

4 仿真实验

实验中所用语料库包含不同知识点的编程试题20套，每套试题配置5份参考答案，这样语料库规模为100。为了评估不同情况下该评分模型的有效性，从每套试题的参考答案中随机抽取1份，然后对其进行6种修改操作(modify operation，MO)，具体修改操作如表2所示。

表2 修改操作的种类

这样得到了120份的模拟学生程序，然后使用二元模糊匹配模型对这些程序进行评分，并将评分与人工评分进行对比，最终得到了两者之间的差值，如表3所示。

表3 智能评分与人工评分的差值(按百分计算)

从实验结果中可以看出，当修改类型为MO1时，二元模糊匹配能够得到与人工评分相类似的分数。这是因为评分系统首先对学生程序进行了归一化预处理。当修改类型为MO2、MO3、MO4时，智能评分与人工评分的差值也比较小，尽管一些结构已经进行了替换，但在智能评分时，每个学生程序会对照5份参考答案，也就是说，结构替换后，它可能与其中的某一份答案更加类似，从而提高了它的分数。当修改类型为MO5时，智能评分与人工评分则出现了较大的差值。原因在于，如果删除操作去掉了重要词语，那么势必会对结果产生较大的影响。当修改类型为MO6时，智能评分也距人工评分有较大的差距。这是因为增加的冗余语句影响了某些词的权重，使得计算余弦相似时出现了偏差。

但总体来看，智能评分能够对学生程序进行较为智能的检测，克服了传统方法只能评定有限个分类类型的缺陷，因此具有一定的现实意义。

5 结束语

提出了一种新的编程题自动评分方法，称为二元模糊匹配模型，其中第一元是结构模糊匹配，第二元是词语相似匹配。在120份修改测试集上的实验表明，该方法具有不错的性能。特别是当学生程序与参考答案基本接近时，准确率更高。在大规模评分场景中，该方法具有一定的现实意义。