C语言组卷系统中重复题问题研究

陈星+李郴

摘要：在一套试卷中，重复题问题是影响考试质量的一个重要因素。该文针對C语言试卷中选择题间易出现重复题问题进行深入研究.通过对代码相似性检测以及文本相似性检测综合研究应用，希望能找到较好地处理C语言试卷中选择题的重复题问题的方法，进一步提高C语言组卷模块的组卷质量，减轻教师的工作量。

关键词：重复题；代码相似性检测；文本相似性检测

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）01-0214-03

Abstract：In a set of test papers， repetition problem is an important factor affecting the quality of the examination. Aiming at the problem easily appears between the in-depth study of repeated questions C language test. Based on the code similarity detection and text similarity detection method of comprehensive research， hope to repeat questions can find better choice C language in the test， to further improve the quality of the C language test paper module， reduce the teacher the workload.

Key words： Repetition problem；Code similarity detection；Text similarity detection

随着计算机技术的高速发展，越来越多的教学环节向电子化和网络化转变，目前很多高校开始创建自己的C语言试题库平台，大部分的C语言试题库都可以进行试卷的自动生成，这不仅省去了教师编题时苦恼于自身偏向的烦恼，更能体现考试的公平性与公正性，同时减轻了教师的工作压力与负担。计算机自动组卷保证了试卷的客观性、科学性和公平性，使得试题和试卷的管理变得高效便捷，对提高教师工作效率，实现课程管理现代化具有十分重要的意义。但是在C语言自动组卷过程中，有可能会发生重复题问题，导致组卷质量下降，进而影响考试质量。

由于在C语言试卷中选择题形式有其特殊性，主要表现于在一道选择题中文本和代码同时存在，情况相对复杂，因此本文针对C语言试卷中的选择题进行研究。对重复题的检测，本文应用相似性检测原理，并针对选择题的特殊性，采用合理方案，而不能仅仅使用文本相似度检测或者代码相似度检测来对C语言试卷中的选择题进行相似性比对，需要综合应用两种算法进行比对。

1 相关技术分析

本文研究如何解决C语言试卷中选择题易出现的重复题问题，故本文研究的重点是如何寻找选择题中出现的重复题，由于选择题形式的特殊性，本文将引入空间向量模型的概念，综合使用文本相似度比对方法以及代码相似度比对方法来进行C语言选择题中是否出现重复的检测。

1.1 空间向量模型概念

空间向量模型的思想是：每篇文本中都包含一些用特征项表达的揭示其内容的独立属性，而每个属性都可以看成是向量空间的一个维数，那么文本就可以表示为这些属性的集合，从而忽略了文本的结构中段落，句子及词语之间的复杂关系。这样，文本就可以用空间的一个向量来表示，文本之间的相似度可以用向量间的距离来衡量。

本文中把C语言试卷选择题中的文本部分和代码部分的内容当做是一篇文本，那么我们就可以将向量空间模型的概念引入到本文研究的选择题中。两道选择题之间的相似度就可以用向量间的距离来衡量，向量之间的距离通常采用余弦系数法进行判定，即用两个向量之间的夹角余弦来表示两道选择题之间的相似度。夹角越小，说明两道选择题的相似度越大。

通过上述的向量空间模型，文本数据就转换成了计算机可以处理的结构化数据，两个文档之间的相似性问题转变成了两个向量之间的相似性问题。

1.2 分词方法

对于选择题中出现的文本，需要通过分词方法选取出其中的文本关键词，目前常用的分词方法主要有以下两种：

1.2.1 基于统计的分词方法

基于统计的分词方法就是把字与字相邻共现的频率作为成词的可信度评价标准。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词，否则，认为它们不能组合。基于统计的分词方法的原理是根据相邻字出现的频率来确定是否属于一个词，该方法不需要建立词典，有词的歧义判断能力，适用于大规模的文本分词处理。

在本文研究的文本部分中，内容少，相同词汇出现的频率低，因此不适合使用基于统计的分词方法。

1.2.2 基于词典匹配的分词方法

基于词典匹配的分词方法是按照一定的策略将待分析的字符串与词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功[2]。该方法分词效率高，但是完全依赖于词典，无法判断词的歧义性，而且由于汉语环境复杂，词典不太完备，规则不一致等问题的存在，使得这种分词方法无法应用与大规模的文本分词处理。

