基于XML的标记串提取算法

钟美

（成都东软学院，成都611844）

基于XML的标记串提取算法

钟美

（成都东软学院，成都611844）

研究一种基于XML的标记串提取算法。从C语言全集中挑选出部分能代表程序结构的关键结构，总结出常见抄袭方式；根据不同的关键结构设计不同的标记串提取算法，将关键结构的结构信息存储于XML文本中；对此算法进行相关测试，测试结果验证算法的有效性。

XML；C程序；标记串提取算法

0　引言

随着互联网的迅速发展，信息资源的获取变得更加方便和快捷，同时抄袭也变更得加容易。就计算机专业而言，因其工程实践性的特征几乎完全采用计算机进行教学与考核，从而导致作业中程序代码抄袭、克隆等现象越来越普遍［1-4］。日益严重的抄袭现象既破坏正常的教学秩序，同时也影响到教学质量和学生素质的提高。程序代码的相似度研究既能高效地发现存在抄袭嫌疑的程序代码，也有助于确保检测的准确性与评判的客观性。高效的标记串提取算法能提高检测的有效性。

本文针对C程序提出一种生成标记字符串的方法，即用XML（Extensible Markup Language）文本来表示C程序。XML是可扩展标记语言［5-6］，加上C语言的强结构性，用XML文本来存储提取的标记串并反映程序的结构是可行的。此方法提取的标记串可以任意提取C程序代码中容易发生抄袭的信息，可以细化到某个变量的初始化、函数名、结构体名、for语句的3个条件表达式、while和do…while语句的判断条件等，从而提高相似度计算的准确率，为程序代码的抄袭判定提供更准确的度量依据。

1　基于XML的标记串提取算法设计

为了能更好地检测学生程序代码的抄袭和减轻教师的工作量，在研究和设计以XML为基础的标记串提取算法时针对不同的关键结构设计出了不同的标记串提取算法。C程序的关键结构主要分为以下几类：变量定义，指针，结构体，宏定义，函数，循环结构（do…while；while；for）和条件结构（if；else if；else；switch；case；default）。由于篇幅限制，在这主要介绍结构体和for循环的标记串提取算法。

1.1常见抄袭方式

通过近五年讲授《程序设计基础》课程的经验和对五百多份学生编程作业的仔细研究和总结，把结构体和for循环的常见抄袭方式分别总结如下：

①结构体：重命名结构体名和结构体变量名；结构体变量的直接定义与间接定义互换；改变结构体成员的数据类型；结构体成员的标识符重命名；拆分结构体变量定义和初始化赋值；重排序结构体成员列表；调整结构体定义语句或结构体变量定义语句的位置；改变结构体定义语句的书写格式。与结构体相关的部分抄袭方式如图1所示。

图1　结构体抄袭方式实例

②for循环：for、while、do…while之间相互替换；将for语句中的第一个表达式放到for语句的前面；将for语句中的第三个表达式放到for语句循环体的最后面；重命名条件判断语句中的标识符；增加冗余的条件判断语句；循环体内部语句的重排序；语句的等价替换，如把i++变为i=i+1或者把sum=sum+i变为sum+=i；增加冗余语句；调整循环结构的位置。与for循环相关的部分抄袭方式如图2所示。

图2　for循环抄袭方式实例

1.2结构体转化为XML文本的算法

在前文中，我们已经详细给出结构体常见的抄袭方式，在这些信息的基础上设计结构体转化为对应的XML文本的算法。对于结构体而言，我们主要提出它的结构体名和具体的属性项，属性项的提取调用的是变量定义的提取方法。还需要注意的是当结构体变量采用直接定义法时，应提取出结构体变量定义语句，并使用变量定义的转化方法把它转化为对应的XML文本。当识别到程序代码中的某行是结构体定义的开始行我们就调用名为structs的函数来实现转换。structs函数中调用了一个名为CToXml的函数，它的主要功能是实现递归调用将不同关键结构转化为对应的XML文本，此函数的实现只是简单使用字符串的匹配，在这就不给予详细的介绍。structs函数的伪代码如图3所示。

图3　structs函数的伪代码

get_struct_name函数是结构体转化为XML文本的具体信息提取函数。针对提取行，从左到右按标识符提取，当提取的标识符是struct时紧跟着提取结构体名，接着提取结构体的body属性并获得结构体定义语句的结束行行号，最后判断是否存在结构体变量的直接定义语句，如果存在则记录下来。get_struct_name的伪代码如图4所示。

图4　get_struct_name函数的伪代码

1.3for循环转化为XML文本的算法

