Code_Detection
“程序类作业相似度检测软件”,检测C++代码文件的相似度。
Aim at homework
主要针对学生日常作业的一个检测分析，能清晰得将相似度结果展现给老师，使老师更容易了解学生的作业动态，减轻老师的工作量。
程序执行过程(算法实现流程图.png)
程序代码预处理
- 格式化。 去除空行、注释、头文件及无效字符。
- 等价结构替换。 如循环结构（for、while）、条件结构（if-else、switch-case）、常见等价语句（A+=B、A=A+B，K++、++K、K=K+1）
- 代码块分割。 如for、while、if语句switch-case语句后的{}。
建立树形结构
- 生成属性向量集，需要根据C++语言的特点来选择合适的属性集。
- 利用栈的思维根据{}创建结点，结点包含属性向量集、关键词、语句hash值、相似度、深度等属性。
计算两个代码文件的相似度
- 深度优先搜索遍历语法树，在回溯时统计子结点与父节点的综合信息，逐层往上求得相似度
- 对属性向量集采用余弦系数法计算相似度。
- 剪枝优化，对差异性过大结点进行剪枝，不再往下搜索。
- LCS算法优化，在函数体层次引入LCS权重分配，既提高相似度判定的精确度,又不会有太大的时间复杂度。
确定相似度阈值(仅仅在我构造的数据集上，包括请同学copy的代码)
- 确定合适的相似度阈值能够减少误判。
- 通过对6105组数据使用模拟退火算法确定相似度阈值，目前准确率可以达到91.6%