湖南省大学生研究性学习和创新性实验计划项目结题报告.docx

《湖南省大学生研究性学习和创新性实验计划项目结题报告.docx》由会员分享，可在线阅读，更多相关《湖南省大学生研究性学习和创新性实验计划项目结题报告.docx（20页珍藏版）》请在三一文库上搜索。

1、湖南1大学生研究性学理能扇牲奖剑划项目结题报告项目名称：ACM竞赛程序源代码复制检测系统的设计与实现项目编号：学生姓名：刘洋易长庚刘慧凤曾嘉佩所在学校和院系：湖南第一师范学院信工院项目实施时间：2014年6月一2016年3月指导教师：田祖伟联系电话：填表日期：20表年3月30日湖南省教育厅2016年制一、基本情况项目名称ACM竞赛程序源代码复制检测系统的设计与实现立项时间2014年6月完成时间2016年3月项目主要研究人员序号姓名学号专业班级所在院(系)项目中的分工1刘洋12计科1班信工院算法设计2易长庚12计科1班信工院代码实现3刘慧凤13计科1班信工院代码实现4曾嘉佩13计科1班信工院系统

2、测试二、研究成果简介项目研究的目的、意义；研究成果的主要内容、重要观点或对策建议；成果的创新特色、实践意义和社会影响；研究成果和研究方法的特色。限定在2000字以内。1、项目研究的意义通过几代人的不懈努力，人类最伟大的发明之一计算机，已经成为了人们生活中不可或缺的必备工具，也间接地成为了社会衡量和选取人才的标准之一。因此，现代初高等教育也在不断地加强青少年的计算机高级应用水平，几乎所有高校都已开设或正在筹备开设计算机软件应用或计算机程序设计类学科课程。但是，不少学生出于对程序设计的懒惰甚至惧怕心理，在面对程序设计类作业时,采取各种手段复制抄袭网络上或同学朋友的源代码，以应付老师和学校的检查。这

3、种行为严重影响了学校的教学质量，而且极不利于学生提高自身的计算机应用水平，减少了毕业求职时的筹码。针对上述现象，国外教育机构的调查结果表明：有高达85.4%的学生承认抄袭过别人的编程作业。随着程序源代码的抄袭现象越来越普遍，抄袭手段越来越多样化，单纯地依靠学校和老师对学生的思想教育和人工辨别检测已难以抑制抄袭现象的蔓延，高等院校急需更高效、准确的检测方法来检测抄袭行为，遏制抄袭现象地继续发生。但是，判断程序源代码是否抄袭是一项耗时、复杂的工作，若一个班级有n名学生，就必须对其所有的n份作业进行n(n-l)2次对比判断，尤其是当程序设计类作业的难易程度不同时，即无法准确查出抄袭者，又无法确保因难

4、易程度等因素的不同而造成的误判断，往往只能依靠老师的经验和检查的仔细程度来大致控制检测的准确率，这无疑增加了老师的工作时间和复杂度，且收效甚微。利用高效率的程序源代码抄袭检测工具才能有效地解决这个问题，因此，开发ACM竞赛程序源代码复制检测系统具有一定的实用价值。2、研究成果的主要内容（1）程序源代码抄袭检测技术、抄袭手段分类及应对不同情况的分级处理方法，现有检测系统原型及其主要算法研究。程序源代码抄袭检测主要是通过对比两段程序源代码，计算这两段程序源代码之间的相似度并得到一个0.0到1.0之间的相似度值，再通过设置阈值（可由系统自动计算或用户设置）来划分出是否有抄袭行为嫌疑的程序代码片段，进

5、而判断目标程序源代码中是否存在抄袭行为。目前较常用的程序源代码检测技术一般为属性计数法和结构度量法两种。属性计数法是统计程序源代码中所包含的各种属性（即成员变量），并将其映射到给定的向量空间中，再计算这两段程序源代码之间的相似度值。但该方法即使在向量维度上进行优化，准确度仍然较低，误判断较多。VercO等人也指出“单纯地增加向量的维数并不能减少检测的错误率，提高检测精度二结构度量法是将程序源代码进行预处理成特殊的数据序列，再利用相似度计算公式计算出相似度值。相比属性计数法，该方法可将程序源代码中的结构和语义加入检测判断过程，提高检测准确度。基于结构度量法的检测算法通常包括以下两个步骤：1）程序

