摘 要

本文主要研究了基于文本和基于属性计数的代码相似度算法的实现，以及这两种算法在Python程序代码相似度检测中的应用。基于文本的检测方法以相同子串集总长度占串长的比例为基础，对源代码分块内容进行顺序比对或最大匹配比对，从而计算出相似值。基于属性计数的检测方法以本文设计实现的Python词法分析器为基础，进行代码中属性的计数，通过可自定义的加权平均获得整体的相似度。在确定合适阈值后，根据代表入门难度与熟练难度的两类样本检测结果，基于文本的最大匹配比对方法和属性计数方法均可达到良好的检测效果。本文的特色在于，在传统的字符串比对基础上，针对程序主要结构进行分块比较，提高了检测准确度；自主实现了一个Python词法分析器。系统具有一定的拓展性和易用性，具备在实际教学中的应用价值，对于程序特征的挖掘与比较具备指导意义。

关键词：Python；代码相似度检测；属性计数；词法分析器；

Abstract

This paper studies the implementation of code similarity calculation based on text-based approaches and attribute counting and the application of these two algorithms in code similarity detection of Python. The text-based approach is based on the ratio of the total length of identical substring set to the length of the original string. Then the system splits every source code file into blocks according to the structure of the source code. Next, compare every single line between the blocks in sequence, or use the maximum matching to calculate the similarity. The attribute-counting method is based on a Python lexical analyzer designed and implemented in this paper. It counts the attributes in the code and obtains the overall similarity through a set of customizable weight and attribute-counting results. According to the real schoolwork samples representing the difficulties of entry-level and professional-level, the text-based maximum matching comparison method and attributes counting method delivered acceptable results after the appropriate thresholds are determined. The highlights of this article including an independently implemented Python lexical analyzer and improving detection accuracy by combining the structure characteristic of programs with traditional text-based comparison method. The system has expansibility and usability, which assuring its application in the actual environment. And it also has guiding significance for the mining and comparison of program features.

Key Words：Python；Code Similarity Calculation; Attribute counting；Lexical Analyzer；

目 录

第1章 绪论 1

1.1 研究背景和意义 1

1.2 国内外研究现状 1

1.2.1. 国外研究现状 1

1.2.2. 国内研究现状 2

1.3 研究内容和目标 3

第2章 软件技术概要 4

2.1 源代码复制方式定义 4

2.2 系统总体设计 4

2.3 相似度检测方法 6

2.3.1. 字符串相似度检测 6

2.3.2. 属性计数检测 6

2.3.3. 结构度量 6

2.4 词法分析 7

2.5 本章总结 7

第3章 系统实现详细叙述 8

3.1 基于字符串的相似度计算 8

3.1.1. 原理和设计 8

3.1.2. 实现简述 10

3.2 词法分析器 11

3.2.1. 原理及设计 11

3.2.2. 实现简述 17

3.3 基于属性计数相似度计算 20

3.3.1. 设计简述 20

3.3.2. 实现简述 21

3.4 其他模块 21

3.4.3. 用户界面 21

3.4.4. 主控制模块、文件读写及数据存储模块 23

第4章 系统测试及结果阐述 24

4.1 测试样本及测试方案说明 24

4.2 测试结果分析 24

4.2.1. 测试数据处理方法描述 24

4.2.2. 数据阈值的选取与典型样本分析 25

4.2.3. 识别错误结果和复制方式关联的分析 31

4.2.4. 算法总体效果分析 33

第5章 总结和展望 35

5.1 研究成果总结 35

5.2 工作展望 35

参考文献 36

附 录 37

致 谢 38

绪论

研究背景和意义

随着无纸化教学、办公的潮流逐渐被人们认可，作为计算机应用前线的软件工程专业，使用计算机提交编程实验作业甚至对学生进行考核已经普及。但是，传统的在线评测系统（Online Judge，OJ）只能对提交代码运行的正确性和时间、资源进行检验和限制，缺乏对代码相似度的检测，无法对涉嫌代码抄袭的提交进行区分。

对于初学者而言，接触到的代码编写任务往往易于获取、复制和进行简单的等效修改。在实际的教学活动中，对提交的代码进行人工逐一进行比对的方法是不可行的。为了切实提升学生动手编程的能力和教学质量，使用计算机自动化检测代码相似度配合OJ平台的正确性判定功能可以起到事半功倍的效果。对于初学者而言，由于编程任务相对简单，思路多样性较低，不排除会出现误判的情况。但即使如此，对于相似度较高的提交进行人工核实仍能减少大部分的比对工作。目前，可用的知名公共代码检测服务，例如软件相似度度量系统（Measure Of Software Similarity，MOSS），大多作为在线服务的形式存在，不能保证源代码的保密性，也不能适应某些特定的需求。开源的代码检测工具则可以在本地运行，并根据需求进行一定的功能调整，适应性和安全性更强。

在实际的生产环境中，代码复用，又称为“软件克隆”，是十分普遍的现象[1]。在软件迭代时检测复用的代码可以提高软件性能并减少维护成本和工作量[1]，因此代码相似度检测也可以应用到实际的生产环境，在敏捷开发等迭代开发方法中起到快速查重等的作用。

国内外研究现状

国外研究现状

国外由于计算机教育普及比较早，因此相关的代码克隆检测系统研发更早、应用较广。比较知名的有SIM、MOSS、JPlag、YAP3、Plaggie、SID、n-gram和NED等。其中JPlag、SIM、YAP3原理是字符串划分比对；MOSS使用字符串Hash指纹^[2]。虽然上面所述的这些拥有较长历史的检测系统原理只是相对简单的文本意义上的检测或者同时结合属性计数作为特征，但其优点在具备较好检测能力的同时效率更高，甚至可以广泛地支持各种计算机语言，比如MOSS已经支持24种编程语言。正是由于不对编程语言敏感，这些系统作为公共服务的同时又反过来促进了它们的发展。缺点就是由于没有深入到对语义上的检测，对于表达式等效更改、冗余语句干扰和语句顺序调换等反检测手段效果欠佳。