摘  要

在拷贝他人代码提交的现象在程序设计课程中屡禁不止，这种行为使得教师无法对学生的学习水平做出准确的评价，因此在在线测评系统中包含对代码重复率检测的模块。但是现有的代码重复率检测算法仍然存在一些不足，无法应对一些将拷贝代码稍作修改以避过检出的情形，我们将这些修改的行为简单地归纳为5种类型的再编辑手段。在本研究中，首先通过研究原有的代码相似度检测算法，选取了Levenshtein距离作为评判相似度标准的依据，在第2、第3种类型的再编辑情形下取得了很高的检出率。在第三章中，提出了标签化的思想来对代码文本进行去特殊化，引入标签化模块后在第1、第4种情形下的重复率检出程度得到了极大的提升。在此基础上，又添加了函数提取模块，用以应对第5中再编辑情形，从而使得综合Levenshtein距离、标签化、函数提取的算法在5种类型下都取得了令人满意的检出率。同时，使用了加权平均的思想对学生的独立代码率进行计算，使得最终对学生评价具有较好的稳定性。最后，使用数据来源杭州师范大学在线测评系统的提交代码，对本算法的准确性进行评价，在84份测试数据下取得的精确度为92.86%，召回率为87.50%。

 

 

关键词：代码查重，文本匹配，数据分析

目  录

 

第一章 绪论 1

1.1 引言 1

1.2 国内外研究现状 1

1.3 开发的目标与意义 2

1.4 创新点 2

1.5.1度量标准 2

1.5.2采用加权方式计算度量 2

1.5.3特殊情况处理 2

第二章 此前研究 3

2.1 文本处理 3

2.2 最长公共子序列算法 5

2.3 Levenshtein距离 7

第三章 研究内容 10

3.1 函数和变量的标签化处理 10

3.1.1 引入标签 10

3.1.2 标签化的实现 10

3.1.3 标签化对结果的改善 13

3.2 消除函数嵌套扰乱 14

3.3 重复率的带权测算 16

3.3.1 ICR与重复率的关系研究 16

3.3.2 ICR加权计算 19

第四章 结果论证 19

4.1 算法的混淆函数 19

4.2 算法性能分析 24

第五章 总结与展望 25

参考文献 26

致  谢 27