6、源代码预处理。即将程序源代码进行标准格式化、注释和冗余空白字符过滤、关键字标识符替换、常量替换、数据类型等价替换和统一大小写等。目前常用的预处理方法包括：基于String的方法、基于TOken的方法和基于AGT（AbstractGrammarTree,抽象语法树）的方法等。基于String的算法，即将程序源代码以行为单位分割成若干字符串的集合，每个程序代码片段包含相邻的字符串，判断两两程序代码片段的字符串是否相同，再根据程序代码片段相似度判断是否存在抄袭行为。该算法检测准确率不高，代表算法有1995年Baker提出的参数化匹配算法。基于Token的算法，即对程序源代码进行词法分析，生成Toke

7、n序列，再对比检测两段程序源代码的TOken序列中相同的片段。该算法效率很高，但准确度仍然较低。基于AGT的算法，即利用工具对程序源代码进行词法语法分析，得到该段程序源代码的抽象语法树，判断两段程序源代码的抽象语法树中的子树是否相似，再根据相似子树的相似性判断相似度。该算法准确度较高，但冗余较大，效率较低。2)相似度计算。即对程序源代码预处理后，得到其对应的数据序列，再根据两段程序源代码的数据序列进行相似度计算。目前常用的相似度计算方法有向量模型法和字符串匹配算法两类，如点阵图法、序列匹配算法、LCS(LongestCommonSubsequence,最长公共子序列)算法、GST(Greedy

8、String-Tiling)算法和RKR-GST(Running-Karp-RabinGreedy-String-Tiling)算法、WinnoWing算法、余弦度量法等。上述两种方法虽在一定程度上能够检测出程序源代码中的相似处，但效率和准确率都比较低，不能非常有效地应对所有的抄袭手段。且这些算法过于依赖阈值，阈值的设置直接地影响了算法的准确度，而某一算法的阈值需要经过大量实验才能较精确地确定，当情况发生变化时，阈值或需重新设置，这无疑增大了算法设计实现和程序开发的难度。(2)基于N-gram检测算法研究N-gram是一种统计语言模型，其定义为：设Z为一个字母表，S是一个由Z中的字母组成的字

9、符串。ISl表示S的长度，Siu是S中第i个字母(i从1开始)，E同是S中从第i到第j个字母组成的S的子字符串，N是一个整数，且N不大于S,则S中的N-gram就是长度为N的S的邻接子字符串，如：S11,i+N.i,S11jNioG(S,N)表示字符串S中所有的N-gram的集合，长度为ISl的字符串可以生成L=IS卜N+1个N-gram,如：S=detection，S=12,N=5,则G(S,N)=(l,detec)，(2,etect),(3,tecti),(4,ectio),(5,CtiOn)oN-gram适用于语音识别、文字识别、文本分类、信息检索、机器翻译和中文分词等领域，且于1995

10、年被M.Damashek首次应用于文本相似度度量，近几年被证明适用于文本抄袭检测，能有效地提高文本抄袭检测的准确率，且优于普通字符串匹配算法。N-gram算法统计N-gram集合中每个元素出现的频率，而忽略了该元素在程序源代码中的原始位置，使得检测抄袭时能够较好地降低因抄袭者使用代码块及其内部语句重排序和表达式拆分等较高级抄袭手段对检测准确度造成的影响。同时，对生成N-gram前的预处理也可以较有效地检测大部分低中级抄袭手段，使得N-gram算法在一定程度上能够达到较理想的检测准确度。（3）基于Ngram算法检测系统的底层检测计算框架的设计和实现，采用分级处理方法提高检测系统针对性的代码实现。

11、为了提高检测系统的检测准确率和针对性，本文采用了Ngram算法与分级处理的方法对系统进行了实现和优化。Ngram算法是一种统计语言模型，适用于语音识别、文字识别、文本分类、信息检索、机器翻译和中文分词等领域。N-gram可以很好地保持程序源代码的结构和语义，在此基础上进行抄袭检测，可以有效地提高检测的准确度。几乎所有的检测算法都需要为其设置阈值，而阈值的概念对于一般普通的用户而言较抽象晦涩，使其无法达到最理想的值，这也极大程度地影响了最后相似度的计算结果。分级处理是将抽象的阈值形象具体化，即将程序源代码按难易程度划分（可由系统根据程序源代码规模自动计算或用户选择设置），帮助用户在使用系统时更方