本文研究的文本，规模小，词汇量少，词汇之间的歧义性低。因此适合于这种分词方法，能够降低重复题检测模块的时间复杂度。

1.3 代码相似度计算方法

目前使用比较多的代码相似度计算方法主要有，基于属性计数的相似度计算方法，基于结构的相似度计算方法，以及基于语法树的相似度计算方法。基于属性计数计算方法主要是针对于程序代码中的定义的关键词，循环数等，不考虑程序的结构。基于结构的相似度计算方法主要是通过程序的结构特征，分析程序的结构信息及执行流程，通过对程序的内部结构进行分析比较其相似性。基于语法树的代码相似度检测方法对源程序进行语法分析而得到其语法树，对待处理的源程序的语法树结点进行分类统计，采用矢量和计算方法计算结点属性向量，最终通过向量相似度与预设阈值的比较判定是否相似。endprint

该文研究的程序代码的特点是，不一定具有明显的结构，有可能仅仅是几个简单的语句，因此无法仅使用基于属性计数或者基于结构的相似度计算方法进行比较，而基于语法树的相似度计算方法结合了程序代码的结构特征以及属性特征，满足了该文程序代码的特点。因此该文拟采用基于语法树的相似度计算方法处理代码。

1.4 余弦相似度

余弦相似度是用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小的度量。n维余弦公式（公式1）为：

余弦值越接近1，就表明夹角越接近0度，也就是两个向量越相近，夹角等于0，即两个向量相等，这就叫“余弦相似性”。

2 重复题检测方案

本文的思想是将C语言中的选择题看成是由文本特征向量，代码特征向量以及知识点组成的n维向量空间模型，而从对C语言选择题的特点上可以大致将选择题分为以下几种情况，以文字来表述的选择题，以代码形式表述的选择题，以及文本和部分C语言语句混合表述的选择题。对于单纯的以文本形式表述的选择题，其中的代码特征向量全部用0表示，对于单纯以代码形式表述的选择题，其文本特征向量全部用0表示。

在重复题查找的过程中，首先是对待比较的选择题进行格式规范化，然后将选择题中的文本和代码进行分离，提取特征向量，并建立文本和代码的空间向量模型，将文本和代码向量进行融合，得到题目的空间向量模型，之后求取两个向量的余弦值，最终通过余弦值与预设阈值的比较判定是否相似。预设阈值的获取是通过对大量相似题进行比对，计算相似值，根据对大量相似值分析，确定预设阈值的大小，如果两个向量的余弦值大于预设阀值时，就认为这两道选择题是重复题。

所谓的规范化是指：将试题中出现的一些用文本表达的代码表达式，使用代码表示；将题目中相同语义的词语使用同一个词替换。比如在试题中出现这样一句话，“定义一个整型变量a”，转换成“int a”这样的代码表达式表示； “下列属于合法的标识符的是”和“下列标识符正确的是”，两句话中“合法”和“正确”属于同义词，都替换成“正确”一词。

2.1 文本特征向量的提取

由于本文主要是针对于C语言选择题进行研究，对于C语言中存在的许多专业名词，如数组，链表等，若单纯采用普通文本词汇库进行分词，可能会造成较大误差，并且会造成时间复杂度增加，所以我们需要建立专门的词汇库，通过基于字符串匹配的方法对试题中文本进行特征向量提取。

对于短文本来说特征向量越多，代表的文本信息越详细。所以该文拟保留全部的文本词汇，仅将其中的语句顿词，例如“是”，“的”等词汇去掉，剩余词汇作为文本的特征向量，通过文本特征向量，将文本以空间向量模型（公式2）的形式表示出来：

2.2 代码特征属性的提取

对于代码，主要通过对待比较的代码程序进行语法分析，得到语法树，对待处理源程序的语法树结点进行分类统计，采用矢量和计算方法计算结点属性向量。

首先，需要将源代码进行预处理，例如，将源代码中的连续多个空格全部处理成一个，将代码中注释和多行空白行全部去掉，将在语义上相同的语句使用同一语句处理，比如将（a+=b）均使用（a=a+b）代替；（i++，++i）全部使用（i=i+1）代替，将声明多个变量的语句（int a，b）使用单个声明语句代替（int a；int b）等等。

