综合大作业 · 代码相似性检测

#作业

源目录没有保存独立的教师题面，只保存 project2024 提交文件。因此我只记录“最后做成了什么”，不把实现细节倒推成课程硬性要求。

可确认的提交目标

程序读取多份 C 代码，抽取能够代表程序结构的“关键信息流”，削弱标识符命名、空白和局部书写差异的影响，再用编辑距离计算两份归一化结果的相似度，输出超过阈值的代码编号。

保存材料包括：

  • 代码相似性检测1.0.c 与 代码相似性检测2.0.c；
  • 独立的编辑距离实现 editdistDP.c；
  • C 关键字与库函数表 keepwords.txt；
  • 待比较代码集合 codes.txt、codes1.txt；
  • 中间信息流和相似结果 debuginfo.txt。

处理流程

查看提交内容与实现

1. 词法级归一化

程序逐字符扫描源代码，把字母、数字、括号、花括号、空白和其他符号分开处理。keepwords.txt 中保存的 C 关键字和常用库函数名会被保留；普通变量名、函数名等则被统一化，以减少单纯改名带来的差异。

2. 提取函数与程序信息流

提交为每个函数生成归一化字符序列，并继续拼接成整个程序的关键信息流。保存的 debuginfo.txt 同时列出了函数级和程序级结果，便于检查归一化是否符合预期。

3. 编辑距离

两字符串编辑距离使用动态规划。设 dp[i][j] 为前 ii、jj 个字符之间的最小编辑次数，则

dp[i][j]=min⁡{dp[i−1][j]+1,dp[i][j−1]+1,dp[i−1][j−1]+[si≠tj].dp[i][j]=\min\begin{cases} dp[i-1][j]+1,\\ dp[i][j-1]+1,\\ dp[i-1][j-1]+[s_i\ne t_j]. \end{cases}

边界为 dp[i][0]=i、dp[0][j]=j。

4. 相似度与输出

提交把编辑距离按两串长度归一化成相似度，并用 LIMIT=0.95 判断是否输出同组编号。debuginfo.txt 中还保留了一次比较结果：编号 100009 与 100011 的相似度为 0.456710。

5. 1.0 与 2.0 的差异

两版核心算法相同。2.0 把代码数组和标志数组容量从约 1000 扩到约 10000，并留下“关键字查询可继续优化”的注释；不是一套全新的算法。

这份提交的边界

查看实现复盘
  • 关键字表按线性扫描查找，每识别一个词都可能遍历整表；可排序后二分，或改为散列表。
  • 动态规划矩阵固定按 3300×3300 申请，空间为 O(mn)O(mn)，长代码会触及容量上限；若只需距离，可用滚动数组降到 O(min⁡(m,n))O(\min(m,n))。
  • 源实现把字符串长度先加一、循环又使用 <=，存在边界访问风险；正式使用前应按标准 0..m0..m、0..n0..n 的 DP 定义重新核对下标。
  • 归一化是自写字符扫描器，难以完整覆盖注释、字符串字面量、预处理指令和复杂 C 语法。它适合课程项目原型，不能等同于完整编译器前端。
  • 高相似度只表示这种特征和距离下接近，不足以单独证明抄袭。

评论