12、便清晰的设置恰当合理的“阈值”，提高用户体验和检测针对性。系统实现有五个重要步骤：a）读取程序源代码数据。使用JaVa的JDK内置的K）相关API,读取程序源代码。b）预处理。根据难易程度的不同，对待检测程序源代码进行不同复杂度地格式化预处理，预处理方式由用户选择填写传入的相关参数确定。c）生成标记。根据程序源代码使用的程序设计语言的语法规则和关键字,将其转换为对应的标记序列，可以较好的压缩待比较数据的空间占用大小，提高检测系统的运行效率，还可以保持程序源代码中原有的结构和语义，即结构化。d）生成N-gram。将标记序列转换为N-gram集合，统计每个N-gram出现的频率，并将得到的N-gr

13、am文本存入数据库中。e）计算相似度。从数据库中查询区其他程序源代码的N-gram文本，与待对比的程序源代码生成的N-gram频度向量依次进行相似度计算，得到相似度值。本文采用了较为灵活的架构设计，尽量做到能够根据用户不同的需求（即选择传入的不同参数）进行较为恰当地处理和检测，但又不需要用户做出太多太复杂的操作，在保证系统检测的准确度、针对性和效率的同时，有较好的用户交互和体验。同时开发了大部分表示层和中间层，让系统有较高的扩展性，也为第三方开发者提供了二次开发的接口和服务。1）预处理预处理主要用于去除程序源代码中的混淆、无用数据，并按照用户指定的程序设计语言编码标准及风格格式化该该程序源代码

14、同时可检测表22中修改排版的抄袭手段。本文包含的预处理方式有以下几种：a）删除程序源代码中的注释语句。b）将一行包含多条语句的代码转化成每行一句。c）将本为一行的多行代码转化成一行。d）删除代码中的多余空白字符（空格、Tab）oe）将所有字母转化成小写字母。前三种预处理方式可由用户选择是否进行，这样可以有效地避免对格式规范的程序源代码进行无用的预处理操作，提高系统的检测效率。系统将会根据用户提供的难易程度进行一种或多种预处理，即分级处理（3.2节），得到的程序源代码有效地去除了原程序源代码中的注释和多余空白字符，在保证生成标记和N-gram过程中数据的有效性的前提下，直接地过滤了多余无用字符

15、对检测的影响，且格式规范,有利于提高检测系统的准确性。2）生成标记预处理后的程序源代码有很好的符合对应程序设计语言类型标准的代码结构，在此基础上进行标记生成，能够在保证程序源代码结构和语义的同时，压缩代码的数据量，减小其所占的内存空间，提高检测的效率。生成标记的方法分为精确标记生成和模糊标记生成两种。精确标记生成，即将语句用原意标记精确替换。若原语句声明了一个int类型的变量，经过精确标记生成后得到的语句为IT；若原语句声明了一个long类型的变量，经过精确标记生成后得到的语句则为LG。该种标记生成方法可以非常精确的保留原程序源代码的语义，但无法应对抄袭者替换等价数据类型的抄袭手段。模糊标记生

16、成，即将语句用类似标记模糊替换。若原语句声明了一个double类型的变量，经过模糊标记生成后得到的语句为FT；若原语句声明了一个float类型的变量，经过模糊标记生成后得到的语句同样为FT。该种标记生成方法弥补了精确标记生成方法的缺点，但无法完全保留原程序源代码的语义，更容易产生误判断。因此,本项目根据分级处理的结果,在不同难易程度使用不同的标记生成方法,尽量避免判断误差。3）生成N-gramN-gram算法的处理过程能够较好地解决传统的基于TOken的程序源代码抄袭检测技术的问题，提高检测的准确率。gram原代表一个字符，在本文中则代表一条被预处理和标记生成处理后的语句，该语句可能为一个标记

17、或一条完整语句。N-gram算法中最关键的是N值的选择，它会直接影响最后相似度的计算结果，因为若N值太小，会忽略原程序源代码中的结构和顺序，若N值太大，又会降低检测的准确性。因此，由于考虑用户较难选取适当的N值，本文中N的取值将由分级处理和代码规模综合计算后决定。4）计算相似度在信息文本检测领域有很多相似度算法，本文采用的是ManhattanDiStanCe（曼哈顿距离），该算法较其他相似度算法准确度更高。计算公式如下：DlStMan（p,q）=ZIp,-司,/=IDiStMan（p,q）SltTlMany夕）=1EiMaHPMi）/=1其中，Pi和5分别是第i个N-gram在两段程序源代码P