针对for循环，我们主要提取它的三个条件表达式和for语句包含的所有内部语句。由于for循环三个条件表达式书写的灵活性，导致出现了越来越多因改变条件表达式的位置而产生的抄袭现象。在设计提取算法时，我们就设法统一for、while和do…while三种循环语句转化为XML文本的形式，将for语句中的条件表达式1和条件表达式3抽取出来分别处理并转化为对应的XML文本。在for语句的提取过程中，我们主要涉及到的是get_for函数和get_for_condition函数。get_for函数主要用于条件表达式3的提取和实现for循环体语句的递归提取。get_for函数的伪代码如图5所示。

图5　get_for函数的伪代码

get_for_condition函数中主要实现for语句中条件表达式1、条件表达式2和body属性的提取。其中涉及到一个名为begin_end的函数，它的主要功能是得到for循环体内部语句的开始行号、结束行号和循环体的所有内部语句即body属性的存储内容，此函数的实现简单，在这就不给予详细的介绍。get_for_condition函数的伪代码如图6所示。

图6　get_for_condition函数的伪代码

2　算法测试

为了证明本文设计的基于XML的标记串提取算法的有效性，我们将以C程序的关键结构为分类原则对标记串提取算法进行测试。

基于XML的标记串提取算法的设计目的就是为了更有效地检测学生程序设计类课程中存在的抄袭现象，所以在选择测试数据时，我们就随机抽取学生的程序作业作为测试数据。首先选择具有代表性的程序题目，所选择的程序题目必须包括能代表C程序的10种关键结构，再从学生提交成功的程序作业中随机抽取30个程序作为测试数据。把这30个测试用例放在一个test文件夹下，直接把test存放的地址作为输入，输出相应的XML文本。以C程序的10种关键结构为分类原则整理测试数据和测试结果，整理结果如表1所示。经人工仔细判定生成的30个XML文本，全部转化为正确的XML文本。

表1　测试用例表

接着我们来看一个实例，如图7所示，左边的程序代码是上述测试数据中的一个学生作业的源程序，右边为此程序转化为的XML文本。测试程序中的普通变量定义、数组定义、while语句、for语句、if语句和函数都转化为正确的XML文本。

图7　测试实例

3　结语

上述测试结果表明，本文提出的基于XML的标记串提取算法较好地实现了从C程序到XML文本的转换，经过30个程序的测试，转换工作正常。但由于前期算法设计需要准备的知识较多，花费时间较长，实现后的测试工作还不够充分。今后我们将选择更多的学生程序，来对算法进行更全面的测试，完善存在的不足。基于XML的标记串提取算法现在只适用于C程序，如需要还可以扩展到C++、Java程序。基于XML的标记串提取算法的实现不仅为检测学生程序设计类课程中的抄袭奠定了基础，而且保证了抄袭检测的准确性和评价的客观性。

［1］Georgina C，Mike J.Source-Code Plagiarism：A UK Academic Perspective［R］.Research Report RR-422，Department of Computer Science，University of Warwick，2006.

［2］Sheard J，Dick M，Markham S，et al.Cheating and Plagiarism：Perceptions and Practices of First Year IT Students［A］.In Proc.of the 7th Annual SIGCSE Conference on Innovation and Technology in Computer Science Education.New York：Association for Computing Machinery，2002：183-187.

［3］侯敏，刘东升.程序代码抄袭检测技术研究［J］.内蒙古师范大学学报（自然科学汉文版），2007，36（6）：24-26.

［4］程金宏，刘东升.程序代码相似度自动度量技术研究综述［J］.内蒙古师范大学学报（自然科学汉文版），2006，35（4）：457-461.

［5］王继远.一种用于软件作业评判系统的程序结构分析算法的设计与实现［D］.北京邮电大学，2007.

［6］朱江.基于XML的程序设计自动批改的研究［D］.湘潭：湘潭大学，2004.

Algorithm of Token String Extraction Based on XML

ZHONG Mei
（Chengdu Neusoft University，Chengdu 611844）

Studies an extraction algorithm for token string based on XML.The key structure that can represent the procedural structure from C language is picked out，summarizes the means of plagiarism of possible existence of key structure；according to the different key structure，designs the different extraction algorithm for token string，the structure information of key structure is extracted and stored in XML text. Test result verifies the efficiency of the algorithm.

XML；C Program；Extraction Algorithm for Token String

1007-1423（2016）23-0046-04DOI：10.3969/j.issn.1007-1423.2016.23.012

钟美（1985-），女，四川都江堰，硕士研究生，研究方向为计算机辅助教学、算法设计与分析

2016-05-26

2016-07-20