语法树中的结点也就是将源代码进行预处理之后程序的特征属性，可以选择以下结点[标识符，常量，赋值语句，函数或过程，数组和结构体，条件结构，表达式语句，声明变量个数，循环结构等]表示语法树的每个结点，父结点的属性向量等于结点初始属性向量及其所有子结点的属性向量的矢量和。在生成语法树的时候，可以采用UCC的方法或ANTLR语法分析工具，将程序生成相应的语法结构和抽像语法树，本文将语法结构存到一个*.txt文件中，之后利用著名的词法分析工具Lex从这个文件中抽取逻辑结构，另外将语法树存放在*.asm文件中[6]。

在生成程序的语法树之后，可以针对相应的文件来抽取里面的特征向量（结构信息）及其个数。这里从该语法树中抽取其相应的结点作为特征向量，其结点可以表示为[标识符，常量，赋值语句，函数或过程，数组和结构体，条件结构，表达式语句，声明变量个数，循环结构]，每个结点出现的个数作为其频度信息。

最后将提取的代码特征向量，使用n维空间向量模型（公式3）表示出来：

2.3 向量对齐

将文本空间向量，代码空间向量，以及从数据库中提取的试题知识点属性（本文采用每题最多3个知识点）融合到一起形成一个多维的试题空间向量模型S，如公式（4）。

由于不同试题中文本空间向量个数以及代码空间向量个数不一致，因此需要将试题空间向量模型的维数统一成n维的，例如存在两道试题，试题1的文本空间向量由（A，B，C）三个特征向量组成，代码空间向量由（D，E，F）三个特征向量组成，知识点由（Z1，Z2，Z3）三个特征向量组成，试题1的空间向量模型可以表示为S1（A，B，C，D，E，F，Z1，Z2，Z3）；试题2的文本空间向量由（A，B，C，D）四个特征向量组成，代码空间向量由（D，F，G，H）四个特征向量組成，知识点由（Z1，Z2，Z3）三个特征向量组成，试题2的空间向量模型组成可以表S2（A，B，C，D，D，F，G，H，Z1，Z2，Z3）。对于试题1和试题2的相似性比较，首先需要将文本，代码维数进行统一。对特征向量之间进行比对，将两道试题中不同的特征向量融合到一起作为试题的特征向量，若上面两道试题中特征向量全都不一样，则试题1的空间向量模型可以表示为：S1（A，B，C，A，B，C，D，D，E，F，D，F，G，H，Z1，Z2，Z3，Z1，Z2，Z3），对于试题1中的所有关于试题2的特征向量都不存在，因此需要用0来表示；同理，试题2的空间向量模型也可以用S2（A，B，C，A，B，C，D，D，E，F，D，F，G，H，Z1，Z2，Z3，Z1，Z2，Z3）来表示出来。这样可以使得两道待比较试题维数的统一。

2.4 题目相似度计算

通过上面对选择题的处理，分别将两道选择题使用空间向量表示出来，然后通过多维余弦定理（公式5）进行相似度计算：

将求得的余弦值与预定阈值进行比较，判断两道题目是否相似。

3 结束语

本文在C语言试题库的研究基础上，对自动组卷后的试题进行重复题查找研究，通过对试卷中出现的重复题特点进行归纳总结，对文本和代码相似度进行深入研究，给出合理算法，以查找自动组卷后试卷中产生的重复题，使C语言试题库系统的智能组卷功能更加合理有效。

参考文献：

[1] Jacob G，Debar H，Fillol E.Behavioral detection of malware： From a survey towards an established taxonomy.Journal in Computer Virology，2015.

[2] Li Y，Zuo ZH.An overview of object-code obfuscation technologies.Journal of Computer Technology and Development，2016（17）.

[3] 全上克，杨新锋.程序代码相似度检测方法的设计与实现[J].微型电脑与应用，2013（6）.

[4] 曹海英，元元等.程序代码抄袭检测中串匹配算法的研究[J].信息安全技术，2015（6）.

[5] 郭少友.自动分类中的文档表示及其改善方法研究[J].信息技术，2014，3（8）：23-25.

[6] 尚文倩.文本分类及其相关技术的研究[D].北京：北京交通大学，2015.endprint