18、和q中出现的频度，n是两段程序源代码中N-gram的总数。5）分级处理目前大部分的抄袭检测算法都采用阈值来控制检测的准确度，但阈值的设置很难做到较精确地自动计算设置，一般由用户自行判断输入。很多用户无法很好的理解阈值的概念,无法设置适当的阈值,导致检测系统的准确率不可避免地受到影响。因此,本项目采用分级处理的方法,将抽象的阈值形象具体成代码的难易程度。通过用户选择的作业难易程度等参数，再结合程序源代码的规模，进而在预处理和标记生成阶段对程序源代码进行不同地、恰当地处理，有效地避免了传统阈值导致地判断误差。本系统底层使用的工厂模式会根据传入的不同的程序设计语言类型，实例化对应的关键字集合、预处理

19、类、标记生成类等，能够更准确地进行程序源代码的处理，同时增强了系统的扩展性。系统也会根据作业的命题是否相同，进行不同程度的结构化，避免由于命题不同但结构相同的两份作业被误判断为抄袭行为。作业难易等级则是保证系统最终检测准确度的关键因素。越简单的作业虽然越容易被抄袭，但抄袭的手段却越简单。抄袭者若想对该程序进行抄袭，能够使用的抄袭手段就只有增加注释和空白字符、更改变量名等，若实在要牵强地使用较高级抄袭手段，也只能勉强用上常量替换和方法抽取等。由于这段代码过于简单，这些手段甚至都无法被判别为是否属于个体间必然出现的不同或抄袭行为。因此，检测时的处理复杂度应该和作业的难易程度及代码规模成正比。3、成

20、果的创新特色1）设计了一种基于N-gram的检测算法；2）采用分级处理的方法，将抽象的阈值形象具体成代码的难易程度。通过用户选择的作业难易程度等参数，再结合程序源代码的规模，进而在预处理和标记生成阶段对程序源代码进行不同地、恰当地处理，有效地避免了传统阈值导致地判断误差。3）设计并实现一个ACM竞赛程序源代码复制检测系统。三、项目研究总结报告预定计划执行情况，项目研究和实践情况，研究工作中取得的主要成绩和收获，研究工作有哪些不足，有哪些问题尚需深入研究，研究工作中的困难、问题和建议。(字数不限，可加页面)1、项目研究和实践情况本项目组采用基于N-gram的检测算法，首先对C/C+程序源代码进行

21、预处理，转换为N-gram集合，通过统计N-gram的出现频度进行相似度计算。为提高检测的准确率，系统采用分级处理方法来进行优化，即将程序源代码按难易程度等进行划分，在预处理阶段根据不同的等级判断其可能采取的抄袭手段，从而减少因程序难易程度等因素造成的误判，使得检测更有针对性。实验结果表明，经过分级处理优化后，检测算法的针对性有了明显提高。课题组设计并实现了一个基于N-gram的ACM竞赛程序源代码复制检测系统。具体项目研究内容的执行情况如下：1)N-gram算法研究N-gram算法的处理过程能够较好地解决传统的基于Token的程序源代码抄袭检测技术的问题，提高检测的准确率。gram原代表一个

22、字符，在本文中则代表一条被预处理和标记生成处理后的语句，该语句可能为一个标记或一条完整语句。N-gram算法中最关键的是N值的选择，它会直接影响最后相似度的计算结果，因为若N值太小，会忽略原程序源代码中的结构和顺序，若N值太大，又会降低检测的准确性。因此，由于考虑用户较难选取适当的N值，本文中N的取值将由分级处理和代码规模综合计算后决定。计算公式如下：N=2：Xdffculty其中scale(n)为代码规模，difficulty为作业难易程度。这样虽然会对最终检测结果产生一定影响，但避免了由于用户选取N值不恰当而造成的较大错误。之后对得到的N-gram集合建立索引，统计每个N-gram的出现频

23、度，并将其存入N-gram文本即可。2)分级处理方法通过研究现有的抄袭检测技术，发现某些算法的确能够较准确地检测出两段程序源代码中的相同或相似之处，但在预处理阶段却不能很好的识别出这些相同或相似之处出现的必然性，即在特殊的条件下，两段代码必然会相同或相似的情况。因本系统的研究检测环境为ACM程序设计竞赛选手提交的源代码，所以不可避免的会出现以下特殊条件：一是若是同一命题作业，很有可能仅仅是为了实现在课堂上所学的算法或程序，因此大部分学生上交的代码相同或相似率必然很高，此类算法或程序有以下几个共同特点：算法或程序本身不是特别复杂；算法或程序有固定的标准的写法，且可被改变替换处较少；在同一名任课老

24、师的指导教学或同一本教材的参考下完成作业。二是若是不同命题作业，对于某些特定的检测算法(如将整行语句替换成个别标识符)，相当于将代码结构化，虽然减少了很多系统占用的内存空间，提高了效率，但忽略了程序源代码的实现细节，很有可能造成较严重的问题：如两个程序实现了不同的功能，但具有相同的结构，结果被系统检测为抄袭行为。根据上述条件，本文要求用户在检测之前向系统提供如下前提条件：(a)语言类型。不同的程序设计语言，在结构和关键字上都有所不同。(b)作业难度。难度的设置应考虑上述特殊条件(1)中的共同特点，难度越低，检测的方式应该越简单，甚至可提供可选的检测条件，增强检测的灵活性。(c)是否为同一命题作

25、业。若是同一命题，则可对其进行结构化处理，提高检测的时间、空间效率，否则需综合考虑以上条件进行处理。本系统使用的分级处理方法取代了传统的阈值设置，将抽象的阈值转化为形象具体的难易程度划分，提高了检测算法的准确度和用户体验。3)基于N-gram算法检测系统的底层检测计算框架的设计和实现。为了提高检测系统的检测准确率和针对性,本文采用了N-gram算法与分级处理的方法对系统进行了实现和优化。N-gram算法是一种统计语言模型，适用于语音识别、文字识别、文本分类、信息检索、机器翻译和中文分词等领域。N-gram可以很好地保持程序源代码的结构和语义，在此基础上进行抄袭检测，可以有效地提高检测的准确度。

26、4)系统实现与性能测试本课题组已成功地开发出了一个ACM竞赛程序源代码复制检测系统，该系统能够实现对程序源代码复制的检测，大量的测试实验表明，该系统检测准确性高。2、项目研究情况（1）程序源代码抄袭检测技术、抄袭手段分类及应对不同情况的分级处理方法，现有检测系统原型及其主要算法研究。程序源代码抄袭检测主要是通过对比两段程序源代码，计算这两段程序源代码之间的相似度并得到一个0.0到1.0之间的相似度值，再通过设置阈值（可由系统自动计算或用户设置）来划分出是否有抄袭行为嫌疑的程序代码片段，进而判断目标程序源代码中是否存在抄袭行为。目前较常用的程序源代码检测技术一般为属性计数法和结构度量法两种。属性

27、计数法是统计程序源代码中所包含的各种属性（即成员变量），并将其映射到给定的向量空间中，再计算这两段程序源代码之间的相似度值。但该方法即使在向量维度上进行优化，准确度仍然较低，误判断较多。Verco等人也指出“单纯地增加向量的维数并不能减少检测的错误率，提高检测精度”。结构度量法是将程序源代码进行预处理成特殊的数据序列，再利用相似度计算公式计算出相似度值。相比属性计数法，该方法可将程序源代码中的结构和语义加入检测判断过程，提高检测准确度。基于结构度量法的检测算法通常包括以下两个步骤：1）程序源代码预处理。即将程序源代码进行标准格式化、注释和冗余空白字符过滤、关键字标识符替换、常量替换、数据类型等

28、价替换和统一大小写等。目前常用的预处理方法包括：基于String的方法、基于Token的方法和基于AGT（AbstractGrammarTree,抽象语法树）的方法等。基于String的算法，即将程序源代码以行为单位分割成若干字符串的集合，每个程序代码片段包含相邻的字符串，判断两两程序代码片段的字符串是否相同,再根据程序代码片段相似度判断是否存在抄袭行为。该算法检测准确率不高，代表算法有1995年Baker提出的参数化匹配算法。基于Token的算法，即对程序源代码进行词法分析，生成TOken序列，再对比检测两段程序源代码的TOken序列中相同的片段。该算法效率很高，但准确度仍然较低。基于AGT

29、的算法，即利用工具对程序源代码进行词法语法分析，得到该段程序源代码的抽象语法树，判断两段程序源代码的抽象语法树中的子树是否相似，再根据相似子树的相似性判断相似度。该算法准确度较高，但冗余较大，效率较低。2)相似度计算。即对程序源代码预处理后，得到其对应的数据序列，再根据两段程序源代码的数据序列进行相似度计算。目前常用的相似度计算方法有向量模型法和字符串匹配算法两类，如点阵图法、序列匹配算法、LCS(LongestCommonSubsequence,最长公共子序列)算法、GST(Greedy-String-Tiling)算法和RKR-GST(Running-Karp-RabinGreedy-St

30、ring-Tiling)算法、WinnOWing算法、余弦度量法等。上述两种方法虽在一定程度上能够检测出程序源代码中的相似处，但效率和准确率都比较低，不能非常有效地应对所有的抄袭手段。且这些算法过于依赖阈值,阈值的设置直接地影响了算法的准确度，而某一算法的阈值需要经过大量实验才能较精确地确定，当情况发生变化时，阈值或需重新设置，这无疑增大了算法设计实现和程序开发的难度。1999年，DiCkGrUne提出了SIM(SoftwareSimilarityTest)系统。该系统采用一种用于检测DNA序列相似性的字符串排列算法(时间复杂度为0(r),其中n为语法分析树最大长度)得到相似度值。SlM系统的

31、检测步骤如下：a)使用词法分析器生成代表程序源代码结构和含义的标记串；b)将标记串分割成若干部分，每一部分代表一个模块，再与其他程序源代码生成的的标记串的每个模块依次匹配，为匹配结果计分；c)利用得到的分数计算相似度，计算公式如下：c.7.2score(ptp2)Sunilanty=SCOre(PLPI)+SCOre(P2,p2)其中，Similarity表示两段程序源代码之间的相似度，SCOre函数表示两个模块匹配的分数。SlM系统仅能检测部分抄袭手段，且待检测的程序源代码量较大、数量较多时，检测效率会受到较大的影响，运行效率明显降低。1992年,Wise在已有的PlagUe系统的基础上开发

32、了YAP1(YetAnotherPlague)系统，两年后推出了YAP2系统，在1996年推出了YAP3系统。YAP系列系统的检测步骤如下：(1)对程序源代码进行词法分析，并生成特定的标记(TOken)串；(2)进行相似度计算。YAP系列系统中的YAP3系统经过经过Wise的反复修改和实验证明，抄袭检测效果不错，可覆盖上述十二种抄袭手段中的大部分抄袭手段。1996年，L.Prechelt等人用JaVa语言开发了JPlag系统，其相似度计算方法于YAP3系统相同，即RKR-GST算法，但其优化了YAP3系统中RKR-GST算法的时间复杂度，提高了检测效率。JPIag系统的检测步骤如下：a)b)将

33、程序源代码生成相应的标记字符串(TokenString)；将标记字符串分割成更新的tile子串，再对子串集两两进行相似度计算。计算公式如下：b/人m2xCoverage(Mles)Sm(AI)=同+同，Coveragtiles)=ZlengthnatcM.a,b,lengh)Gtiles其中，IAl和IBl分别表示程序源代码A和B中的标记字符串长度，match函数表示起始位置分别为a和b,长度为length的相同子字符串。JPlag系统功能与YAP3系统和下面将要介绍的MOSS系统一样强大，抄袭检测的准确度和效率较高。1994年，AIeXAikerl开发了MOSS(MeasureofSoftw

34、areSimikirity)系统。该系统结合了属性计数法和结构度量法，并在检测过程中包含了数据预处理、统计标识符出现次数和字符串匹配算法，功能强大，支持目前大部分流行程序设计语言的检测，但检测效率较低。(2)基于N-gram检测算法研究N-gram是一种统计语言模型，其定义网为：设Z为一个字母表，S是一个由Z中的字母组成的字符串。S表示S的长度，Sih是S中第i个字母(i从1开始),SM是S中从第i到第j个字母组成的S的子字符串，N是一个整数，且N不大于S,则S中的N-gram就是长度为N的S的邻接子字符串,如：SlijN.i,Si+uNoG(S,N)表示字符串S中所有的N-gram的集合，长

35、度为ISl的字符串可以生成L=IS卜N+1个N-gram,如:S=detection,S=12,N=5,则G(S,N)=(l,detec),(2,etect)，(3,“tecti)，(4,ttectio,),(5,t4ction,)。N-gram适用于语音识别、文字识别、文本分类、信息检索、机器翻译和中文分词等领域，且于1995年被M.Damashek首次应用于文本相似度度量，近几年被证明适用于文本抄袭检测，能有效地提高文本抄袭检测的准确率，且优于普通字符串匹配算法。N-gram算法统计N-gram集合中每个元素出现的频率，而忽略了该元素在程序源代码中的原始位置，使得检测抄袭时能够较好地降低因

36、抄袭者使用代码块及其内部语句重排序和表达式拆分等较高级抄袭手段对检测准确度造成的影响。同时，对生成N-gram前的预处理也可以较有效地检测大部分低中级抄袭手段，使得N-gram算法在一定程度上能够达到较理想的检测准确度。（3）基于N-gram算法检测系统的底层检测计算框架的设计和实现，采用分级处理方法提高检测系统针对性的代码实现。为了提高检测系统的检测准确率和针对性,本文采用了N-gram算法与分级处理的方法对系统进行了实现和优化。N-gram算法是一种统计语言模型，适用于语音识别、文字识别、文本分类、信息检索、机器翻译和中文分词等领域。N-gram可以很好地保持程序源代码的结构和语义，在此基

37、础上进行抄袭检测，可以有效地提高检测的准确度。几乎所有的检测算法都需要为其设置阈值，而阈值的概念对于一般普通的用户而言较抽象晦涩，使其无法达到最理想的值，这也极大程度地影响了最后相似度的计算结果。分级处理是将抽象的阈值形象具体化，即将程序源代码按难易程度划分（可由系统根据程序源代码规模自动计算或用户选择设置），帮助用户在使用系统时更方便清晰的设置恰当合理的“阈值”，提高用户体验和检测针对性。系统实现有五个重要步骤：f）读取程序源代码数据。使用JaVa的JDK内置的IO相关API,读取程序源代码。g）预处理。根据难易程度的不同，对待检测程序源代码进行不同复杂度地格式化预处理，预处理方式由用户选择

38、填写传入的相关参数确定。h）生成标记。根据程序源代码使用的程序设计语言的语法规则和关键字，将其转换为对应的标记序列，可以较好的压缩待比较数据的空间占用大小，提高检测系统的运行效率，还可以保持程序源代码中原有的结构和语义,即结构化。i）生成N-gram。将标记序列转换为N-gram集合，统计每个N-gram出现的频率，并将得到的N-gram文本存入数据库中。j）计算相似度。从数据库中查询区其他程序源代码的N-gram文本，与待对比的程序源代码生成的N-gram频度向量依次进行相似度计算，得到相似度值。本文采用了较为灵活的架构设计，尽量做到能够根据用户不同的需求(即选择传入的不同参数)进行较为恰当

39、地处理和检测，但又不需要用户做出太多太复杂的操作，在保证系统检测的准确度、针对性和效率的同时，有较好的用户交互和体验。同时开发了大部分表示层和中间层，让系统有较高的扩展性，也为第三方开发者提供了二次开发的接口和服务。1)预处理预处理主要用于去除程序源代码中的混淆、无用数据，并按照用户指定的程序设计语言编码标准及风格格式化该该程序源代码，同时可检测表2-2中修改排版的抄袭手段。本文包含的预处理方式有以下几种： 删除程序源代码中的注释语句。 将一行包含多条语句的代码转化成每行一句。 将本为一行的多行代码转化成一行。 删除代码中的多余空白字符(空格、Tab)o 将所有字母转化成小写字母。预处理的流程

40、和伪代码如下：classpreprocess/格式化多余代码(注释等)：/返回类型和参数类型RetumParam为一个自定义的返回参数类/其中包含处理后的代码、是否跳过、是否换行等参数RetumParamformatConfusion(ReturnParamretumParam)/处理多行注释/判断该语句是否属于多行注释块if(toContinue)/判断该语句中是否存在多行注释结束符if(SegmentAnnotationEndIndex-1)/删除该语句中多行注释结束符之前的所有字符else/删除该语句中从多行注释起始符到结束符之间的所有字符/处理单行注释/判断该语句是否存在单行注释符if

41、singleAnnotationindex-1)/删除该语句中单行注释符之后的所有字符1/格式化单到多语句(本为多行语句的单行语句)/和多到单行语句(本位单行语句的多行语句)：ReturnParamformatConfusion(ReturnPararnreturnParam)/判断语句中是否存在语句结束符，且不在语句末尾if(semicolonindex-I&semicolonindex!=h()-1)/判断该语句结束符之前的语句中圆括号是否完全匹配if(parcnthesisCount=0)/在该语句结束符后换行/若存在语句结束符，且在语句末尾，且圆括号不完全匹配else/设置该语句结尾

42、不换行)/其他预处理操作：过滤常量和变量等I前三种预处理方式可由用户选择是否进行，这样可以有效地避免对格式规范的程序源代码进行无用的预处理操作，提高系统的检测效率。系统将会根据用户提供的难易程度进行一种或多种预处理，即分级处理，得到的程序源代码有效地去除了原程序源代码中的注释和多余空白字符,在保证生成标记和N-gram过程中数据的有效性的前提下，直接地过滤了多余无用字符对检测的影响，且格式规范,有利于提高检测系统的准确性。预处理的结果，如表1所示。表1预处理结果编号原语句处理结果1inti=0;/这是单行注释inti=0;2inti=0;/*这是多行注释*/inti=0;3if(true)br

43、eak;if(true)break;for(inti=0;4in;for(inti=0;in;i+)i+)5inti=0;inti=0;2)生成标记预处理后的程序源代码有很好的符合对应程序设计语言类型标准的代码结构，在此基础上进行标记生成，能够在保证程序源代码结构和语义的同时，压缩代码的数据量，减小其所占的内存空间，提高检测的效率。生成标记的方法分为精确标记生成和模糊标记生成两种。精确标记生成，即将语句用原意标记精确替换。若原语句声明了一个im类型的变量，经过精确标记生成后得到的语句为IT；若原语句声明了一个IOng类型的变量，经过精确标记生成后得到的语句则为LG。该种标记生成方法可以非常精确

44、的保留原程序源代码的语义，但无法应对抄袭者替换等价数据类型的抄袭手段。模糊标记生成，即将语句用类似标记模糊替换。若原语句声明了一个double类型的变量，经过模糊标记生成后得到的语句为FT；若原语句声明了一个float类型的变量，经过模糊标记生成后得到的语句同样为FT。该种标记生成方法弥补了精确标记生成方法的缺点，但无法完全保留原程序源代码的语义，更容易产生误判断。因此，本项目根据分级处理的结果，在不同难易程度使用不同的标记生成方法，尽量避免判断误差。3)生成N-gramN-gram算法的处理过程能够较好地解决传统的基于Token的程序源代码抄袭检测技术的问题，提高检测的准确率。gram原代表

45、一个字符，在本文中则代表一条被预处理和标记生成处理后的语句，该语句可能为一个标记或一条完整语句。(I)N-gram算法中最关键的是N值的选择，它会直接影响最后相似度的计算结果，因为若N值太小，会忽略原程序源代码中的结构和顺序，若N值太大，又会降低检测的准确性。因此，由于考虑用户较难选取适当的N值，本文中N的取值将由分级处理和代码规模综合计算后决定。计算公式如下：N=金Xdifficulty其中scale(n)为代码规模，difficulty为作业难易程度。这样虽然会对最终检测结果产生一定影响，但避免了由于用户选取N值不恰当而造成的较大错误。之后对得到的N-gram集合建立索引，统计每个N-gr

46、am的出现频度，并将其存入N-gram文本即可。4)计算相似度在信息文本检测领域有很多相似度算法，本文采用的是ManhattanDistance(曼哈顿距离)，该算法较其他相似度算法准确度更高。计算公式如下：DiStMan(P，夕)=ZIP，-司，Z=IDiStMan(p,q)Slf11Man(p,q)=ZMQMP,5)/=1其中，Pi和中分别是第i个N-gram在两段程序源代码P和q中出现的频度，n是两段程序源代码中N-gram的总数。目前大部分的抄袭检测算法都采用阈值来控制检测的准确度，但阈值的设置很难做到较精确地自动计算设置，一般由用户自行判断输入。很多用户无法很好的理解阈值的概念，无法

47、设置适当的阈值，导致检测系统的准确率不可避免地受到影响。因此，本项目采用分级处理的方法，将抽象的阈值形象具体成代码的难易程度。通过用户选择的作业难易程度等参数，再结合程序源代码的规模，进而在预处理和标记生成阶段对程序源代码进行不同地、恰当地处理，有效地避免了传统阈值导致地判断误差。本系统底层使用的工厂模式会根据传入的不同的程序设计语言类型，实例化对应的关键字集合、预处理类、标记生成类等，能够更准确地进行程序源代码的处理，同时增强了系统的扩展性。系统也会根据作业的命题是否相同，进行不同程度的结构化，避免由于命题不同但结构相同的两份作业被误判断为抄袭行为。作业难易等级则是保证系统最终检测准确度的关键因素。越简单的作业虽然越容易被抄袭，但抄袭的手段却越简单。例如一段简单的程序如下：publicstaticvoidmain(Stringargs)intsum=0;for(inti=l;i=10;i+)sum+=i;).println(“整数1到10的和为：”+sum);)抄袭者若想对该程序进行抄袭，能够使用的抄袭手段就只有增加注释和空白字符、更改